Algoritmos em grafos

Algoritmos em Grafos¶

5.1 Caminhamento em largura (Breadth-first search - BFS)¶

Caminhamento em largura geralmente é usado para encontrar distâncias mínimas de um vértice a todos os outros em relação ao nuúmero de arestas.

BFS(G, s)
// Arguments:
// G: Graph with vertices V and adjacency list AdjList
// s: Source vertex from which to start the search

for each vertex u in G.V except s
   u.pi = NIL
   u.d = infinity
   u.color = WHITE
s.color = GRAY
s.d = 0
s.pi = NIL
Q = queue containing s
while Q is not empty
   u = dequeue(Q)
   for each v in G.AdjList[u]
      if v.color == WHITE
         v.color = GRAY
         v.pi = u
         v.d = u.d + 1
         enqueue(Q, v)
   u.color = BLACK
            v.d = u.d + 1
            enqueue(Q, v)
      u.color = BLACK    // BLACK: fully explored

5.2 Caminhamento em profundidade (Depth-first search - DFS)¶

DFS(G)
 // Arguments:
 // G: Graph with vertices V and adjacency list AdjList

 for each vertex u in G.V
    u.color = WHITE
    u.pi = NIL
 time = 0
 for each vertex u in G.V
    if u.color == WHITE
       DFS-VISIT(G, u)

DFS-VISIT(G, u)
 time = time + 1
 u.d = time
 u.color = GRAY
 for each v in G.AdjList[u]
    if v.color == WHITE
       v.pi = u
       DFS-VISIT(G, v)
 u.color = BLACK
 time = time + 1
 u.f = time

• O intervalo $[u.d, u.f ]$ está totalmente contido dentro do intervalo $[v.d, v.f]$ sse $u$ é descendente de $v$ em alguma a´rvore na floresta de predecessores do DFS (ou vice versa)
  

• O intervalo $[u.d, u.f]$ é totalmente disjunto de $[v.d, v.f]$ sse os dois vértices pertencem a árvores diferentes na floresta de predecessores do DFS.
  

• Não é possível que intervalos tenham sobreposição mas que um não esteja totalmente contido dentro do outro: se isso pudesse acontecer, teríamos que o vértice ancestral seria terminado antes do seu descendente, o que contraria a definição de caminhamento em profundidade já que vértices ancestrais só terminam quando todos os seus descendentes tenham terminado.

5.2.1 Classificação de arestas em DFS¶

Se considerarmos o caso mais geral com grafos direcionados, podemos classificar as arestas de um grafo em quatro categorias:

1. Arestas da árvore (tree edges) são aquelas que aparecem na floresta de predecessores – aquelas que são selecionadas para visitar novos vértices;
   

2. Arestas de volta (back edges) são aquelas que vão de um descendente para algum de seus ancestrais na árvore DFS;
   

3. Arestas avançadas (forward edges) são aquelas que vão de um vértice até algum de seus descendentes na árvore DFS;
   

4. Arestas de cruzamento (cross edges) são as outras arestas: pode acontecer entre vértices de diferentes árvores da floresta ou mesmo entre vértices da mesma árvore que não compartilham relação ancestral/descendente (irmãos, por exemplo);

Toda vez que visitamos um novo vértice v no DFS, digamos através da aresta $(u, v)$, temos alguma informação sobre qual tipo de aresta ela será. Se a cor de v for $WHITE$, então a aresta $(u, v)$ é uma aresta da árvore (tree edge). Se a cor do vértice $v$ for $GRAY$ , então a aresta $(u, v)$ é de volta (back). Se a cor de $v$ for $BLACK$, então a aresta pode ser avançada (forward) ou de cruzamento (cross). Podemos tirar essa última dúvida se a aresta é avançada ou de cruzamento ao observar os tempos de cada aresta: se além de ser $BLACK$, o intervalo de u for disjunto do intervalo de v então temos uma aresta de cruzamento sem relação ancestral/descendente; caso contrário, se os intervalos estiverem contido um dentro do outro, temos uma aresta avançada, já que a sobreposição indica ancestralidade (pela parentização).

