Teorema de Ore

El teorema de Ore es un resultado de la teoría de grafos demostrado en 1960 por el matemático noruego Øystein Ore . Proporciona una condición suficiente para que un grafo sea hamiltoniano , estableciendo esencialmente que un grafo con un número suficientemente grande de aristas debe contener un ciclo hamiltoniano . Específicamente, el teorema considera la suma de los grados de pares de vértices no adyacentes : si la suma de los grados de cada par es al menos igual al número total de vértices del grafo, entonces el grafo es hamiltoniano.

Sea G un grafo (finito y simple) con n ≥ 3 vértices. Denotamos por deg v el grado de un vértice v en G , es decir, el número de aristas incidentes en G a v . Entonces, el teorema de Ore establece que si

entonces G es hamiltoniano .

Es equivalente a demostrar que todo grafo no hamiltoniano G no obedece la condición (∗) . En consecuencia, sea G un grafo con n ≥ 3 vértices que no es hamiltoniano, y sea H formado a partir de G añadiendo aristas una a una que no creen un ciclo hamiltoniano, hasta que no se puedan añadir más aristas. Sean x e y dos vértices no adyacentes cualesquiera en H. Entonces, añadir la arista xy a H crearía al menos un nuevo ciclo hamiltoniano, y las aristas distintas de xy en dicho ciclo deben formar un camino hamiltoniano v ₁ v ₂ ... v _n en H con x = v ₁ e y = v _n . Para cada índice i en el rango 2 ≤ i ≤ n , consideremos las dos posibles aristas en H de v ₁ a v _i y de v _{i − 1} a v _n . Como máximo, uno de estos dos bordes puede estar presente en H , ya que de lo contrario el ciclo v ₁ v ₂ ... v _{i − 1} v n _v n _{− 1 ...} v i _v 1 _sería un ciclo hamiltoniano. Por lo tanto, el número total de bordes incidentes a v ₁ o v _n es como máximo igual al número de elecciones de i , que es n − 1. Por consiguiente, H no cumple la propiedad (∗) , que requiere que este número total de bordes ( deg v ₁ + deg v _n ) sea mayor o igual que n . Dado que los grados de los vértices en G son como máximo iguales a los grados en H , se deduce que G tampoco cumple la propiedad (∗) . 

Palmer (1997) describe el siguiente algoritmo simple para construir un ciclo hamiltoniano en un grafo que cumple la condición de Ore.

1. Disponga los vértices de forma arbitraria formando un ciclo, ignorando las adyacencias en el grafo.
2. Mientras el ciclo contenga dos vértices consecutivos v _i y v _{i  +  1} que no sean adyacentes en el grafo, realice los siguientes dos pasos:
   • Buscar un índice j tal que los cuatro vértices v _i , v _{i  +  1} , v _j , y v _{j  +  1} sean todos distintos y tal que el grafo contenga aristas de v _i a v _j y de v _{j  +  1} a v _{i  +  1}
   • Invierte la parte del ciclo entre v _{i  +  1} y v _j (inclusive).

Cada paso incrementa el número de pares consecutivos en el ciclo que son adyacentes en el grafo, en uno o dos pares (dependiendo de si v _j y v _{j  +  1} ya son adyacentes), por lo que el bucle externo solo puede ocurrir como máximo n veces antes de que el algoritmo termine, donde n es el número de vértices en el grafo dado. Por un argumento similar al de la demostración del teorema, el índice deseado j debe existir, o de lo contrario los vértices no adyacentes v _i y v _{i  +  1} tendrían un grado total demasiado pequeño. Encontrar i y j , y revertir parte del ciclo, se puede lograr en tiempo O( n ). Por lo tanto, el tiempo total para el algoritmo es O( n ² ), que coincide con el número de aristas en el grafo de entrada.

El teorema de Ore es una generalización del teorema de Dirac que establece que, cuando cada vértice tiene un grado de al menos n /2 , el grafo es hamiltoniano. Porque, si un grafo cumple la condición de Dirac, entonces claramente cada par de vértices tiene grados que suman al menos n .

A su vez, el teorema de Ore se generaliza mediante el teorema de Bondy-Chvátal . Se puede definir una operación de cierre en un grafo en la que, siempre que dos vértices no adyacentes tengan grados que sumen al menos n , se añade una arista que los conecta; si un grafo cumple las condiciones del teorema de Ore, su cierre es un grafo completo . El teorema de Bondy-Chvátal establece que un grafo es hamiltoniano si y solo si su cierre es hamiltoniano; dado que el grafo completo es hamiltoniano, el teorema de Ore es una consecuencia inmediata.

Woodall (1972) encontró una versión del teorema de Ore que se aplica a grafos dirigidos . Supongamos que un digrafo G tiene la propiedad de que, para cada par de vértices u y v , o bien existe una arista de u a v , o bien el grado de salida de u más el grado de entrada de v es igual o superior al número de vértices en G. Entonces, según el teorema de Woodall, G contiene un ciclo hamiltoniano dirigido. El teorema de Ore se puede obtener a partir de Woodall reemplazando cada arista en un grafo no dirigido dado por un par de aristas dirigidas. Un teorema estrechamente relacionado de Meyniel (1973) establece que un digrafo fuertemente conexo de n vértices con la propiedad de que, para cada par de vértices no adyacentes u y v , el número total de aristas incidentes a u o v es al menos 2 n − 1 debe ser hamiltoniano.  

El teorema de Ore también puede reforzarse para dar una conclusión más fuerte que la hamiltonicidad como consecuencia de la condición de grado en el teorema. Específicamente, todo grafo que satisface las condiciones del teorema de Ore es un grafo bipartito completo regular o es pancíclico ( Bondy 1971 ) .

• Bondy, JA (1971), "Grafos pancíclicos I", Journal of Combinatorial Theory, Serie B , 11 (1): 80–84 , doi : 10.1016/0095-8956(71)90016-5.
• Meyniel, M. (1973), "Une condition suffisante d'existence d'un circuito hamiltonien dans un graphe orienté", Journal of Combinatorial Theory, Serie B (en francés), 14 (2): 137– 147, doi : 10.1016/0095-8956(73)90057-9.
• Ore, Ø. (1960), "Nota sobre circuitos hamiltonianos", American Mathematical Monthly , 67 (1): 55, doi : 10.2307/2308928 , JSTOR 2308928 .
• Palmer, EM (1997), "El algoritmo oculto del teorema de Ore sobre ciclos hamiltonianos", Computers & Mathematics with Applications , 34 (11): 113–119 , doi : 10.1016/S0898-1221(97)00225-3 , MR 1486890 .
• Woodall, DR (1972), "Condiciones suficientes para circuitos en grafos", Actas de la Sociedad Matemática de Londres , Tercera Serie, 24 : 739–755 , doi : 10.1112/plms/s3-24.4.739 , MR 0318000 .