Grafos de Hamilton: Identificação e cálculo de circuitos

Explicação

Um circuito de Hamilton é um circuito que passa por todos os vértices apenas uma vez. Um grafo é hamiltoniano se admite um circuito hamiltoniano.

Exemplo

Será que o grafo seguinte é um grafo hamiltoniano?

Matemática Aplicada às Ciências Sociais; Modelos de grafos; 11º Ano; Grafos de Hamilton: Identificação e cálculo de circuitos

O grafo acima é um grafo de ordem $6$ . Nota que $\text{A}\ a_2\ \text{B}\ a_5\ \text{D}\ a_8\ \text{F}\ a_{10}\ \text{E}\ a_6\ \text{C}\ a_1 \ \text{A}$ é um circuito hamiltoniano, pelo que o grafo é hamiltoniano também.

Teoremas de Ore e de Dirac

Existem dois teoremas que permitem determinar se alguns grafos contêm circuitos de Hamilton. Estes teoremas dão-te condições suficientes para tal ocorrer, mas não são condições necessárias.

Teorema de Dirac

Se $G$ for um grafo conexo e simples de ordem $n\geq 3$ , $G$ é hamiltoniano se o grau de cada vértice for maior ou igual a $\frac{n}{2}$ .

Exemplo

Matemática Aplicada às Ciências Sociais; Modelos de grafos; 11º Ano; Grafos de Hamilton: Identificação e cálculo de circuitos

O grafo acima é de ordem $5$ , pelo que metade da sua ordem é $\dfrac{5}{2}$ . O grau do vértice $\text{D}$ é $4$ e dos restantes é $3$ e como $4>\dfrac{5}{2}$ e $3>\dfrac{5}{2}$ , o teorema verifica-se, sendo $\text{ACDEBA}$ um possível circuito hamiltoniano.

Teorema de Ore

Considerando um grafo $G$ conexo e simples de ordem $n\geq 3$ , se a soma dos graus de cada par de vértices não adjacentes é maior ou igual a $n$ , então $G$ tem um circuito de Hamilton.

Exemplo

Matemática Aplicada às Ciências Sociais; Modelos de grafos; 11º Ano; Grafos de Hamilton: Identificação e cálculo de circuitos

O grafo acima é de ordem $7$ . Como os vértices $\text{I}$ e $\text{J}$ são de grau $3$ e os restantes de grau $4$ , a soma dos graus de qualquer par de vértices não adjacentes é $7$ ou $8$ . Como $7=7$ e $8>7$ , verifica-se pelo teorema de Ore que o grafo admite um circuito de Hamilton, como, por exemplo, $\text{FGKIJHLF}$ . É, então, um grafo hamiltoniano.

Circuitos de Hamilton em grafos-grelha

Considerando um grafo-grelha com $m$ linhas e $n$ colunas, sabe-se que o grafo tem circuitos hamiltonianos se $m$ e $n$ forem pares, ou se apenas um deles for ímpar. Se ambos forem ímpares, não existem circuitos hamiltonianos.

Exemplo

Matemática Aplicada às Ciências Sociais; Modelos de grafos; 11º Ano; Grafos de Hamilton: Identificação e cálculo de circuitos

Matemática Aplicada às Ciências Sociais; Modelos de grafos; 11º Ano; Grafos de Hamilton: Identificação e cálculo de circuitos

Matemática Aplicada às Ciências Sociais; Modelos de grafos; 11º Ano; Grafos de Hamilton: Identificação e cálculo de circuitos

Na primeira imagem tens um grafo de $4$ linhas por $4$ colunas, enquanto na segunda tens um de $4$ linhas por $3$ colunas. Em ambos estão representados a cinzento circuitos hamiltonianos.

Na última imagem observas um grafo de $3$ linhas por $3$ colunas, pelo que este grafo não é hamiltoniano.

Circuitos de Hamilton em grafos completos

Grafos completos têm sempre circuitos de Hamilton. De facto, pode provar-se que o grafo completo $K_n$ tem $(n-1)!$ circuitos hamiltonianos.

A dimensão de um grafo é o número de arestas que possui. A dimensão de $K_n$ é calculada através de $\dfrac{n(n-1)}{2}$ .

Nota: $n!=n\times(n-1)\times(n-2)\times...\times3\times2\times1$

Exemplo

Matemática Aplicada às Ciências Sociais; Modelos de grafos; 11º Ano; Grafos de Hamilton: Identificação e cálculo de circuitos

O grafo acima é um grafo completo de ordem $5$ , podendo ser representado por $K_5$ .

Assim, sabe-se que tem $4!=4\times3\times2\times1=24$ circuitos hamiltonianos e $\dfrac{5\times4}{2}=10$ arestas.