Saltar para o conteúdo

Teorema de Ore

Origem: Wikipédia, a enciclopédia livre.
Gráfico exemplificando o Teorema de Ore

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 wn para todo par de vértices v distintos não-adjacentes e wde G (*) então G é hamiltoniano.

Figura para provar o Teorema de Ore.

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 (*).

Ícone de esboço Este artigo sobre matemática é um esboço. Você pode ajudar a Wikipédia expandindo-o.