5.2.2 Ordenação topológica¶

A ideia é que vértices que terminam primeiro devem ser posicionados depois de todos os seus ancestrais na ordenação topológica.

Topological-Sort(G)
 // G: Grafo direcionado acíclico com vértices V e lista de adjacência AdjList

 chame DFS(G), registrando os tempos de término para cada vértice
 à medida que cada vértice termina, insira-o no início de uma lista ligada
 retorne a lista ligada de vértices

5.2.3 Encontrando componentes fortemente conectados¶

A ideia aqui é que ao executar o DFS em $G^T$ , sempre visitamos primeiro aqueles vértices de maior tempo de término em $G$, ou seja, aqueles vértices que não possuem aresta para outros vértices posicionados antes na ordem topológica. Dessa forma, toda vez que um vértice branco é encontrado, podemos ter certeza de que ele pertence à componente atual e toda vez que encontramos vértices já terminados, sabemos se tratar de vértices cuja componente já determinamos em uma visita anterior.

STRONGLY-CONNECTED-COMPONENTS(G)
// G: Grafo direcionado com vértices V e lista de adjacência AdjList

1. chame DFS(G) para determinar os tempos de término de cada vértice do grafo
2. construa G^T, que representa G com suas arestas invertidas
3. chame DFS(G^T), visitando primeiro os vértices com maior tempo de término (passo 1)
4. cada árvore da floresta visitada pelo último caminhamento representa um componente fortemente conectado do grafo original

5.3 Árvores geradoras de custo mínimo¶

5.3.1 Algoritmo de Prim¶

Fazemos $|V|$ operações de EXTRACT-MIN, uma para cada vértice, totalizando $O(V \;log \;V )$. Além disso, no pior caso, as chaves dos vértices são atualizadas $O(E)$ vezes, já que fazemos isso para as listas de adjacências do grafo. Como cada operação DECREASE-KEY custa $O(log \;V )$, temos o total de $O(V \;log \;V + E \;log \;V ) = O(E \;log \;V )$. Usando Fibonacci heaps, podemos melhorar esse custo assintótico para $O(E + V \;log \;V )$: isso acontece porque nessa estrutura, o custo amortizado de $V$ operações EXTRACT-MIN continua sendo $O(log \;V )$, mas o custo amortizado de $O(E)$ operações DECREASE-KEY fica reduzido para $O(1)$ (ao invés de $O(log \;V )$ no heap tradicional).

MST-PRIM(G(V, E), w, r)
// Arguments:
// G(V, E): Graph with vertices V and edges E
// w: edge weight function
// r: starting vertex

1. for each u in V
2.     u.pi = NIL
3.     u.key = ∞
4. r.key = 0
5. Q = BUILD-HEAP(V) // priority heap by u.key
6. while Q ≠ empty
7.     u = EXTRACT-MIN(Q)
8.     for each v in G.AdjList[u]
9.         if v ∈ Q and w(u, v) < v.key
10.            v.key = w(u, v) // decrease-key
11.            v.pi = u
11.            v.pi ← u

5.3.2 Algoritmo de Kruskal¶

O algoritmo faz $V$ operações MAKE-SET e $E$ operações FIND-SET/UNION. O custo dessas operações usando uma estrutura de dados para union/find é uma função que cresce bem lentamente e é limitada superiormente por $O(log \;V )$. Portanto, o custo total do algoritmo é $O((V + E) log \;V )$. Mas como em um grafo conectado temos $E ≥ V − 1$, totalizando $O(E \;log \;V )$.

***## 5.4 Propriedades de caminhos mínimos

• Desigualdade triangular:
  $δ(s, v) ≤ δ(s, u) + w(u, v)$
  O menor caminho entre $s$ e $v$ não pode ser maior do que o menor caminho entre $s$ e $u$ mais o custo da aresta $(u, v)$, senão teríamos um caminho de custo menor para $v$ (contradição).
  

• Propriedade do limite superior:
  É sempre verdade que a estimativa de menor caminho para $v$, $v.d$, é sempre maior do que o menor caminho real até $v$:
  $δ(s, v) ≤ v.d$.
  

