Grafos eulerianos e grafos hamiltonianos

Um caminho euleriano num grafo é um caminho simples que contém todas as arestas do grafo. Um circuito euleriano é um caminho euleriano fechado. Um grafo diz-se grafo euleriano se contém um circuito euleriano.

Historicamente, os caminhos eulerianos estão associados à génese da teoria de grafos, essencialmente à custa das pontes de Königsberg (actual Kalingrado, no enclave russo entre a Polónia e a Lituânia). A questão era saber se seria possível passar exactamente uma vez em cada ponte, voltando ao ponto de partida.

Em 1736, Leonhard Euler mostrou que tal não é possível. O multi-grafo associado ao problema é

$$\xymatrix{ & w \ar@{-}@/_/[ld]\ar@{-}[rd] &\\ u \ar@{-}@/_/[ru]\ar@{-}@/_/[rd] \ar@{-}[rr] &&v \\ &x \ar@{-}@/_/[lu] \ar@{-}[ru] &}$$

Teorema 7.1   Seja ${\cal{G}}=({\cal{V}}_{\cal{G}},{\cal{A}}_{\cal{G}})$ um (multi-)grafo. São equivalentes:

1. ${\cal{G}}$ é euleriano.
2. $deg(v)$ é par, para todo o $v\in {\cal{V}}_{\cal{G}}$.
3. ${\cal{A}}_{\cal{G}}$ é a união de ciclos disjuntos.

$(1)\Rightarrow (2)$. Seja $\gamma$ um circuito euleriano. Como passa por todas as arestas, então passa por todos os vértices. Para qualquer vértice $v$, $\gamma$ passa por $v$, e como não repete arestas, então o número de arestas que incidem em $v$ é par.

$(2)\Rightarrow (3)$. Suponhamos agora que $deg(v)$ é par. Como o grafo é conexo, então o grau de qualquer vértice é um par não nulo. Portanto, o grafo não é uma árvore, e portanto existe um ciclo $\gamma$ em ${\cal{G}}$. Defina-se o grafo ${\cal{G}}'$ como o grafo obtido de ${\cal{G}}$ removendo as arestas de $\gamma$. Note-se que os graus dos vértices de ${\cal{G}}'$ continuam a sere números pares. Se ${\cal{G}}'$ não tem arestas (o que correponde ao caso em que $\gamma$ contém todas as arestas de ${\cal{G}}$) então (3) está provado. Caso contrário, repete-se o algoritmo de remoção de arestas.

$(3)\Rightarrow (1)$. Seja $\gamma$ um ciclo da partição do conjunto das arestas. Se $\gamma$ é o único ciclo, então ${\cal{G}}$ é euleriano. Caso contrário, existe um outro ciclo $\gamma'$ com um vértice $v$ comum com $\gamma$ (recorde que o grafo é conexo). Considere a concatenação $\gamma \circ \gamma'$. Este caminho, iniciado (e terminado) em $v$ é um circuito. Repetindo o algoritmo, obtemos um circuito que contém todas as arestas, e logo o grafo é euleriano.

Como aplicação, o teorema anterior mostra que um grafo cúbico (e em particular o cubo e o grafo de Petersen) não é euleriano. O grafo

$$\xymatrix{ & u \ar@{-}[ld] \ar@{-}[ldd]\ar@{-}[rdd] \ar@{-}[rd] & \\ y \ar@{-}[d] \ar@{-}[rrd] && v\ar@{-}[d]\ar@{-}[lld]\\ x \ar@{-}[rr] && w}$$

também não é euleriano, já que o grau do vértice $y$ (e de $v$) não é par.

A demonstração do teorema anterior, por outro lado, fornece-nos uma construção de um circuito euleriano, no caso de grafo dado ter os vértices de grau par. Considere, como exemplo, o grafo $K_5$:

$$\xymatrix{ & u \ar@{-}[ld] \ar@{-}[ldd]\ar@{-}[rdd] \ar@{-}[rd] &... ...-}[d] \ar@{-}[rrd]\ar@{-}[rr] && v\ar@{-}[d]\ar@{-}[lld]\\ x \ar@{-}[rr] && w}$$

Os ciclos disjuntos (nas arestas) que formam o grafo são

