Projeto e Análise de Algoritmos I

Aula 24 - Grafos Eulerianos e Hamiltonianos. Caixeiro Viajante.

Lucas Nunes Alegre

Universidade Federal do Rio Grande do Sul
Instituto de Informática
Departamento de Informática Teórica

Estes slides utilizam conteúdo adaptado da bibliografia da disciplina e também de notas de aula e slides prévios dos professores Bruno Grisci, Rodrigo Machado e André Grahl.

Grafos Eulerianos

Problema das Pontes de Königsberg

Considerado o primeiro problema de teoria dos grafos.
Resolvido em 1736 por Leonhard Euler.

Problema: Dada a disposição das pontes da cidade, há algum caminho que passe por cada uma delas uma única vez?

Problema das Pontes de Königsberg

Tipos de Passeio

Definição: Um passeio p(x,y) é fechado quando x = y.

Definição: Uma trilha (trail) é um passeio sem arestas repetidas.

Definição: Um caminho (path) é uma trilha p(x,y) sem nodos repetidos (com exceção de x e y, que podem ser iguais).

Definição: Nomes especiais para alguns passeios:

circuito (circuit): trilha fechada

ciclo (cycle): caminho fechado

laço (loop): caminho fechado de tamanho 1

%%{init: {'themeVariables': { 'fontSize': '26px' }}}%%
graph TD
  A([Passeio])
  B([Trilha])
  C(["Passeio<br>Fechado"])
  D([Caminho])
  E([Circuito])
  F([Ciclo])
  G([Laço])

  A --> B
  A --> C
  B --> D
  B --> E
  C --> E
  D --> F
  E --> F
  F --> G

  classDef default fill:#23373b,color:#fafafa,stroke:none,font-size:26px;

Circuitos e Grafos Eulerianos

Definição: Uma trilha/circuito é euleriana(o) sss passa por todas as arestas do grafo.

Definição: Um grafo é semi-euleriano sss possui uma trilha euleriana ou é nulo (sem arestas).

Definição: Um grafo é euleriano sss possui um circuito euleriano ou é nulo (sem arestas).

Trilha euleriana: d \to c \to a \to b \to c

Circuito euleriano: A \to B \to C \to D \to E \to C \to A

Circuitos e Grafos Eulerianos: Exercício

Exercício: Classifique os seguintes grafos de acordo com a existência ou não de trilhas/circuitos eulerianos:

Caracterização de Grafos Eulerianos

Lema: Dado um grafo simples finito G, se deg(v) \geq 2 para todo v \in V, então G é cíclico.

Demonstração: Considere um caminho c em G que seja:

aberto: os pontos extremos a e b são distintos;
maximal: não está contido em nenhum outro caminho aberto.

c(a,b) =

