CCT-UFCA/Ciência da Computação/Teoria dos Grafos/Grafos Hamiltonianos:

Definições fundamentais

Definição: Um caminho Hamiltoniano de um grafo $G$ é um caminho que contém todos os vértices de $G$. Similarmente, um ciclo Hamiltoniano de $G$ é um ciclo que contém todos os vértices de $G$.

Definição: Um grafo $G$ é Hamiltoniano se contém um ciclo Hamiltoniano.

Definição: O fecho Hamiltoniano de um grafo conexo $G$ é o grafo obtido pela adição sucessiva de arestas entre vértices $u$ e $v$ não adjacentes e tal que $d(u)+d(v)\geq n$.

Teoremas relacionados

Teorema 1: Seja $G$ um grafo conexo com pelo menos 3 vértices. Se $G$ é Hamiltoniano, então $\forall S\subset V(G)$:

$$\omega (G-S)\leq |S|$$

Prova: Seja $G$ Hamiltoniano e $C=<v_{1},v_{2},...,v_{n}>$ um ciclo Hamiltoniano de $G$. Seja $S\subset V(G)$ tal que $|S|=k\geq 1$.

Podemos observar naturalmente que $\omega (C-S)$ é no máximo igual a $k$, que ocorre somente quando $S$ não possui vértices adjacentes entre si. Como $G$ possui mais arestas que o ciclo $C$, temos que $\omega (G-S)$ é no máximo $\omega (C-S)$, que é no máximo $k=|S|$.

---

Teorema de Dirac: Seja $G$ um grafo simples com pelo menos 3 vértices e tal que $\delta (G)\geq \lceil {\frac {n}{2}}\rceil$. Então $G$ é Hamiltoniano.

Prova: Seja $G$ simples, tal que $V(G)\geq 3$ e $\delta (G)\geq \lceil {\frac {n}{2}}\rceil$ e suponha por absurdo que $G$ não é Hamiltoniano.

Seja $G$, então, o grafo maximal em arestas que atende à premissa e tal que $G$ não é Hamiltoniano. Sabemos que $G$ não é completo, visto que se assim fosse, seria Hamiltoniano. Ou seja, existem vértices $u$ e $v$ não adjacentes em $G$. Pela maximalidade de $G$, temos que a adição de $e=uv$ em $G$ gera um grafo $G'$ que é Hamiltoniano, isto é, gera um ciclo Hamiltoniano $C=<v_{1},v_{2},...,v_{n},v_{1}>$, tal que $v_{1}=u$ e $v_{n}=v$. Sabemos que $C$ contém a aresta $e=uv$ adicionada, logo, $C'=C-e$ é um caminho Hamiltoniano em $G$.

Se existissem uma aresta $uv_{i}$ e uma aresta $v_{i-1}v$ para algum $2\leq i\leq n-2$, teríamos um ciclo hamiltoniano em $G$, formado pelo caminho de $u$ a $v_{i-1}$ através do caminho Hamiltoniano $C'$ e a aresta $v_{i}u$. Logo, cada vizinho de $u$ em $C'$ proíbe um vizinho de $v$, visto que se assim não fosse, formaríamos ciclos hamiltonianos em $G$. Assim, $v$ possui no máximo $n-(\lceil {\frac {n}{2}}\rceil +1)$ vizinhos, isto é, $n-\lceil {\frac {n}{2}}\rceil -1<\lceil {\frac {n}{2}}\rceil$, o que é absurdo. Portanto, $G$ não pode existir e o resultado vale.

---

Corolário do Teorema de Dirac: Seja $G$ simples conexo com ao menos 3 vértices e tal que $d(u)+d(v)\geq n$, para um par de vértices $u$ e $v$ não adjacentes. Então $G$ é Hamiltoniano se e somente se $G+uv$ é Hamiltoniano.

Prova (ida): Se $G$ é Hamiltoniano, então claramente $G+uv$ é Hamiltoniano.

Prova (volta): Se $G+uv$ é Hamiltoniano, temos que existe um caminho Hamiltoniano $P$ com extremidades $u$ e $v$ em $G$. Por argumentos análogos ao Teorema de Dirac, temos que deve existir uma aresta $uv_{i}$ e uma aresta $v_{i-1}v$, para algum $2\leq i\leq n-2$. Logo, $G$ é Hamiltoniano.