• Propriedade do não-caminho:
  Se não existir caminho entre dois vértices (grafo orientado), temos que:
  $δ(s, v) = ∞$.
  

• Propriedade da convergência:
  Seja um caminho $s ⇝ u → v$, se relaxamos a aresta $(u, v)$ depois de já termos encontrado o caminho mínimo para $u$ (isto é, $u.d = δ(s, u)$), então:
  $v.d = δ(s, v)$
  E o mais importante, essa estimativa ótima nunca mais será alterada.
  

• Propriedade do relaxamento de um caminho:
  Seja um caminho mínimo $s ⇝ v$, se relaxamos as arestas na ordem desse caminho, então a estimativa do menor caminho para $v$ se tornará o menor caminho real:
  $v.d = δ(s, v)$.
  

• Propriedade do predecessor:
  Ao computar todas as estimativas para o menor caminho, $v.d = δ(s, v)$, teremos uma árvore de caminhos mínimos cuja raiz é $s$.

***## 5.5 Caminhos mínimos a partir de uma única fonte

5.5.1 Algoritmo de Bellman-Ford¶

$\begin{array}{ll} \text{\footnotesize RELAX}(u, v, w) \\ 1.\ \quad \text{if } v.d > u.d + w(u, v) \\ 2.\ \quad \quad v.d \gets u.d + w(u, v) \\ 3.\ \quad \quad v.\pi \gets u \\ \end{array}$
$\begin{array}{ll} \text{\footnotesize BELLMAN-FORD}(G(V, E), w, s) \\ 1.\ \quad \text{inicialize todos os predecessores dos vértices para } \textit{NIL} \\ 2.\ \quad \text{inicialize todas as estimativas dos vértices para } \infty \\ 3.\ \quad s.d \gets 0 \\ 4.\ \quad \text{for } i \gets 1 \text{ to } |V| - 1 \\ 5.\ \quad \quad \text{for } (u, v) \in E \\ 6.\ \quad \quad \quad \text{\footnotesize RELAX}(u, v, w) \\ 7.\ \quad \text{for } (u, v) \in E \\ 8.\ \quad \quad \text{if } v.d > u.d + w(u, v) \\ 9.\ \quad \quad \quad \text{return false} \ \langle \langle \text{existe ciclo negativo} \rangle \rangle \\ 10.\ \quad \text{return true} \\ \end{array}$

5.5.2 Algoritmo de Dijkstra¶

Este algoritmo utiliza uma escolha gulosa de sempre escolher para alcançar em seguida o vértice não alcançado que tenha a menor estimativa de distância até o momento. A inteligência do algoritmo vem do fato de que ao se alcançar um novo vértice, temos a oportunidade de melhorar a estimativa de distância de todos aqueles vértices não alcançados e que sejam adjacentes ao novo vértice.

O algoritmo faz $|V|$ operações EXTRACT-MIN e faz $O(|E|)$ operações DECREASE-KEY (que acontece quando relaxamos uma aresta e diminuímos a prioridade de um vértice). Essas duas operações podem ser implementadas com complexidade $O(log |V |)$ em um heap binário mínimo, totalizando $O((V + E) log \;V )$, ou $O(E \;log \;V )$ se todos os vértices forem alcançáveis (grafo conectado).

É possível obter um custo assintótico melhor se usarmos heaps Fibonacci, que oferecem um custo amortizado de $O(log \;V )$ por EXTRACT-MIN (o mesmo de antes), mas melhora o custo amortizado de DECREASE-KEY para $O(1)$, totalizando $O(V log \;V + E)$.

5.5.3 Caminhos mínimos em DAGs¶

Em grafos acíclicos direcionados (DAG), não temos ciclos por definição. Isso facilita nossa tarefa de obter caminhos mínimos pois podemos estabelecer qual serão as ordens dos caminhos mínimos. Sabendo disso, podemos relaxar as arestas em uma ordem específica e pela propriedade do relaxamento de um caminho, estamos garantidos que teremos a estimativa ótima para cada vértice. A ordem assim mencionada é diretamente obtida a partir de uma ordenação topológica do grafo de entrada. Observe que assim conseguimos obter os caminhos mínimos a partir de uma fonte em tempo linear $Θ(V + E)$.