Como G é finito, caminhos maximais existem em cada componente conexo.
Como deg(a) \geq 2, \textcolor{#eb811b}{a} deve estar conectado a no mínimo mais um nó x (além do seu vizinho em c).
Se \textcolor{#c62828}{x \notin c}: teríamos um caminho maior c'(x,b) \Rightarrow contradição com o fato de c ser maximal!
Portanto, a deve estar conectado a algum \textcolor{#2e7d32}{x \in c}, formando um ciclo. \blacksquare

Caracterização de Grafos Eulerianos (Cont.)

Definição: Um componente conexo é não-trivial sss possui ao menos uma aresta.

Teorema: Um grafo simples finito G=(V,E) é euleriano sss

possui no máximo um componente conexo não-trivial, e

os graus de todos os nós são pares.

Graus pares e um único componente não-trivial (o vértice isolado é trivial) \Rightarrow euleriano

Graus pares, mas dois componentes não-triviais \Rightarrow não é euleriano

Caracterização de Grafos Eulerianos: (\Rightarrow)

Demonstração: (\Rightarrow) G possui um circuito euleriano, que chamaremos c.

Um dado nodo n pode ocorrer ou não em c.
\textcolor{#eb811b}{n \notin c}: não há arestas incidentes \Rightarrow grau 0 (par).
n \in c: cada ocorrência do nodo soma 2 ao grau (uma aresta de chegada e uma de saída, distintas, pois c é euleriano).
Como o circuito contém todas as arestas, não há outras contribuições para o grau.
Logo, o grau de n é par: 2 vezes o número de ocorrências de n em c.

c = A \to B \to \textcolor{#c62828}{C} \to D \to E \to \textcolor{#c62828}{C} \to A

C ocorre 2 vezes: arestas \textcolor{#2e7d32}{2, 3} e \textcolor{#eb811b}{5, 6} \Rightarrow deg(C) = 2 \cdot 2 = 4

Obs: Assumir que há mais de um componente conexo não-trivial gera contradição com o fato de haver um circuito euleriano: não seria possível haver caminho entre dois componentes conexos distintos.

Caracterização de Grafos Eulerianos: (\Leftarrow)

Demonstração: (\Leftarrow) Por indução no número de arestas |E|.

Caso base: |E| = 0. O grafo é euleriano por definição.
Passo indutivo: como há nodos de grau maior que zero, existe ao menos um componente conexo não-trivial.
Nele, todos os graus são pares e > 0 (logo \geq 2). Pelo lema anterior, existe um subgrafo ciclo \textcolor{#1565c0}{C=(V_C,E_C)}.
O grafo \textcolor{#c62828}{G'} = G - \textcolor{#1565c0}{E_C} possui menos arestas e todos os graus continuam pares (cada nodo de \textcolor{#1565c0}{C} perde exatamente 2).
Cada componente conexo não-trivial de \textcolor{#c62828}{G'} possui um vértice em comum com \textcolor{#1565c0}{C}.
Hipótese indutiva: cada componente conexo de \textcolor{#c62828}{G'} ou é nulo, ou possui circuito euleriano.
Resultado: percorre-se \textcolor{#1565c0}{C} e, ao passar por um nodo comum, entra-se no circuito euleriano daquele componente de \textcolor{#c62828}{G'}.

Corolário: Todo grafo euleriano pode ser decomposto em ciclos disjuntos nas arestas (podem compartilhar nodos).

Algoritmo de Hierholzer (1873)

Encontrando o circuito euleriano de um grafo euleriano:

\begin{algorithmic} \Procedure{Hierholzer}{$G,\ v_0$} \State \textbf{stack} $St$ \State coloque o vértice inicial $v_0$ em $St$ \While{$St \neq \emptyset$} \State seja $V$ o valor no topo de $St$ \If{$degree(V) = 0$} \State adicione $V$ à resposta \State remova $V$ do topo de $St$ \Else \State encontre uma aresta que sai de $V$ \State remova essa aresta do grafo \State coloque o segundo extremo dessa aresta em $St$ \EndIf \EndWhile \EndProcedure \end{algorithmic}

Qual a complexidade? O(|E|)

Algoritmo de Hierholzer (1873) - Exemplo

Grafo (todos os graus pares):

■ topo da pilha \quad - - - aresta removida

\deg(C)=4; \deg(A)=\deg(B)=\deg(D)=\deg(E)=2

Saída obtida: [A,\,C,\,E,\,D,\,C,\,B,\,A]

Circuito (saída ao contrário): A\!\to\!B\!\to\!C\!\to\!D\!\to\!E\!\to\!C\!\to\!A

#	Pilha St (base\totopo)	Operação
0	[A]	início em A
1	[A,B]	remove e_1, empilha B
2	[A,B,C]	remove e_2, empilha C
3	[A,B,C,A]	remove e_3, empilha A
4	[A,B,C]	\deg(A){=}0: adiciona A à saída
5	[A,B,C,D]	remove e_4, empilha D
6	[A,B,C,D,E]	remove e_5, empilha E
7	[A,B,C,D,E,C]	remove e_6, empilha C
8	[A,B,C,D,E]	\deg(C){=}0: adiciona C à saída
9	[A,B,C,D]	\deg(E){=}0: adiciona E à saída
10	[A,B,C]	\deg(D){=}0: adiciona D à saída
11	[A,B]	\deg(C){=}0: adiciona C à saída
12	[A]	\deg(B){=}0: adiciona B à saída
13	[\,]	\deg(A){=}0: adiciona A à saída

As Pontes de Königsberg

https://www.google.com/maps/place/Kaliningrad,+Kaliningrad+Oblast,+Russia/@54.7057454,20.5102359,16z

Dígrafos Eulerianos

O Problema do Carteiro Chinês

Um carteiro precisa percorrer todas as ruas do seu bairro e voltar ao ponto de partida, andando o mínimo possível (Kwan Mei-Ko, 1960).

Problema: Dado um grafo conexo G=(V,E) com pesos positivos nas arestas, encontrar um passeio fechado de custo mínimo que passe por todas as arestas de G pelo menos uma vez.

Se G é euleriano, basta um circuito euleriano; senão, algumas ruas precisam ser repetidas.
Pode ser resolvido em tempo polinomial (Edmonds e Johnson, 1973).

Cidade Baixa, Porto Alegre: cruzamentos são vértices e trechos de rua são arestas. Mapa: © colaboradores do OpenStreetMap.

Wikipedia: Problema do carteiro chinês

Grafos Hamiltonianos

Problema do Ciclo Hamiltoniano

Problema: Achar um caminho fechado nos vértices de um dodecaedro (poliedro regular de 12 faces) passando por cada vértice (ponta) uma única vez.

Proposto por Sir William Rowan Hamilton em 1857 (mais conhecido pelo desenvolvimento dos quatérnios e contribuições para a mecânica analítica).
Foi produzido um jogo de tabuleiro baseado neste problema (Icosian game).

Imagens: http://puzzlemuseum.com/month/picm02/200207icosian.htm, http://en.wikipedia.org/wiki/Dodecahedron

Problema do Ciclo Hamiltoniano: Solução

No grafo do dodecaedro (visão planar), queremos um ciclo que passe uma única vez por cada um dos 20 vértices.

Um ciclo hamiltoniano (em verde), começando e terminando no vértice laranja.

Ciclos e Grafos Hamiltonianos

Definição: Um caminho/ciclo é hamiltoniano sss passa por todos os vértices do grafo.

Definição: Um grafo é semi-hamiltoniano sss possui um caminho hamiltoniano ou possui 1 vértice.

Definição: Um grafo é hamiltoniano sss possui um ciclo hamiltoniano ou possui 1 vértice.

Caminho hamiltoniano (ordem de visita nos vértices), mas nenhum ciclo.

Ciclo hamiltoniano (ordem de visita nos vértices).

Ciclos e Grafos Hamiltonianos: Exercício

Exercício: Determine a classificação dos seguintes grafos de acordo com a existência ou não de ciclos/caminhos hamiltonianos.

Caracterização de Grafos Hamiltonianos

Grafos eulerianos possuem uma caracterização precisa em termos de propriedades de grau dos vértices.
Podemos dizer se um grafo é euleriano sem precisar construir o circuito euleriano correspondente.
No caso de grafos hamiltonianos, não se sabe até o momento um conjunto de condições simultaneamente suficientes e necessárias que os caracterizem completamente.

Exemplo: Condições necessárias para um grafo simples G ser hamiltoniano:

\delta(G) \geq 2, onde \delta(G) é o grau mínimo de G

G é conexo

Notem que elas não são suficientes, como mostra o grafo ao lado (do exercício anterior): todo ciclo hamiltoniano teria que passar duas vezes pelo vértice em vermelho.

Condição Suficiente para Grafos Hamiltonianos

Ideia: se o grafo contém arestas suficientes, ele certamente é hamiltoniano.

Exemplo: Grafos completos K_3, K_4, K_5, \ldots (ciclo hamiltoniano em verde)

À medida que aumenta o valor \delta(G) (grau mínimo do grafo), existem mais interconexões entre nodos arbitrários.

Pergunta: Qual o menor \delta(G) de um grafo para que tenhamos certeza que ele é hamiltoniano?

Teorema de Dirac

Teorema: (Dirac, 1952) se G=(V,E) é um grafo simples finito onde |V| \geq 3 e \delta(G) \geq |V|/2, então G é hamiltoniano.

Demonstração: Baseada em grafos não-hamiltonianos maximais e contradição.

Definição: um grafo G=(V,E) é não-hamiltoniano maximal sss

G não é hamiltoniano, e

para qualquer e \notin E, temos que (V,E \cup \{e\}) é hamiltoniano.

Teorema de Dirac: Grafos Não-Hamiltonianos Maximais

Intuição:

Um grafo não-hamiltoniano maximal possui o maior número possível de arestas sem ser hamiltoniano.
Se colocarmos qualquer aresta a mais, então ele se torna hamiltoniano.
Note que ele deve ser certamente semi-hamiltoniano (para poder fechar o ciclo com a aresta extra).

Exemplo: Com quatro vértices, temos o seguinte grafo não-hamiltoniano maximal (a menos de isomorfismo):

G + {b, d}: hamiltoniano

G + {a, d}: hamiltoniano

Teorema de Dirac (2)

Vamos mostrar que não existe grafo não-hamiltoniano maximal G=(V,E) com \delta(G) = n/2, onde n = |V|.
Para isso, assumimos que existe, e vamos obter uma contradição.
Do grafo não-hamiltoniano maximal G, tomamos um caminho hamiltoniano aberto \textcolor{#1565c0}{c} (e portanto, possuindo n vértices).

c =

Se algum vizinho de \textcolor{#eb811b}{a} sucede um vizinho de \textcolor{#eb811b}{b} no caminho c…
… certamente há um ciclo hamiltoniano (desviando da aresta central \{v_i, v_{i+1}\}) \Rightarrow contradição com o fato de G ser não-hamiltoniano!
Basta mostrar que com \delta(G) = n/2 a situação acima sempre ocorrerá.

Teorema de Dirac (3)

V_a: conjunto de posições dos antecessores dos vizinhos de a (de 1 a n-1).
V_b: conjunto de posições dos vizinhos de b (de 1 a n-1).
Suponha \delta(G) = n/2: tanto a quanto b possuem n/2 vizinhos, todos no caminho c (pois c é hamiltoniano). Consequentemente, |V_a| = |V_b| = n/2.
Somando a cardinalidade dos dois conjuntos: n = |V_a| + |V_b| = |V_a \cup V_b| + |V_a \cap V_b|
Como o índice n não ocorre nem em V_a nem em V_b, certamente |V_a \cup V_b| < n. Portanto, |V_a \cap V_b| \geq 1.
Há no mínimo um índice comum entre antecessores de vizinhos de a e vizinhos de b \Rightarrow a situação do slide anterior ocorre \Rightarrow ciclo hamiltoniano em G: contradição!
Portanto, não é possível haver um grafo maximal não-hamiltoniano com \delta(G) = |V|/2. O argumento vale para qualquer \delta(G) maior que n/2. \blacksquare

Teorema de Dirac (3): Visualização

Exemplo: n = 8 e \delta(G) = 4, com o caminho hamiltoniano a = v_1, v_2, \ldots, v_8 = b (só as arestas de a e b são mostradas).

Vizinhos de a: v_2, v_4, v_5, v_7 \Rightarrow \textcolor{#1565c0}{V_a = \{1, 3, 4, 6\}} (antecessores).
Vizinhos de b: v_2, v_5, v_6, v_7 \Rightarrow \textcolor{#c62828}{V_b = \{2, 5, 6, 7\}}.
|V_a| + |V_b| = 8, mas só há 7 posições possíveis \Rightarrow \textcolor{#2e7d32}{V_a \cap V_b = \{6\}}: a é vizinho de v_7, que sucede v_6, vizinho de b.
Ciclo hamiltoniano: a \to v_2 \to \cdots \to v_6 \to b \to v_7 \to a.

Teorema de Dirac (4)

Exemplo: o grafo abaixo tem 6 nodos e grau mínimo 3.

Graus: \delta(G) = 3 \geq 6/2. Portanto, pelo teorema de Dirac, é hamiltoniano.
De fato: um ciclo hamiltoniano.
Existem outros teoremas que garantem que certos tipos de grafos são hamiltonianos.
Contudo, nenhum deles engloba todos os possíveis grafos hamiltonianos.

Problema do Caixeiro Viajante

Intuição:

Um caixeiro viajante parte de uma cidade e quer vender seus produtos em todas as demais cidades de um determinado estado, voltando para a cidade de origem.
Ele não quer passar mais de uma vez por cada cidade.
Além disso, ele gostaria de andar o mínimo possível.
A resposta do problema é a rota que o caixeiro viajante deve utilizar para alcançar seus objetivos.

Problema: Dado um grafo com pesos nas arestas (não-negativos), determinar um ciclo hamiltoniano de peso mínimo.

Exercício: Apresente um ciclo hamiltoniano de menor peso para o grafo ao lado.

Problema do Caixeiro Viajante

Para um grafo completo K_n, há \frac{n!}{2n} ciclos hamiltonianos distintos.
No exemplo anterior, temos que averiguar o peso de \frac{5!}{2 \cdot 5} = 12 ciclos distintos.
Para um grafo completo com 50 vértices, número de caminhos distintos: 304140932017133780436126081660647688443776415689605120000000000

Complexidade:

Problema de decisão (há ciclo hamiltoniano de peso menor que x?): NP-completo
Problema de otimização (encontre o ciclo hamiltoniano de menor peso): NP-difícil
É comum o emprego de heurísticas eficientes para se chegar a resultados aproximados (sub-ótimos).

Problema do Caixeiro Viajante

Exemplo:

Ciclos e respectivos pesos (calculados por força bruta):

("abedc",9)      ("acdbe",10)
("abdce",11)     ("abdec",11)
("abcde",13)     ("acbde",14)
("abecd",17)     ("acebd",18)
("acbed",20)     ("adcbe",20)
("abced",21)     ("adbce",22)

São 12 ciclos distintos para n = 5.
Ótimo: \textcolor{#2e7d32}{a \to b \to e \to d \to c \to a}, com peso \textcolor{#2e7d32}{9}.

Problema do Caixeiro Viajante

Algoritmos para o Problema do Caixeiro Viajante

Exatos (exponenciais no pior caso)

Held–Karp (1962): programação dinâmica em O(n^2 2^n), ainda o melhor limite conhecido para o caso geral.
Dantzig, Fulkerson e Johnson (1954): programação linear com planos de corte; resolveram 49 cidades.
Concorde: branch-and-cut. Recordes com prova de otimalidade: 85.900 pontos e 81.998 bares na Coreia.

Heurísticas (sem garantia, excelentes na prática)

2-opt e Lin–Kernighan (1973): busca local trocando arestas; a variante LKH (Helsgaun) está entre as melhores heurísticas conhecidas.
Implementações em Python (Peter Norvig).

Aproximados (TSP métrico: vale a desigualdade triangular)

Um algoritmo tem fator \alpha se sempre devolve um ciclo de custo {\leq \alpha \cdot \mathrm{OPT}}, onde \mathrm{OPT} é o custo do ciclo ótimo.

Árvore geradora mínima + percurso em pré-ordem: fator 2 (Cormen et al., Seção 35.2).
Christofides (1976) e Serdyukov (1978): fator 3/2.
Karlin, Klein e Oveis Gharan (2021): fator {3/2 - 10^{-36}}, a primeira melhora desde 1976.
Arora (1998) e Mitchell (1999): fator 1 + \varepsilon para qualquer \varepsilon > 0 no TSP euclidiano (PTAS).

Limites

Sem desigualdade triangular, não existe aproximação com fator constante, a menos que {P = NP} (Sahni e Gonzalez, 1976).
TSP métrico: a menos que {P = NP}, nenhum algoritmo polinomial tem fator menor que {123/122 \approx 1{,}008}, ou seja, nenhum garante ciclos menos de 0{,}8\% acima do ótimo (Karpinski, Lampis e Schmied, 2015).