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)$ :

$ω (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 $ω (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 $ω (G - S)$ é no máximo $ω (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 $δ (G) \geq ⌈ \frac{n}{2} ⌉$ . Então $G$ é Hamiltoniano.

Prova: Seja $G$ simples, tal que $V (G) \geq 3$ e $δ (G) \geq ⌈ \frac{n}{2} ⌉$ 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 = u v$ 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 = u v$ adicionada, logo, $C^{'} = C - e$ é um caminho Hamiltoniano em $G$ .

Se existissem uma aresta $u v_{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 - (⌈ \frac{n}{2} ⌉ + 1)$ vizinhos, isto é, $n - ⌈ \frac{n}{2} ⌉ - 1 < ⌈ \frac{n}{2} ⌉$ , 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 + u v$ é Hamiltoniano.

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

Prova (volta): Se $G + u v$ é 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 $u v_{i}$ e uma aresta $v_{i - 1} v$ , para algum $2 \leq i \leq n - 2$ . Logo, $G$ é Hamiltoniano.