French
DeutschTeorema de Ore – Wikipédia, a enciclopédia livre
O Teorema de Ore é um resultado provado em 1960 pelo matemático norueguês Øystein Ore relacionado à Teoria dos grafos. Ele fornece uma condição suficiente para um grafo para ser Hamiltoniano, essencialmente, afirmando que um grafo com "quantidade de arestas suficiente" deve conter um ciclo de Hamilton. Especificamente, a teoria considera a soma dos graus dos pares de vértices não adjacentes: se cada um destes pares tem uma soma que, pelo menos, é equivalente ao número total de vértices no grafo, então o mesmo é Hamiltoniano.
Definição formal
[editar | editar código-fonte]Seja G um grafo simples e finito com n ≥ 3 vértices. Denotaremos por deg v o grau do vértice v em G i.e. o número de arestas incidentes em G a partir de v. Então, o Teorema de Ore mostra que se :deg v + deg w ≥ n para todo par de vértices v distintos não-adjacentes e wde G (*) então G é hamiltoniano.
Prova
[editar | editar código-fonte]A prova se resume a demonstrar que todo grafo G não hamiltoniano não obedece a condição (*). Suponha G um grafo com n ≥ 3 vértices não-hamiltoniano, e seja H formado a partir de G adicionando arestas de forma a não criar um ciclo hamiltoniano, até que não seja possível adicionar mais arestas. Sejam x e y dois vértices não-adjacentes de H quaisquer. Então, adicionando a aresta xy em H vai criar ao menos um novo ciclo hamiltoniano, e as outras arestas irão formar um caminho hamiltoniano v 1 v 2 ... v n em H com x = v 1 e y = v n. Para cada i no intervalo 2 ≤ i ≤ n, considere as duas arestas possíveis em H de v 1 a v i e de v i - 1 a v n. Ao menos uma dessas duas arestas estará presente em H, caso contrário o ciclo v 1 v 2 ... v i-1v nv n-1 ... v i será um ciclo hamiltoniano. Assim, o total de arestas incidentes em v 1 ou v n será igual ao número de escolhas de i, cujo valor é n - 1. Portanto, H não pode obedecer à proposição (*), o que requer que o número total de arestas (deg v 1 + deg v 1) seja maior ou igual a n. Assim, os graus dos vértices em G são iguais aos graus de H, e segue que G também não obedece a propriedade (*).
Referências
[editar | editar código-fonte]- Bondy, J. A. (1971), «Pancyclic graphs I», Journal of Combinatorial Theory, Series B, 11 (1): 80–84, doi:10.1016/0095-8956(71)90016-5.
- Meyniel, M. (1973), «Une condition suffisante d'existence d'un circuit hamiltonien dans un graphe orienté», Journal of Combinatorial Theory, Series B (em francês), 14 (2): 137–147, doi:10.1016/0095-8956(73)90057-9.
- Ore, Ø. (1960), «Note on Hamilton circuits», American Mathematical Monthly, 67 (1): 55, JSTOR 2308928, doi:10.2307/2308928.
- Palmer, E. M. (1997), «The hidden algorithm of Ore's theorem on Hamiltonian cycles», Computers & Mathematics with Applications, 34 (11): 113–119, MR 1486890, doi:10.1016/S0898-1221(97)00225-3.
- Woodall, D. R. (1972), «Sufficient conditions for circuits in graphs», Proceedings of the London Mathematical Society, Third Series, 24: 739–755, MR 0318000, doi:10.1112/plms/s3-24.4.739.