***## 5.6 Caminhos mínimos entre todos os pares de vértices

Vamos assumir que os pesos das arestas estão organizados em uma matriz quadrada $w_{ij}$ e que uma matriz de predecessores $Π_{ij}$ armazena os caminhos mínimos entre cada par de vértices. Veremos que essa formulação nos ajudará a construir algoritmos para o caso em que os grafos são densos. A subestrutura de um caminho mínimo nos permite caracterizar uma equação para custos ótimos de subproblemas e também um algoritmo de programação dinâmica. Seja $l_{ij}$ o custo de um caminho mínimo entre o vértice $i$ e $j$. Sabemos que esse caminho pode ter, no máximo, $n − 1$ arestas onde $n = |V|$. Por isso, podemos caracterizar qualquer caminho mínimo em subcaminhos que usam uma quantidade de arestas. Seja $l^{(m)} _{i j}$ o custo do caminho mínimo entre $i$ e $j$ que usa, no máximo, $m$ arestas:

Com essa equação, conseguimos dois algoritmos para o problema.

O primeiro constrói $l^{(0)} _{ij} ⇝ l^{(1)} _{ij} ⇝ · · · ⇝ l^{(m-1)} _{ij}$ para todo par de vértices $i, j$. Computar cada entrada da matriz requer tempo linear porque é o mínimo entre $n$ alternativas. Temos $O(n^2)$ pares e isso quer dizer que cada passo custa $O(n^3)$. Temos ao todo n − 1 passos até conseguir obter os menores caminhos com até $n − 1$ arestas, totalizando $O(V^4)$. Podemos melhorar esse custo ao observar que esse processo iterativo é similar à multiplicação de matrizes e, portanto, podemos “dobrar” sucessivamente a quantidade de arestas consideradas e encontrar $l^{(n-1)} _{ij}$ em menos passos, totalizando $O(V^3 log \; n)$.

5.6.1 Algoritmo de Floyd-Warshall¶

Este algoritmo melhora a definição recursiva de custo de um caminho mínimo ao considerar quais vértices intermediários podem aparecer em um caminho mínimo. Se fixamos um vértice intermediário como $k$, teremos $p : i ⇝ p_{1} \;k ⇝ p_{2} \;j$. Veja que os vértices intermediários que aparecem no subcaminho $p_1$ não podem ser $k$ (mesma coisa para $p_2$). Dessa forma, podemos melhorar um custo de caminho que considere $\{1, ..., k\}$ como vértice intermediário se já tivermos calculado os custos ótimos de caminhos que considerem $\{1, ..., k − 1\}$ como intermediário:

Veja que agora continuamos com um algoritmo iterativo sobre matrizes, mas cada passo de refinamento requer custo constante e não linear. Portanto, temos $O(n)$ iterações e cada uma custa $O(n^2)$, totalizando $O(n^3)$.

Veja que podemos melhorar esse custo de espaço do algoritmo de $O(n^3)$ para $O(n^2)$. Podemos reconstruir também os caminhos mínimos além dos custos ótimos ao armazenar em outra matriz $Π$ quais decisões a cada passo levaram ao melhor custo. Uma alternativa é guardar o índice do predecessor do vértice que levou ao melhor custo: $Π^{(0)}$ considera como predecessores as arestas isoladas.

5.6.2 Algoritmo de Johnson¶

5.7 Fluxo máximo¶

Alguns conceitos importantes em fluxo máximo: entender as premissas do problema como conservação e skew, entender o conceito de cortes nessas redes, entender que o fluxo máximo é limitado superiormente por qualquer corte nessa rede, entender o conceito de redes residuais, entender que um caminho em uma rede residual que vai da origem até o destino indica que a rede admite mais fluxo e que portanto, a função ainda não está maximizada.