$\xymatrix{ & u \ar@{-}[ld] \ar@{-}[ldd] & \\ y \ar@{-}[d] && \\ x && }$	$\xymatrix{ & u \ar@{-}[rdd] \ar@{-}[rd] & \\ && v\ar@{-}[d]\\ && w}$	$\xymatrix{ &&\\ y \ar@{-}[rrd]\ar@{-}[rr] && v\ar@{-}[lld]\\ x \ar@{-}[rr] && w}$
$\gamma_1=uxyu$	$\gamma_2=uwvu$	$\gamma_3=ywxvy$

Atentando, em primeiro lugar, nos ciclos $\gamma_1$ e $\gamma_2$, estes têm o vértice $u$ em comum. Seja $\gamma_4=\gamma_1 \circ \gamma_2$, que é um circuito:

$$\xymatrix{ & u \ar@{-}[ld] \ar@{-}[ldd]\ar@{-}[rdd] \ar@{-}[rd] & \\ y \ar@{-}[d] && v\ar@{-}[d]\\ x && w}$$

Este circuito tem, por exemplo, o vértice $y$ em comum com $\gamma_3$. Façamos então a concatenação, esgotando, portanto, as arestas disponíveis. Um circuito euleriano é, por exemplo, o que se inicia (e termina) em $u$, percorre $\gamma_4$ até encontrar $y$, faz um "desvio" percorrendo $\gamma_3$, para depois continuar o percurso em $\gamma_4$ regressando a $v$ . Ou seja, $uxywxvyuwvu$.

Um caminho hamiltoniano num grafo é um caminho elementar que contém todos os vértices do grafo. Um ciclo hamiltoniano é um ciclo que contém todos os vértices do grafo. Um grafos diz-se grafo hamiltoniano se contém um ciclo hamiltoniano.

É importante salientar que o problema de se saber se certo grafo hamiltoniano é NP-completo. Ou seja, e simplicando, é simples testar que um ciclo é hamiltoniano, mas o problema recíproco de se encontrar um ciclo hamiltoniano é difícil. Ou seja, não se encontrou, até à data, um algoritmo que resolva tal problema em tempo razoável (no tamanho do input). Existem, no entanto, condições necessárias e outras suficientes que permitem, em alguns casos, testar se o grafo é (ou não) hamiltoniano de uma forma fácil.

Se o grafo ${\cal{G}}$ é hamiltoniano então

# 1.

se $deg(v)=2$ então as arestas incidentes em $v$ estão em qualquer ciclo hamiltoniano;

# 2.

na construção de um ciclo hamiltoniano, nenhum ciclo se pode formar até se percorrerem os vértices todos;

# 3.

se na construção de um ciclo hamiltoniano 2 arestas que incidem em $v$ não podem ser eliminadas, então as restantes que incidem em $v$ podem-no.

Com base nestas regras, vamos mostrar que o seguinte grafo não é hamiltoniano:

$$\xymatrix{ a \ar@{-}[r]\ar@{-}[d] & b \ar@{-}[r]\ar@{-}[rd] & c \... ...d] & i \ar@{-}[r] & d \ar@{-}[d]\\ g \ar@{-}[r] & f \ar@{-}[ru]\ar@{-}[r] & e}$$

Suponha que o grafo é hamiltoniano. Como os vértices $a,c,e,g$ têm grau dois, as arestas

$$ab,ah,cb,cd,ed,eg,gf,gh$$

estão em qualquer ciclo hamiltoniano, pela regra 1. Aplicando a regra 3 aos vértices $d$ e $h$, as arestas $hb,hi,hf,db,di,df$ podem ser eliminadas. Mas ficamos então com o ciclo $abcdefgha$ que não passa por $i$, o que viola a regra 2.

Teorema 7.2 (Ore, 1960)   Se um $n-$grafo simples com 3 ou mais vértices satisfaz $deg(v)+deg(w)\ge n$ para quaisquer vértices não vizinhos um do outro, então o grafo é hamiltoniano.

Corolário 7.3 (Dirac, 1952)   Seja ${\cal{G}}$ um grafo simples com 3 ou mais vértices, vértices esses que têm grau não inferior à metade do número de vértices. Então ${\cal{G}}$ é hamiltoniano.

Com base nestes resultados, segue que $K_4,K_5,K_{3,3}$ são hamiltonianos. O grafo $W_5$, apresentado em baixo, é também hamiltoniano:

$$\xymatrix{ & \bullet \ar@{-}@/^.4cm/[rd]\ar@{-}[d] &\\ \bullet\a... ...[r] & \bullet\ar@{-}@/^.4cm/[ld]\\ & \bullet \ar@{-}@/^.4cm/[lu]\ar@{-}[u] & }$$