Propriedade da conservação do fluxo. Para cada vértice na rede que não for nem a fonte nem o destino, a quantidade de fluxo chegando no vértice deve ser igual à quantidade de fluxo saindo do vértice

Propriedade da restrição de capaciidade. Para cara par de vértices da rede, a quantidade de fluxo passando entre eles não pode ultrapassar a capacidade:

***## 5.8 Exercícios

1 (crls 3ed. – 24.1.5) Dado um grafo direcionado com pesos nas arestas $G(V, E), w : E → \R$. Forneça um algoritmo $O(V E)$ que encontre, para cada vértice v, o valor δ∗(v) = minu∈V {δ(u, v)}.

Descrição de algoritmo: Vamos substituir o procedimento RELAX do algoritmo de Bellman-Ford pelo procedimento RELAX-MIN abaixo. Outra modificação, é inicializar os predecessores de cada vértices como eles próprios: $u.\pi \gets u$ para todo $u ∈ V$ . Veja que o último passo é necessário e coerente, já que $δ(u, u) = 0$ e portanto, representa um limite superior para a função em cada vértice.

2 (crls 3ed. – 24.1.6) Suponha que um grafo direcionado $G(V, E)$ e com pesos nas arestas contenha um ciclo de peso negativo. Forneça um algoritmo eficiente para listar os vértices desse ciclo.

Ideia de algoritmo: faça um caminhamento em profundidade (DFS) no grafo mantendo a soma dos pesos acumulados no caminho. Se o caminhamento encontrar uma aresta de volta (back edge), então um ciclo foi encontrado e tem-se também a soma dos pesos do ciclo. Ao detectar esse ciclo negativo, interrompemos o caminhamento imprimindo os vértices do caminho de volta à raíz, isto é, nas voltas da recursão até o destino da aresta de volta encontrada. Isso pode ser implementado:

(1) executando o Bellman-Ford; (2) marcando $u.d ← −∞$ para vértices alcançáveis através de vértices do ciclo negativo (DFS); (3) fazendo um novo DFS para detectar ciclo a partir de vértices cuja estimativa seja u.d = −∞; se encontrar aresta de volta (back-edge, cinza) significa que um ciclo foi detectado.## 5.9 Grafos Eulerianos e Hamiltonianos

Conceitos importantes: caminhos e ciclos eulerianos, teorema que argumenta que em um grafo euleriano todo vértice tem grau par, algoritmo de Fleury que constrói um ciclo euleriano.

5.9.1 Definições importantes¶

• Percurso: coleção de vértices que são sequencialmente adjacentes

• Caminho: percurso em um grafo direcionado com todas as arestas no sentido início-fim do percurso.

• Percurso simples: não repete ligações.

• Percurso elementar: não repete vértices.

• Ciclo: percurso elementar fechado.

• Circuito: caminho elementar fechado – ciclo orientado.

5.9.2 Grafos eulerianos¶

Teorema 5.1. Um grafo $G = (V, E)$ não direcionado e conexo possui um ciclo euleriano se, e somente se, todos os seus vértices tiverem grau par.

Prova: Para $\Rarr$ devemos observar que em um ciclo precisamos ter uma forma de entrar e sair de cada vértice, ou seja, pelo menos uma quantidade par de arestas incidentes a cada um deles. Para $\Larr$ devemos fazer por indução no número de arestas. Todo grafo conexo cujos graus dos vértices forem todos ≥ 2 possui um percurso fechado: basta escolher iterativamente para cada vértice duas arestas, uma para entrada e uma para saída. Vamos considerar o percurso fechado de maior tamanho. Ao retirar as arestas desse percurso fechado do grafo, temos dois casos: ou todas as arestas foram retiradas e o percurso em questão é por si só um ciclo euleriano (percurso fechado que não repete arestas), ou sobraram algumas arestas formando uma componente também com todos os vértices de grau par – cada vértice tem seu grau diminuído de duas unidades, já que estamos retirando um percurso fechado. Se a componente restante tem vértices com grau par apenas e ela tem arestas, então novamente podemos dizer que existe um percurso fechado. Isso é um absurdo, já que poderíamos combinar esse novo percurso fechado com o percurso fechado inicial e máximo que teríamos um percurso fechado maior ainda, contradizendo a premissa. Em suma, podemos visualizar um ciclo euleriano (percurso fechado com todas as arestas) como uma decomposição disjunta das arestas em vários ciclos.

$\begin{array}{ll} \textbf{\footnotesize CICLO-EULERIANO-FLEURY}(G(V, E)) \text{ // assume que G é euleriano} \\ 1.\ \quad \text{seja } s \in V \text{ um vértice inicial qualquer} \\ 2.\ \quad u \leftarrow s \quad \small{\langle \langle\text{ vértice corrente no percurso } \rangle \rangle}\\ 3.\ \quad \text{ repita enquanto existirem arestas no grafo } \\ 4.\ \quad \quad \textbf{se} \ d(u) = 1 \; \small{\langle \langle \textit{ grau de u} \rangle \rangle}\\ 5.\ \quad \quad \quad \text{escolha a única aresta possível } (u, v) \in E \\ 6.\ \quad \quad \textbf{senão} \\ 7.\ \quad \quad \quad \text{escolha } (u, v) \in E \text{ tal que mesmo que } (u, v) \text{ seja removida,} \\ \quad \quad \quad \quad s\text{ continua na mesma componente do restante das arestas} \\ 8.\ \quad \quad \text{adicione } (u, v) \text{ ao percurso} \\ 9.\ \quad \quad \text{remova a aresta } (u, v) \text{ do grafo } \\ 10.\! \quad \quad u \leftarrow v \\ 11.\! \quad \textbf{retorne} \text{ a sequência de arestas} \end{array}$
$\begin{array}{ll} \textbf{\footnotesize CARTEIRO-CHINES}(G = (V, E)) \\ 1.\ \quad \text{se } G \text{ for não-euleriano} \\ 2.\ \quad \quad \text{seja } I \subseteq V \text{ o conjunto de vértices de grau ímpar} \\ 3.\ \quad \quad \text{para cada } u \in I \\ 4.\ \quad \qquad \text{descubra os caminhos mínimos } d_{uv} \text{ a partir de } u \text{ (usando Dijkstra, por exemplo)} \\ 5.\ \quad \qquad d_{uu} \gets \infty \\ 6.\ \quad \quad P \gets \text{"pares de vértices } u, v \in I \text{ cuja soma das distâncias } d_{uv} \text{ seja mínima"} \text{(Alg. húngaro)} \\ 7.\ \quad \quad \text{para cada } (u, v) \in P \\ 8.\ \quad \qquad \text{adicionar \textbf{aresta artificial} } (u, v) \text{ em } G \text{ com custo } d_{uv} \\ 9.\ \quad C \gets \text{\footnotesize CICLO-EULERIANO-FLEURY}(G = (V, E)) \\ 10.\! \quad \text{ para cada aresta artificial } (u, v) \in C \\ 11.\! \quad \quad C \gets \text{substitua em } C \text{ a aresta } (u, v) \text{ pelo caminho mínimo } u \rightsquigarrow v \\ 12.\! \quad \textbf{retorne } C \\ \end{array}$
$\begin{array}{ll} \textbf{\footnotesize CARTEIRO-CHINES-DIRECIONADO}(G = (V, E)) \\ 1.\ \quad \text{se } G \text{ for não-euleriano} \\ 2.\ \quad \quad \text{seja }S \subseteq V \text{ o conjunto de vértices } u \text{ tal que } d^+(u) - d^-(u) > 0 \} \\ 3.\ \quad \quad \text{seja }T \subseteq V \text{ o conjunto de vértices } u \text{ tal que } d^+(u) - d^-(u) < 0 \} \\ 4.\ \quad \quad \text{para cada } u \in S \\ 5.\ \quad \qquad \text{descubra os caminhos mínimos } d_{uv} \text{ a partir de } u \text{ para todo } v \in T \text{ (Alg. Dijkstra)} \\ 6.\ \quad \qquad d_{uu} \gets \infty \\ 7.\ \quad \quad S' \gets \text{\small REPLICA-VERTICES}(S) \quad \small{\langle \langle w^{(u)} \text{ denota uma cópia de } u \in S \rangle \rangle}\\ 8.\ \quad \quad T' \gets \text{\small REPLICA-VERTICES}(T) \quad \small{\langle \langle w^{(u)} \text{ denota uma cópia de } u \in T \rangle \rangle}\\ 9.\ \quad \quad \text{\footnotesize PREENCHE-DISTANCIAS-REPLICAS}(S', T', S, T) \\ 10.\ \quad \quad P \gets \text{"pares } u \in (S \cup S'), v \in (T \cup T') \text{ cuja soma das distâncias } d_{uv} \text{ seja mínima } \text{" (Alg. húngaro)} \\ 11.\ \quad \quad \text{para cada } (w, z) \in P \\ 12.\ \quad \qquad \text{se } w \text{ é réplica } w^{(r)} \text{ então } u \gets r \text{ senão } u \gets w \\ 13.\ \quad \qquad \text{se } z \text{ é réplica } z^{(r)} \text{ então } v \gets r \text{ senão } v \gets z \\ 14.\ \quad \qquad \text{adicionar \textbf{aresta artificial} } (u, v) \text{ em } G \text{ com custo } d_{uv} \\ 15.\ \quad C \gets \text{\footnotesize CICLO-EULERIANO-FLEURY}(G = (V, E)) \\ 16.\ \quad \text{para cada aresta artificial } (u, v) \in C \\ 17.\ \quad \quad C \gets \text{substitua em } C \text{ a aresta } (u, v) \text{ pelo caminho mínimo } u \rightsquigarrow v \\ 18.\ \quad \textbf{retorne } C \\ \end{array}$
$\begin{array}{ll} \textbf{\footnotesize REPLICA-VERTICES}(V) \\ 1.\quad V' \gets \emptyset \\ 2.\quad \text{para cada } u \in V \\ 3.\quad\quad \text{para } i \gets 2 \text{ até } |d^+(u) - d^-(u)| \\ 4.\quad\quad\quad \text{seja } w^{(u)} \text{ uma cópia de } u \\ 5.\quad\quad\quad V' \gets V' \cup \{w^{(u)}\} \\ 6.\quad \textbf{retorne } V' \\ \end{array}$
$\begin{array}{ll} \textbf{\footnotesize PREENCHE-DISTANCIAS-REPLICAS}(S', T', S, T) \\ 1.\quad \text{para cada } w(u) \in S' \\ 2.\quad\quad \text{para cada } z(v) \in T' \\ 3.\quad\quad\quad d_{w(u)z(v)} \leftarrow d_{uv} \\ 4.\quad \text{para cada } w(u) \in S' \\ 5.\quad\quad \text{para cada } v \in T \\ 6.\quad\quad\quad d_{w(u)v} \leftarrow d_{uv} \\ 7.\quad \text{para cada } u \in S \\ 8.\quad\quad \text{para cada } w(v) \in T' \\ 9.\quad\quad\quad d_{uw(v)} \leftarrow d_{uv} \\ \end{array}$

Algumas características importantes do algoritmo que resolve o problema do carteiro chinês:

• Se trata de um algoritmo de complexidade polinomial: algoritmo húngaro e chamadas do algoritmo de Djkstra continuam sendo polinomiais.
  

• Quando organizamos os vértices de grau ímpar em um grafo não euleriano em pares, isso sempre é seguro já que para qualquer grafo devemos ter uma quantidade par de vértices com grau ímpar: senão a soma dos graus não seria par e sabemos que isso é verdade.
  

• Se um grafo é euleriano já sabemos exatamente qual é o custo mínimo da instância: exatamente a soma dos pesos de cada aresta.
  

• Se um grafo não é euleriano, será inevitável passar por algumas arestas mais de uma vez e isso é capturado pelas arestas artificiais adicionadas: passar por uma aresta artificial (u, v) no percurso é equivalente a um percurso de mesmo custo que usa apenas arestas do grafo original: $u...v$.

5.9.3 Grafos hamiltonianos¶