Skip to article frontmatterSkip to article content
Site not loading correctly?

This may be due to an incorrect BASE_URL configuration. See the MyST Documentation for reference.

Algoritmos em grafos

Ordem de crescimento assintótico (Big-Oh)

Ao longo deste capítulo, o custo de tempo e de espaço de cada algoritmo é indicado por meio da notação assintótica (em particular, a notação Big-Oh), escrita como O(⋅)O(\cdot). O objetivo aqui é oferecer uma noção de como interpretá-la.

A notação O(g(n))O(g(n)) descreve a ordem de crescimento de uma função, isto é, como o custo de um algoritmo escala à medida que o tamanho da entrada cresce (n→∞n \to \infty). Quando dizemos que um algoritmo é O(n2)O(n^2), leia-se “cresce na ordem de n2n^2”: dobrar o tamanho da entrada tende a quadruplicar o custo. O foco recai sobre a tendência de crescimento, não sobre o valor exato do número de operações.

Um aspecto essencial é que constantes multiplicativas e termos de ordem inferior são desprezíveis (e, portanto, ignorados) quando a variável da função assume valores muito altos. Considere, por exemplo, uma função como n2/2+n/2−1n^2/2 + n/2 - 1: embora tenha coeficientes e termos extras, trata-se de um polinômio de grau 2 — sua curva tem o mesmo formato de n2n^2, uma parábola. Como o interesse está no comportamento quando nn é grande, constantes não alteram a natureza nem o formato da curva de crescimento. Isso permite comparar algoritmos de forma abstrata, independente de detalhes de hardware ou implementação.

A escolha de um algoritmo com complexidade eficiente é crucial. A diferença entre O(n2)O(n^2) e O(n3)O(n^3) pode parecer pequena à primeira vista, mas cresce drasticamente: para n=1000n = 1000, n2=106n^2 = 10^6 enquanto n3=109n^3 = 10^9 — mil vezes mais operações. Por isso, ao longo do texto, prestaremos atenção não apenas à corretude de cada algoritmo, mas também à sua classe de complexidade, que determina sua viabilidade em instâncias grandes.

Diferentemente de problemas cuja entrada é descrita por um único tamanho nn, algoritmos em grafos dependem de duas variáveis que descrevem o tamanho da entrada:

Isso é fundamental para interpretar as complexidades deste capítulo. A quantidade de arestas mm varia de 0 (grafo sem arestas) até O(n2)O(n^2) (grafo completo), de modo que expressões como O(n+m)O(n + m) e O(n2)O(n^2) representam realidades distintas. Por exemplo, a lista de adjacência ocupa O(n+m)O(n + m) de espaço — eficiente para grafos esparsos —, enquanto a matriz de adjacências sempre ocupa O(n2)O(n^2), independentemente de mm. Ler O(n+m)O(n + m) exige ter ambas as variáveis em mente: se o grafo for denso (m≈n2m \approx n^2), então O(n+m)=O(n2)O(n + m) = O(n^2); se for esparso (m≈nm \approx n), então O(n+m)=O(n)O(n + m) = O(n).

A tabela abaixo resume as complexidades mais comuns nos algoritmos de grafos que aparecerão ao longo deste capítulo, interpretadas em termos de nn (vértices) e mm (arestas):

NotaçãoIntuição (em grafos)Exemplo no capítulo
O(1)O(1)independe de nn e mminserir aresta na matriz
O(n+m)O(n + m)linear no grafo; cada vértice/aresta é processado poucas vezesBFS, DFS
O(mlog⁡n)O(m \log n)quase-linear; típico de filas de prioridade (heap)Dijkstra, Prim
O(n⋅m)O(n \cdot m)relaxa todas as arestas para cada vérticeBellman-Ford
O(n2)O(n^2)quadrático em vértices; natural em matrizes n×nn \times nespaço da matriz de adjacências
O(n3)O(n^3)três laços aninhados sobre os vérticesWarshall, Floyd-Warshall

Observe como a mesma notação pode comportar-se de forma distinta conforme a densidade do grafo. Ao aproximarmos mm em função de nn, a função efetivamente plotada fica explícita: no caso esparso (m≈nm \approx n), O(n+m)∼O(n)O(n + m) \sim O(n); no caso denso (m≈n2m \approx n^2), O(n+m)∼O(n2)O(n + m) \sim O(n^2). A figura abaixo deixa essas substituições visíveis nos rótulos de cada curva. O eixo horizontal representa o número de vértices nn — as arestas mm variam conforme o regime de densidade.

Curvas de crescimento das complexidades em grafos esparsos e densos

Crescimento de complexidades em grafos: esparso vs. denso


5.1 Representações de grafos

5.1.1 Introdução

G=(V,E)G = (V, E), n=n = número de vértices, m=m = número de arestas. Duas representações básicas:

EstruturaIdeiaMelhor para
Matriz de adjacênciasmatriz n×nn \times n; M[u][v] = 1 se há aresta u→vu \to vgrafos densos
Lista de adjacênciaLA[u] contém apenas os vizinhos de uugrafos esparsos

Densidade d=2mn(n−1)d = \frac{2m}{n(n-1)}: d≈1d \approx 1 → denso (matriz); d≈0d \approx 0 → esparso (lista).


5.1.2 Matriz de adjacências

M[u][v] vale 1 se existe a aresta u→vu \to v, 0 caso contrário.

    0 1 2 3 4
  ┌───────────┐
0 │ 0 1 1 0 0 │
1 │ 0 0 1 1 0 │
2 │ 0 0 0 0 1 │
3 │ 0 0 0 0 1 │
4 │ 0 0 0 0 0 │
  └───────────┘

Implementação em C

#include <stdio.h>

#define MAXN 100

int main() {
    int n, m;

    // matriz de adjacência, inicializada com zeros
    int MA[MAXN][MAXN] = {0};

    // leitura: n vértices e m arestas
    scanf("%d %d", &n, &m);

    for (int i = 0; i < m; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        MA[u][v] = 1;           // digrafo: aresta u -> v
        // MA[v][u] = 1;       // não-direcionado: descomente esta linha
    }

    // impressão da matriz n x n
    for (int u = 0; u < n; u++) {
        for (int v = 0; v < n; v++)
            printf("%d ", MA[u][v]);
        printf("\n");
    }

    return 0;
}

Implementação em C++

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;

    // matriz n x n inicializada com 0
    vector<vector<int>> MA(n, vector<int>(n, 0));

    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        MA[u][v] = 1;           // digrafo: aresta u -> v
        // MA[v][u] = 1;       // não-direcionado: descomente esta linha
    }

    // impressão da matriz
    for (int u = 0; u < n; u++) {
        for (int v = 0; v < n; v++) {
            cout << MA[u][v] << " ";
        }
        cout << "\n";
    }

    return 0;
}

vector é um array dinâmico: cresce automaticamente, push_back anexa ao final em O(1)O(1) amortizado.

Complexidade

OperaçãoCusto
EspaçoO(n2)O(n^2)
Inserir / consultar arestaO(1)O(1)
Iterar vizinhos de uuO(n)O(n)

5.1.3 Lista de adjacência

LA[u] guarda apenas os vizinhos de uu — espaço proporcional a mm, não a n2n^2.

LA[0] -> 1 -> 2
LA[1] -> 2 -> 3
LA[2] -> 4
LA[3] -> 4
LA[4] -> (vazia)

Implementação em C (lista ligada)

#include <stdio.h>
#include <stdlib.h>

#define MAXN 1000

typedef struct no {
    int v;               // vértice de destino
    struct no* prox;     // próximo nó da lista
} no;

// LA[u] aponta para o primeiro vizinho de u (NULL se não houver)
no* LA[MAXN];

// insere v na lista de adjacência de u (inserção no início: O(1))
void insere(int u, int v) {
    no* novo = (no*) malloc(sizeof(no));
    novo->v = v;
    novo->prox = LA[u];
    LA[u] = novo;
}

int main() {
    int n, m;
    scanf("%d %d", &n, &m);

    for (int i = 0; i < m; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        insere(u, v);            // digrafo: aresta u -> v
        // insere(v, u);        // não-direcionado: descomente esta linha
    }

    // impressão
    for (int u = 0; u < n; u++) {
        printf("%d:", u);
        for (no* p = LA[u]; p != NULL; p = p->prox)
            printf(" %d", p->v);
        printf("\n");
    }

    // liberação de memória
    for (int u = 0; u < n; u++) {
        no* p = LA[u];
        while (p != NULL) {
            no* tmp = p;
            p = p->prox;
            free(tmp);
        }
    }

    return 0;
}

Inserção no início é O(1)O(1) mas inverte a ordem dos vizinhos.

Implementação em C++ (vector)

#include <iostream>
#include <vector>
using namespace std;

typedef vector<int> vi;    // apelido: "lista de vizinhos"

int main() {
    int n, m;
    cin >> n >> m;

    // vetor de n listas de adjacência
    vi* LA = new vi[n];

    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        LA[u].push_back(v);     // digrafo: aresta u -> v
        // LA[v].push_back(u); // não-direcionado: descomente esta linha
    }

    // impressão (range-based for — C++11)
    for (int u = 0; u < n; u++) {
        cout << u << ":";
        for (int v : LA[u])
            cout << " " << v;
        cout << "\n";
    }

    delete[] LA;
    return 0;
}

Consultar se uma aresta existe

Não há acesso direto — é preciso percorrer (O(deg⁡(u))O(\deg(u))):

// C
int existe_aresta(no** LA, int u, int v) {
    for (no* p = LA[u]; p != NULL; p = p->prox) {
        if (p->v == v) return 1;
    }
    return 0;
}
// C++
bool existe_aresta(vi* LA, int u, int v) {
    for (int vizinho : LA[u]) {
        if (vizinho == v) return true;
    }
    return false;
}

Complexidade

OperaçãoCusto
EspaçoO(n+m)O(n + m)
Inserir arestaO(1)O(1)
Consultar aresta u→vu \to vO(deg⁡(u))O(\deg(u))
Iterar vizinhos de uuO(deg⁡(u))O(\deg(u))

5.1.4 Extensão para grafos ponderados

Em C (struct com peso)

#include <stdio.h>
#include <stdlib.h>

#define MAXN 1000

typedef struct aresta {
    int v;               // vértice de destino
    int w;               // peso da aresta
    struct aresta* prox;
} aresta;

aresta* LA[MAXN];

void insere(int u, int v, int w) {
    aresta* novo = (aresta*) malloc(sizeof(aresta));
    novo->v = v;
    novo->w = w;
    novo->prox = LA[u];
    LA[u] = novo;
}

int main() {
    int n, m;
    scanf("%d %d", &n, &m);

    for (int i = 0; i < m; i++) {
        int u, v, w;
        scanf("%d %d %d", &u, &v, &w);
        insere(u, v, w);          // digrafo ponderado: u -> v com peso w
        // insere(v, u, w);      // não-direcionado: descomente
    }

    for (int u = 0; u < n; u++) {
        printf("%d:", u);
        for (aresta* p = LA[u]; p != NULL; p = p->prox)
            printf(" (%d,%d)", p->v, p->w);
        printf("\n");
    }

    // liberação (mesma lógica da versão sem peso)
    for (int u = 0; u < n; u++) {
        aresta* p = LA[u];
        while (p != NULL) {
            aresta* tmp = p;
            p = p->prox;
            free(tmp);
        }
    }

    return 0;
}

Em C++ (pair)

pair<int,int> (biblioteca <utility>) agrupa (destino, peso) sem definir struct.

#include <iostream>
#include <vector>
#include <utility>   // pair, make_pair
using namespace std;

typedef pair<int,int> ii;       // (vértice destino, peso)
typedef vector<ii> vii;         // lista de adjacência ponderada

int main() {
    int n, m;
    cin >> n >> m;

    vii* LA = new vii[n];

    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        LA[u].push_back(make_pair(v, w));    // aresta u -> v com peso w
        // LA[v].push_back(make_pair(u, w)); // não-direcionado: descomente
    }

    // impressão: a.first = vértice, a.second = peso
    for (int u = 0; u < n; u++) {
        cout << u << ":";
        for (ii a : LA[u])
            cout << " (" << a.first << "," << a.second << ")";
        cout << "\n";
    }

    delete[] LA;
    return 0;
}

Para matriz ponderada, troque 1/0 pelo peso e use um sentinela (ex.: INT_MAX) para ausência de aresta.


5.1.5 Variantes avançadas

set/map (C++)

A lista com vector consulta arestas em O(deg⁡(u))O(\deg(u)). Substituindo o container, melhora-se a consulta:

ContainerEstrutura internaInserirConsultar existe?Ordem
vector<int>array dinâmicoO(1)O(1) amort.O(deg⁡(u))O(\deg(u))inserção
set<int>árvore rubro-negraO(log⁡deg⁡(u))O(\log \deg(u))O(log⁡deg⁡(u))O(\log \deg(u))crescente
unordered_set<int>hash tableO(1)O(1) médioO(1)O(1) médioindefinida
#include <iostream>
#include <set>
using namespace std;

typedef set<int> si;    // conjunto ordenado de vizinhos

int main() {
    int n, m;
    cin >> n >> m;

    // cada LA[u] é um set<int> (árvore balanceada)
    si* LA = new si[n];

    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        LA[u].insert(v);       // inserção O(log deg(u))
        // LA[v].insert(u);   // não-direcionado: descomente
    }

    // consulta: existe aresta u -> v?  O(log deg(u))
    // LA[u].count(v) retorna 1 se v está no conjunto, 0 caso contrário

    // impressão (set percorre em ordem crescente automaticamente)
    for (int u = 0; u < n; u++) {
        cout << u << ":";
        for (int v : LA[u])
            cout << " " << v;
        cout << "\n";
    }

    delete[] LA;
    return 0;
}

Para grafos ponderados: map<int,int> (árvore rubro-negra) mapeia vizinho →\to peso; unordered_map (hash table) oferece O(1)O(1) médio.

typedef map<int,int> mii;    // vizinho -> peso
// LA[u][v] = w;      // define o peso da aresta u -> v
// LA[u].count(v);    // verifica se a aresta existe

Compressed Sparse Row (CSR)

Formato para processamento de grafos muito usado em álgebra linear esparsa (exemplo: processamento de grafos em GPU). Dois arrays contíguos:

ArrayConteúdoTamanho
col_idx[]vértice de destino de cada aresta, agrupado por origemmm
row_ptr[]índice inicial de cada vértice em col_idx (soma prefixa dos graus)n+1n+1

Número de vizinhos de uu: row_ptr[u+1] - row_ptr[u].

for (i = row_ptr[u]; i < row_ptr[u+1]; i++) {
    v = col_idx[i];
}
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;

    // leitura das arestas
    vector<int> origem(m), destino(m);
    for (int i = 0; i < m; i++)
        cin >> origem[i] >> destino[i];

    // 1. contar grau de cada vértice
    vector<int> row_ptr(n + 1, 0);
    for (int i = 0; i < m; i++)
        row_ptr[origem[i] + 1]++;

    // 2. soma prefixa: row_ptr[u] = início dos vizinhos de u em col_idx
    for (int u = 0; u < n; u++)
        row_ptr[u + 1] += row_ptr[u];

    // 3. preencher col_idx (preserva a ordem de leitura das arestas)
    vector<int> col_idx(m);
    vector<int> pos = row_ptr;    // posição de escrita atual por vértice
    for (int i = 0; i < m; i++) {
        int u = origem[i];
        col_idx[pos[u]] = destino[i];
        pos[u]++;
    }

    // impressão
    for (int u = 0; u < n; u++) {
        cout << u << ":";
        for (int i = row_ptr[u]; i < row_ptr[u + 1]; i++)
            cout << " " << col_idx[i];
        cout << "\n";
    }

    return 0;
}

Para grafos ponderados, adicione um array values[] paralelo a col_idx[].


5.1.6 Entrada de exemplo e compilação

Salve como input.txt:

5 6
0 1
0 2
1 2
1 3
2 4
3 4
# C
gcc matriz-adjacencias.c -o matriz-c
gcc lista-adjacencia.c -o lista-c

# C++
g++ -std=c++17 matriz-adjacencias.cpp -o matriz-cpp
g++ -std=c++17 lista-adjacencia.cpp -o lista-cpp
g++ -std=c++17 lista-set.cpp -o lista-set
g++ -std=c++17 csr.cpp -o csr

# Executar (todos leem o mesmo input.txt)
./matriz-c < input.txt
./lista-c   < input.txt
./matriz-cpp < input.txt
./lista-cpp  < input.txt
./lista-set  < input.txt
./csr        < input.txt

Saída esperada da matriz:

0 1 1 0 0
0 0 1 1 0
0 0 0 0 1
0 0 0 0 1
0 0 0 0 0

Saída esperada da lista (C++, com push_back — preserva ordem de inserção):

0: 1 2
1: 2 3
2: 4
3: 4
4:

Em C (lista ligada com inserção no início), a ordem dos vizinhos aparece invertida.

Para a versão ponderada, use uma entrada com três valores por linha:

5 6
0 1 10
0 2 5
1 2 2
1 3 7
2 4 3
3 4 1

5.2 Fecho transitivo (algoritmo de Warshall)

O fecho transitivo de um grafo direcionado G=(V,E)G = (V, E) é o grafo G∗=(V,E∗)G^* = (V, E^*) onde E∗E^* contém todo par (u,v)(u, v) tal que existe um caminho de uu a vv em GG. Frequentemente, nos referimos ao algoritmo que computa essa propriedade através do nome de seu autor (Algoritmo de Warshall). A ideia central é estender progressivamente o conjunto de vértices intermediários permitidos: a cada passo kk, verificamos se incluir kk como intermediário cria novos caminhos entre pares de vértices. O algoritmo de Warshall é fundamental por (1) determinar a alcançabilidade entre todos os pares de vértices; (2) revelar a estrutura de conectividade do grafo; (3) servir como base para o algoritmo de Floyd-Warshall, que estende a mesma estrutura para caminhos mínimos ponderados. De fato, como exemplo, o fecho transitivo é geralmente usado para verificar se um grafo é fortemente conectado e para identificar componentes fortemente conectados.

O pseudocódigo é indicado abaixo, mas algumas informações são importantes:

WARSHALL(G)
// argumentos:
// G: grafo direcionado com vértices V e matriz de adjacências G.M (n x n)

W_0 = G.M                       // caso base: apenas arestas diretas
for k = 1 to n
   W_k = nova matriz (n x n)    // nova matriz alocada para este intermediário
   for u = 1 to n
      for v = 1 to n
         W_k[u][v] = W_{k-1}[u][v] OR (W_{k-1}[u][k] AND W_{k-1}[k][v])
return W_n

Complexidade de tempo: Observe que, sendo nn a quantidade de vértices do grafo, temos três laços aninhados cada um executando uma quantidade fixa de iterações (1⋯n1 \cdots n). Assim, temos um algoritmo que totaliza uma ordem de O(n3)O(n^3) operações.

Complexidade de espaço: O algoritmo aloca uma nova matriz W_i de tamanho (n×n)(n \times n) a cada iteração de vértices intermediários kk, totalizando n×O(n2)=O(n3)n \times O(n^2) = O(n^3) na ordem de espaço gasto. É possível otimizar o custo de espaço de O(n3)O(n^3) para O(n2)O(n^2) atualizando a mesma matriz in-place a cada iteração kk. Isso é seguro porque a kk-ésima linha e coluna não se alteram: como W_{k-1}[k][k] = 1, temos W_k[u][k] = W_{k-1}[u][k] OR (W_{k-1}[u][k] AND 1) = W_{k-1}[u][k], e analogamente W_k[k][v] = W_{k-1}[k][v]. Logo, os valores lidos durante a atualização in-place são exatamente os mesmos que seriam lidos da matriz anterior.


5.3 Caminhamento em largura (Breadth-first search - BFS)

Um caminhamento (ou busca) em largura é um procedimento cujo objetivo é visitar (encontrar) cada vértice de um grafo e, naturalmente, seguindo as arestas. Frequentemente, nos referimos a essa busca através do nome em inglês e sua sigla (Breadth-First Search - BFS). Busca em largura significa que os vizinhos de um vértice são todos visitados antes que possamos cogitar visitar vizinhos dos vizinhos (remete a uma ideia de fila FIFO). A BFS é um algoritmo tão fundamental que é utilizada para (1) extrair propriedades estruturais de um grafo; (2) consultar atributos de vértices e arestas de forma ordenada e eficiente; (3) como subrotina de outras tarefas em grafos. De fato, como exemplo, a BFS é geralmente é usada para encontrar distâncias mínimas de um vértice a todos os outros em relação ao número de arestas.

O pseudocódigo é indicado abaixo, mas algumas informações são importantes:

bfs(G, s)
// argumentos:
// G: grafo com vértices V e listas de adjacências Adjlist
// s: vértice fonte que representa o ponto de partida da busca

  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) // próximo da fila FIFO
    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    // BLACK: totalmente explorado

5.3.1 Grafos de exemplo para exercitar BFS

Exemplos:

Três grafos de exemplo para exercitar a busca em largura

Grafos de exemplo para BFS

5.4 Caminhamento em profundidade (Depth-first search - DFS)

Um caminhamento (ou busca) em profundidade é um procedimento cujo objetivo é, assim como a busca em largura, visitar (encontrar) cada vértice de um grafo seguindo as arestas. Frequentemente, nos referimos a essa busca através do nome em inglês e sua sigla (Depth-First Search - DFS). Busca em profundidade significa que, a partir de um vértice, exploramos o mais profundamente possível cada ramo antes de retroceder (backtrack) e visitar outros vizinhos (remete a uma ideia de pilha LIFO, naturalmente implementada via recursão). A DFS é um algoritmo tão fundamental que é utilizada para (1) classificar arestas de um grafo direcionado; (2) realizar ordenação topológica em DAGs; (3) encontrar componentes fortemente conectados; (4) detectar ciclos. De fato, como exemplo, a DFS é geralmente usada para determinar a estrutura de ancestralidade entre vértices por meio dos tempos de descoberta e término.

O pseudocódigo é indicado abaixo, mas algumas informações são importantes:

dfs(G)
// argumentos:
// G: grafo com vértices V e listas de adjacências Adjlist

  for each vertex u in G.V
    u.color = WHITE
    u.pi = NIL
  for each vertex u in G.V
    if u.color == WHITE
      dfs-visit(G, u)

time = 0    // variável global para marcar os tempos dos vértices

dfs-visit(G, u)
// argumentos:
// G: grafo com vértices V e listas de adjacências Adjlist
// u: vértice a visitar

  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

5.4.1 Grafos de exemplo para exercitar DFS

Exemplos:

Três grafos de exemplo para exercitar a busca em profundidade

Grafos de exemplo para DFS


5.4.2 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)(u, v), temos alguma informação sobre qual tipo de aresta ela será. Se a cor de v for WHITEWHITE, então a aresta (u,v)(u, v) é uma aresta da árvore (tree edge). Se a cor do vértice vv for GRAYGRAY , então a aresta (u,v)(u, v) é de volta (back). Se a cor de vv for BLACKBLACK, 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 BLACKBLACK, 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.4.3 Detecção de articulações e pontes

O algoritmo de Tarjan estende a DFS com dois atributos adicionais além dos já conhecidos (u.coloru.color, u.du.d, u.πu.\pi):

Em grafos não direcionados, toda aresta de volta define um ciclo, de modo que u.lowu.low rastreia, em essência, até onde os ciclos da subárvore conseguem subir em direção à raiz. Se u.low<u.du.low < u.d, existe um ciclo que conecta a subárvore de uu a algum ancestral acima de uu, funcionando como caminho alternativo de conectividade. Se u.low=u.du.low = u.d, nenhum ciclo escapa acima de uu e a subárvore pende isolada — justamente o que caracteriza articulações e pontes:

time = 0        // variável global para marcar os tempos dos vértices

tarjan-pontes-articulacoes(G)
// argumentos:
// G: grafo com vértices V e listas de adjacências Adjlist
// ART: conjunto global de articulações (vértices de corte)
// PONTES: conjunto global de pontes (arestas cuja remoção desconecta o grafo)

  ART = {}        // conjunto global de articulações
  PONTES = {}     // conjunto global de pontes
  for each vertex u in G.V
    u.color = WHITE
    u.pi = NIL
  for each vertex u in G.V
    if u.color == WHITE
      nchildren = dfs-tarjan(G, u)
      if nchildren > 1
        ART = ART union {u}     // raiz com mais de um filho é articulação
  return ART, PONTES

dfs-tarjan(G, u)
// argumentos:
// G: grafo com vértices V e listas de adjacências Adjlist
// u: vértice a visitar

  u.color = GRAY
  nchildren = 0
  time = time + 1
  u.d = time
  u.low = time
  for each v in G.AdjList[u]
    if v.color == WHITE     // (u,v) é aresta de árvore
      v.pi = u
      nchildren = nchildren + 1
      dfs-tarjan(G, v)
      if u.pi != NIL and v.low >= u.d
        ART = ART union {u}            // u (não-raiz) é articulação
      if v.low > u.d
        PONTES = PONTES union {(u,v)}  // (u,v) é ponte
      u.low = min(u.low, v.low)
    else if v != u.pi
      u.low = min(u.low, v.d)
  u.color = BLACK
  return nchildren

5.4.4 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.4.5 Encontrando componentes fortemente conectados

A ideia aqui é que ao executar o DFS em GTG^T , sempre visitamos primeiro aqueles vértices de maior tempo de término em GG, 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.5 Árvores geradoras de custo mínimo

5.5.1 Algoritmo de Prim

Fazemos nn operações de EXTRACT-MIN, uma para cada vértice, totalizando O(nlog⁡n)O(n \log n). Além disso, no pior caso, as chaves dos vértices são atualizadas O(m)O(m) vezes, já que fazemos isso para as listas de adjacências do grafo. Como cada operação DECREASE-KEY custa O(log⁡n)O(\log n), temos o total de O(nlog⁡n+mlog⁡n)=O(mlog⁡n)O(n \log n + m \log n) = O(m \log n).

A complexidade final depende da implementação da fila de prioridades utilizada. Para detalhes sobre as diferentes implementações (arranjo simples e heap binário), consulte a seção Filas de Prioridade do capítulo Estruturas de Dados.

mst-prim(G, w, r)
// argumentos:
// G: grafo com vértices V e arestas E
// w: função de peso das arestas
// r: vértice de partida

  for each u in V
    u.pi = NIL
    u.key = infinity
  r.key = 0
  Q = build-priority-queue(V)
  while Q is not empty
    u = extract-min(Q)
    for each vertex v in G.AdjList[u]
      if v in Q and w(u, v) < v.key
        v.key = w(u, v)
        v.pi = u
        decrease-key(Q, v, v.key)

Análise de complexidade

Usando arranjo simples:

OperaçãoChamadasCusto por chamadaCusto total
build-priority-queue1O(n)O(n)O(n)O(n)
extract-minnnO(n)O(n)O(n2)O(n^2)
decrease-keyO(m)O(m)O(1)O(1)O(m)O(m)
TotalO(n2+m)=O(n2)O(n^2 + m) = O(n^2)

Usando heap binário:

OperaçãoChamadasCusto por chamadaCusto total
build-priority-queue1O(n)O(n)O(n)O(n)
extract-minnnO(log⁡n)O(\log n)O(nlog⁡n)O(n \log n)
decrease-keyO(m)O(m)O(log⁡n)O(\log n)O(mlog⁡n)O(m \log n)
TotalO(nlog⁡n+mlog⁡n)=O(mlog⁡n)O(n \log n + m \log n) = O(m \log n)

Observação: A escolha da estrutura de dados é crítica. Em grafos densos (m≈n2m \approx n^2), ambas as implementações resultam em O(n2)O(n^2) ou O(n2log⁡n)O(n^2 \log n), respectivamente. Em grafos esparsos (m≈nm \approx n), o heap é significativamente superior: O(nlog⁡n)O(n \log n) versus O(n2)O(n^2).


5.5.2 Algoritmo de Kruskal

O custo do algoritmo é dominado pela ordenação das mm arestas por peso, que leva O(mlog⁡m)O(m \log m). Além da ordenação, o algoritmo faz nn operações MAKE-SET e mm operações FIND-SET/UNION sobre a estrutura de conjuntos disjuntos. Com a implementação por florestas com union by rank e compressão de caminho, essas operações têm custo quase constante amortizado, totalizando um custo essencialmente linear que, como assumimos GG conectado (m≥n−1m \geq n − 1), é absorvido pela ordenação. O custo total é, portanto, O(mlog⁡m)O(m \log m) e, como m<n2m < n^2 implica log⁡m=O(log⁡n)\log m = O(\log n), podemos declará-lo como O(mlog⁡n)O(m \log n). Para detalhes sobre as implementações dessa estrutura, consulte a seção Conjuntos Disjuntos do capítulo Estruturas de Dados.

mst-kruskal(G, w)
// argumentos:
// G: grafo com vértices V e arestas E
// w: função de peso das arestas

  A = {}
  for each u in V
    make-set(u)
  E_sorted = sort-by-weight-nondecreasing(E, w) // ordena arestas por w em ordem não-decrescente
  for each (u, v) in E_sorted // em ordem
    if find-set(u) != find-set(v)
      A = A union {(u, v)}
      union(u, v)

5.6 Propriedades de caminhos mínimos


5.7 Caminhos mínimos a partir de uma única fonte

5.7.1 Algoritmo de Bellman-Ford

relax(u, v, w)
// argumentos:
// u: vértice de origem
// v: vértice de destino
// w: função de peso das arestas

  if v.d > u.d + w(u, v)
    v.d = u.d + w(u, v)
    v.pi = u
bellman-ford(G, w, s)
// argumentos:
// G: grafo com vértices V e arestas E
// w: função de peso das arestas
// s: vértice fonte

  for each u in V
    u.pi = NIL
    u.d = infinity
  s.d = 0
  for i = 1 to n - 1
    for each (u, v) in E
      relax(u, v, w)
  for each (u, v) in E
    if v.d > u.d + w(u, v)
      return false // existe ciclo negativo
  return true

5.7.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 nn operações EXTRACT-MIN e faz O(m)O(m) operações DECREASE-KEY (que acontece quando relaxamos uma aresta e diminuímos a prioridade de um vértice). A complexidade final depende da implementação da fila de prioridades utilizada. Para detalhes sobre as diferentes implementações (arranjo simples e heap binário), consulte a seção Filas de Prioridade do capítulo Estruturas de Dados.

dijkstra(G, w, s)
// argumentos:
// G: grafo com vértices V e arestas E
// w: função de peso das arestas
// s: vértice fonte

  for each u in V
    u.pi = NIL
    u.d = infinity
  s.d = 0
  S = empty
  Q = build-priority-queue(V)
  while Q is not empty
    u = extract-min(Q)
    S = S union {u}
    for each vertex v in G.AdjList[u]
      if v in Q and v.d > u.d + w(u, v)
        v.d = u.d + w(u, v)
        v.pi = u
        decrease-key(Q, v, v.d)

Análise de complexidade

Usando arranjo simples:

OperaçãoChamadasCusto por chamadaCusto total
build-priority-queue1O(n)O(n)O(n)O(n)
extract-minnnO(n)O(n)O(n2)O(n^2)
decrease-keyO(m)O(m)O(1)O(1)O(m)O(m)
TotalO(n2+m)=O(n2)O(n^2 + m) = O(n^2)

Usando heap binário:

OperaçãoChamadasCusto por chamadaCusto total
build-priority-queue1O(n)O(n)O(n)O(n)
extract-minnnO(log⁡n)O(\log n)O(nlog⁡n)O(n \log n)
decrease-keyO(m)O(m)O(log⁡n)O(\log n)O(mlog⁡n)O(m \log n)
TotalO(nlog⁡n+mlog⁡n)=O(mlog⁡n)O(n \log n + m \log n) = O(m \log n)

Observação: Assim como em Prim, a escolha da estrutura de dados é crítica. Em grafos esparsos (m≈nm \approx n), o heap binário oferece uma melhoria significativa: O(nlog⁡n)O(n \log n) versus O(n2)O(n^2).


5.7.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.

O algoritmo tem duas fases:

  1. Ordenação topológica dos vértices de GG (seção 5.4.4)

  2. Relaxamento das arestas nessa ordem: para cada vértice uu na ordem topológica, relaxamos todas as arestas que saem de uu, isto é, as arestas (u,v)(u, v) da lista de adjacência G.AdjList[u]G.AdjList[u]

A garantia de correção vem da propriedade da convergência (seção 5.6): quando processamos o vértice uu na ordem topológica, todos os vértices com arestas chegando em uu já foram processados e, portanto, todas as arestas que entram em uu já foram relaxadas. Isso quer dizer que u.du.d já é o caminho mínimo real δ(s,u)δ(s, u) e não será mais alterado. Assim, ao relaxar as arestas que saem de uu, propagamos diretamente o custo ótimo para os vizinhos de uu. Uma única passada pelos vértices basta.

dag-shortest-paths(G, w, s)
// argumentos:
// G: grafo direcionado acíclico com vértices V e arestas E
// w: função de peso das arestas
// s: vértice fonte

  for each u in V
    u.pi = NIL
    u.d = infinity
  s.d = 0
  V_sorted = topological-sort(G)
  for each u in V_sorted // em ordem topológica
    for each v in G.AdjList[u] // arestas que saem de u
      if v.d > u.d + w(u, v) then // relaxa a aresta (u, v)
        v.d = u.d + w(u, v)
        v.pi = u

Duas observações importantes sobre esse algoritmo:

Ao final, os predecessores u.πu.\pi definem a árvore de caminhos mínimos com raiz em ss (propriedade do predecessor, seção 5.6). Observe que assim conseguimos obter os caminhos mínimos a partir de uma fonte em tempo linear Θ(V+E)Θ(V + E).


5.7.4 Exercícios interessantes

Dois exercícios do CLRS 3ed. sobre o tema desta seção, com esboços de solução.

1 (crls 3ed. – 24.1.5) Dado um grafo direcionado com pesos nas arestas G=(V,E)G = (V, E), w:E→Rw : E \to \mathbb{R}. Forneça um algoritmo O(VE)O(VE) que encontre, para cada vértice vv, o valor δ∗(v)=min⁡u∈V{δ(u,v)}\delta^*(v) = \min_{u \in V}\{\delta(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értice como eles próprios: u.π←uu.\pi \gets u para todo u∈Vu \in V. Esse passo é necessário e coerente, já que δ(u,u)=0\delta(u, u) = 0 e, portanto, representa um limite superior para a função em cada vértice.

relax-min(u, v, w)
// argumentos:
// u: vértice de origem
// v: vértice de destino
// w: função de peso das arestas

  if v.d > MIN(w(u, v), u.d + w(u, v))
    v.d = MIN(w(u, v), u.d + w(u, v))
    v.pi = u.pi // o predecessor de v é o predecessor de u: u ou u' != u

2 (crls 3ed. – 24.1.6) Suponha que um grafo direcionado G=(V,E)G = (V, 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 à raiz, 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←−∞u.d \gets -\infty 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=−∞u.d = -\infty; se encontrar aresta de volta (back edge, cinza), significa que um ciclo foi detectado.


5.8 Caminhos mínimos entre todos os pares de vértices

Vamos assumir que os pesos das arestas estão organizados em uma matriz quadrada wijw_{ij} e que uma matriz de predecessores ΠijΠ_{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 lijl_{ij} o custo de um caminho mínimo entre o vértice ii e jj. Sabemos que esse caminho pode ter, no máximo, n−1n − 1 arestas (onde nn é o número de vértices). Por isso, podemos caracterizar qualquer caminho mínimo em subcaminhos que usam uma quantidade de arestas. Seja lij(k)l^{(k)} _{i j} o custo do caminho mínimo entre ii e jj que usa, no máximo, kk arestas:

lij(k)={0se k=0 e i=j∞k=0 e i≠jmin1≤u≤n(liu(k−1)+wuj)caso contraˊriol^{(k)}_{ij} = \begin{cases} 0 & \text{se } k = 0 \text{ e } i = j \\ \infin & k = 0 \text{ e } i \neq j \\ \text{min} _{1≤u≤n} (l^{(k-1)}_{iu} + w_{uj}) & \text{caso contrário} \end{cases}

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

O primeiro constrói lij(0)⇝lij(1)⇝⋅⋅⋅⇝lij(k−1)l^{(0)} _{ij} ⇝ l^{(1)} _{ij} ⇝ · · · ⇝ l^{(k-1)} _{ij} para todo par de vértices i,ji, j. Computar cada entrada da matriz requer tempo linear porque é o mínimo entre nn alternativas. Temos O(n2)O(n^2) pares e isso quer dizer que cada passo custa O(n3)O(n^3). Temos ao todo n−1n − 1 passos até conseguir obter os menores caminhos com até n−1n − 1 arestas, totalizando O(n4)O(n^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 lij(n−1)l^{(n-1)} _{ij} em menos passos, totalizando O(n3log⁡n)O(n^3 \log n).


5.8.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 kk, teremos p:u⇝p1  k⇝p2  vp : u ⇝ p_{1} \;k ⇝ p_{2} \;v. Veja que os vértices intermediários que aparecem no subcaminho p1p_1 não podem ser kk (mesma coisa para p2p_2). Dessa forma, podemos melhorar um custo de caminho que considere {1,...,k}\{1, ..., k\} como vértice intermediário se já tivermos calculado os custos ótimos de caminhos que considerem {1,...,k−1}\{1, ..., k − 1\} como intermediário:

duv(k)={wuvk=0min(duv(k−1),duk(k−1)+dkv(k−1))se k>0d^{(k)}_{uv} = \begin{cases} w_{uv} & k = 0 \\ \text{min} (d^{(k-1)}_{uv}, d^{(k-1)}_{uk} + d^{(k-1)}_{kv} ) & \text{se } k > 0 \end{cases}

Na notação do pseudocódigo abaixo, wijw_{ij} corresponde a G.W[u][v]G.W[u][v] e duv(k)d^{(k)}_{uv} corresponde a Dk[u][v]D_k[u][v]. 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)O(n) iterações e cada uma custa O(n2)O(n^2), totalizando O(n3)O(n^3).

floyd-warshall(G)
// argumentos:
// G: grafo com vértices V e matriz de pesos G.W (n x n)

  D_0 = G.W                          // caso base: nenhum vértice intermediário
  for k = 1 to n
    D_k = nova matriz (n x n)
    for u = 1 to n
      for v = 1 to n
        D_k[u][v] = min(D_{k-1}[u][v], D_{k-1}[u][k] + D_{k-1}[k][v])
  return D_n

Veja que podemos melhorar esse custo de espaço do algoritmo de O(n3)O(n^3) para O(n2)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)Π^{(0)} considera como predecessores as arestas isoladas.

A versão abaixo implementa essa otimização: usa uma única matriz DD atualizada in-place (note que D[u][k]D[u][k] e D[k][v]D[k][v] não se alteram durante a iteração kk, logo a leitura é segura) e mantém a matriz de predecessores ΠΠ para reconstruir os caminhos mínimos.

floyd-warshall(G)
// argumentos:
// G: grafo com vértices V e matriz de pesos G.W (n x n)

  D = G.W
  for u = 1 to n
    for v = 1 to n
      if u != v and D[u][v] < ∞ then
        Π[u][v] = u
      else
        Π[u][v] = NIL
  for k = 1 to n
    for u = 1 to n
      for v = 1 to n
        if D[u][k] + D[k][v] < D[u][v] then
          D[u][v] = D[u][k] + D[k][v]
          Π[u][v] = Π[k][v]
  return D, Π

Exemplo passo a passo

Considere o grafo direcionado abaixo com 4 vértices e 6 arestas ponderadas:

Grafo direcionado com 4 vértices e 6 arestas ponderadas

Grafo de exemplo para Floyd-Warshall

A matriz de custos inicial DD e a matriz de predecessores ΠΠ são:

k=0 (inicial):
    D (custos)                      Π (predecessores)
  ┌─────┬─────┬─────┬─────┐       ┌─────┬─────┬─────┬─────┐
  │   0 │   5 │   ∞ │  15 │       │   - │   1 │   - │   1 │
  ├─────┼─────┼─────┼─────┤       ├─────┼─────┼─────┼─────┤
  │   ∞ │   0 │   ∞ │   5 │       │   - │   - │   - │   2 │
  ├─────┼─────┼─────┼─────┤       ├─────┼─────┼─────┼─────┤
  │   1 │   8 │   0 │   ∞ │       │   3 │   3 │   - │   - │
  ├─────┼─────┼─────┼─────┤       ├─────┼─────┼─────┼─────┤
  │   ∞ │   ∞ │   2 │   0 │       │   - │   - │   4 │   - │
  └─────┴─────┴─────┴─────┘       └─────┴─────┴─────┴─────┘

k=1:
    D (custos)                      Π (predecessores)
  ┌─────┬─────┬─────┬─────┐       ┌─────┬─────┬─────┬─────┐
  │   0 │   5 │   ∞ │  15 │       │   - │   1 │   - │   1 │
  ├─────┼─────┼─────┼─────┤       ├─────┼─────┼─────┼─────┤
  │   ∞ │   0 │   ∞ │   5 │       │   - │   - │   - │   2 │
  ├─────┼─────┼─────┼─────┤       ├─────┼─────┼─────┼─────┤
  │   1 │   6*│   0 │  16*│       │   3 │   1*│   - │   1*│
  ├─────┼─────┼─────┼─────┤       ├─────┼─────┼─────┼─────┤
  │   ∞ │   ∞ │   2 │   0 │       │   - │   - │   4 │   - │
  └─────┴─────┴─────┴─────┘       └─────┴─────┴─────┴─────┘

k=2:
    D (custos)                      Π (predecessores)
  ┌─────┬─────┬─────┬─────┐       ┌─────┬─────┬─────┬─────┐
  │   0 │   5 │   ∞ │  10*│       │   - │   1 │   - │   2*│
  ├─────┼─────┼─────┼─────┤       ├─────┼─────┼─────┼─────┤
  │   ∞ │   0 │   ∞ │   5 │       │   - │   - │   - │   2 │
  ├─────┼─────┼─────┼─────┤       ├─────┼─────┼─────┼─────┤
  │   1 │   6 │   0 │  11*│       │   3 │   1 │   - │   2*│
  ├─────┼─────┼─────┼─────┤       ├─────┼─────┼─────┼─────┤
  │   ∞ │   ∞ │   2 │   0 │       │   - │   - │   4 │   - │
  └─────┴─────┴─────┴─────┘       └─────┴─────┴─────┴─────┘

k=3:
    D (custos)                      Π (predecessores)
  ┌─────┬─────┬─────┬─────┐       ┌─────┬─────┬─────┬─────┐
  │   0 │   5 │   ∞ │  10 │       │   - │   1 │   - │   2 │
  ├─────┼─────┼─────┼─────┤       ├─────┼─────┼─────┼─────┤
  │   ∞ │   0 │   ∞ │   5 │       │   - │   - │   - │   2 │
  ├─────┼─────┼─────┼─────┤       ├─────┼─────┼─────┼─────┤
  │   1 │   6 │   0 │  11 │       │   3 │   1 │   - │   2 │
  ├─────┼─────┼─────┼─────┤       ├─────┼─────┼─────┼─────┤
  │   3*│   8*│   2 │   0 │       │   3*│   1*│   4 │   - │
  └─────┴─────┴─────┴─────┘       └─────┴─────┴─────┴─────┘

k=4:
    D (custos)                      Π (predecessores)
  ┌─────┬─────┬─────┬─────┐       ┌─────┬─────┬─────┬─────┐
  │   0 │   5 │  12*│  10 │       │   - │   1 │   4*│   2 │
  ├─────┼─────┼─────┼─────┤       ├─────┼─────┼─────┼─────┤
  │   8*│   0 │   7*│   5 │       │   3*│   - │   4*│   2 │
  ├─────┼─────┼─────┼─────┤       ├─────┼─────┼─────┼─────┤
  │   1 │   6 │   0 │  11 │       │   3 │   1 │   - │   2 │
  ├─────┼─────┼─────┼─────┤       ├─────┼─────┼─────┼─────┤
  │   3 │   8 │   2 │   0 │       │   3 │   1 │   4 │   - │
  └─────┴─────┴─────┴─────┘       └─────┴─────┴─────┴─────┘

Observe como cada iteração kk permite usar o vértice kk como intermediário. Por exemplo, em k=1k=1, o caminho 3→1→23 \to 1 \to 2 (custo 1+5=61+5=6) melhora a aresta direta 3→23 \to 2 (custo 8), e o predecessor de 2 no caminho mínimo a partir de 3 passa a ser 1. Em k=2k=2, o caminho 1→2→41 \to 2 \to 4 (custo 5+5=105+5=10) melhora a aresta direta 1→41 \to 4 (custo 15). A iteração k=4k=4 revela caminhos que só se tornam ótimos quando o vértice 4 é permitido como intermediário, como 1→2→4→31 \to 2 \to 4 \to 3 (custo 5+5+2=125+5+2=12).


5.8.2 Algoritmo de Johnson


5.9 Fluxo máximo

Uma rede de escoamento (ou rede de fluxo) é um grafo direcionado que modela a distribuição (o fluxo) de algum recurso a partir de um vértice fonte ss até um vértice de destino tt: o escoamento parte de ss e chega a tt, e cada aresta (arco) possui uma capacidade máxima. Exemplos de aplicação: líquidos em tubulações, corrente em uma rede elétrica, informação em redes de computadores e linhas de montagem.

Dado um grafo direcionado G=(V,E)G = (V, E), uma fonte e um destino s,t∈Vs, t \in V e capacidades nas arestas c(u,v)c(u,v) para cada (u,v)∈E(u,v) \in E, o objetivo é encontrar a quantidade máxima de fluxo ∣f∣|f| que pode ser enviada a partir de ss até tt de forma que nenhuma capacidade seja violada.

A rede abaixo ilustra o problema: cada aresta traz a sua capacidade máxima.

Rede de escoamento de s a t, com capacidades nas arestas

Rede de escoamento de s a t, com capacidades nas arestas

Trabalharemos com as seguintes premissas:

  1. não existem arestas (arcos) anti-paralelos nem laços;

  2. todo vértice u∈V∖{s,t}u \in V \setminus \{s,t\} está em algum caminho de ss a tt;

  3. capacidades e fluxos são números inteiros não negativos.


5.9.1 Propriedades de um fluxo

Restrição de capacidade. Para cada par de vértices, o fluxo não pode ultrapassar a capacidade:

0≤f(u,v)≤c(u,v)0 \le f(u,v) \le c(u,v)

Em particular, se (u,v)∉E(u,v) \notin E, então c(u,v)=0c(u,v) = 0: só circula fluxo pelas arestas do grafo. Na rede da figura anterior, por exemplo, 0≤f(v1,v3)≤60 \le f(v_1, v_3) \le 6.

Conservação do fluxo. Para cada vértice que não seja ss nem tt, a quantidade de fluxo “chegando” deve ser a mesma da quantidade de fluxo “saindo”:

∑u∈Vf(u,v)=∑u∈Vf(v,u)para todo v∈V∖{s,t}\sum_{u \in V} f(u,v) = \sum_{u \in V} f(v,u) \quad \text{para todo } v \in V \setminus \{s,t\}

As duas propriedades se combinam. A restrição de capacidade permite até 6 unidades em (v1,v3)(v_1,v_3), mas a conservação impõe um limite menor: o vértice v1v_1 recebe fluxo apenas de ss (capacidade 2) e de v2v_2 (capacidade 2), de modo que no máximo 4 unidades podem passar por (v1,v3)(v_1,v_3).

Para um algoritmo, não podemos preencher os fluxos das arestas arbitrariamente, pois aumentar o fluxo em algumas arestas pode impossibilitar que arestas mais vantajosas sejam exploradas. As redes residuais, apresentadas a seguir, auxiliam na identificação dessas oportunidades.


5.9.2 Redes residuais

Uma rede residual GfG_f de um grafo GG indica, para cada par de vértices, qual é o potencial de aumentar ou diminuir o fluxo naquele ponto:

Quando aplicada ao grafo todo, a rede residual mostra as oportunidades de aumento do fluxo ∣f∣|f| total. O exemplo abaixo mostra um fluxo com ∣f∣=3|f| = 3, em notação fluxo/capacidade (apenas a capacidade quando o fluxo é 0), e a rede residual correspondente:

Fluxo com f = 3, em notação fluxo/capacidade, e a respectiva rede residual

Fluxo com |f| = 3, em notação fluxo/capacidade, e a respectiva rede residual


5.9.3 Caminhos de aumento

Um caminho de aumento em uma rede residual GfG_f é qualquer caminho que começa em ss e termina em tt. A menor capacidade residual ao longo do caminho (o gargalo Δ\Delta) indica quantas unidades de fluxo podem ser somadas a ∣f∣|f|.

No exemplo anterior, o caminho s→4v1→6v3→2ts \xrightarrow{4} v_1 \xrightarrow{6} v_3 \xrightarrow{2} t tem gargalo Δ=2\Delta = 2 e eleva o fluxo de ∣f∣=3|f| = 3 para ∣f∣=5|f| = 5. A rede residual fica atualizada como abaixo; note que a aresta (v3,t)(v_3,t) satura e deixa de aparecer em GfG_f:

Caminho de aumento s → v1 → v3 → t destacado na rede residual e a rede residual atualizada, com f = 5

Caminho de aumento s → v1 → v3 → t destacado na rede residual e a rede residual atualizada, com |f| = 5

Importante: nem sempre os caminhos de aumento geram aumentos no fluxo de toda aresta. Considere novamente a rede residual com ∣f∣=3|f| = 3. O caminho s→2v2→1v4→1v3→2ts \xrightarrow{2} v_2 \xrightarrow{1} v_4 \xrightarrow{1} v_3 \xrightarrow{2} t usa a aresta (v4,v3)(v_4,v_3) (tracejada na figura), que não existe em GG: aplicá-lo equivale a desistir de enviar 1 unidade em (v3,v4)(v_3,v_4) para que uma unidade a mais possa ser enviada em (v4,t)(v_4,t). A rede residual resultante tem ∣f∣=4|f| = 4:

Caminho de aumento s → v2 → v4 → v3 → t, com a aresta de cancelamento (v4, v3) tracejada, e a rede residual resultante, com f = 4

Caminho de aumento s → v2 → v4 → v3 → t, com a aresta de cancelamento (v4, v3) tracejada, e a rede residual resultante, com |f| = 4


5.9.4 Método de Ford-Fulkerson

O método de Ford-Fulkerson consiste em aumentar ∣f∣|f| enquanto houver caminho de aumento:

ford-fulkerson(G, s, t)
// argumentos:
// G: rede de fluxo com vértices V e arestas E
// s: vértice fonte
// t: vértice destino
// ao final, cada aresta contém seu fluxo em e.f

  for each (u, v) in G.E
    (u, v).f = 0                      // fluxo inicial nulo
  G_f = rede residual a partir de G
  while existe caminho de aumento p em G_f de s a t
    delta = min { c_f(u, v) : (u, v) in p }
    for each (u, v) in p
      e = (u, v)
      if e in G.E
        e.f = e.f + delta
      else
        e = (v, u)
        e.f = e.f - delta
    atualize a rede residual G_f ao longo do caminho p

Quanto à complexidade, construir a rede residual GfG_f custa O(m)O(m), pois o grafo é conexo, e encontrar um caminho de aumento pp custa O(m)O(m) (uma busca); assim, cada iteração do laço custa O(m)O(m). No pior caso, o fluxo ∣f∣|f| aumenta de 1 em 1 até atingir o fluxo máximo, denotado ∣f∗∣|f^*|. A conclusão é que o método custa, no total, O(∣f∗∣ m)O(|f^*| \, m).


5.9.5 Algoritmo de Edmonds-Karp

O custo O(∣f∗∣ m)O(|f^*| \, m) pode ser ruim. Na rede abaixo, o que acontece se a aresta (v1,v2)(v_1,v_2), de capacidade 1, for escolhida a cada passo nos caminhos de aumento? Os caminhos alternam entre s→v1→v2→ts \to v_1 \to v_2 \to t e s→v2→v1→ts \to v_2 \to v_1 \to t, cada um com Δ=1\Delta = 1, e são necessárias 200 iterações para atingir o fluxo máximo ∣f∗∣=200|f^*| = 200.

Rede em que uma escolha ruim de caminhos de aumento torna o método lento: a aresta de capacidade 1 está destacada

Rede em que uma escolha ruim de caminhos de aumento torna o método lento: a aresta de capacidade 1 está destacada

Como melhorar? Adicionar critérios para a escolha do caminho de aumento a cada passo, o que afeta apenas a escolha de pp no laço do método.

O algoritmo de Edmonds-Karp escolhe, a cada iteração, o caminho de aumento com menor quantidade de arestas (menor comprimento), encontrado por uma busca em largura na rede residual.

Quanto à complexidade: o comprimento dos caminhos mínimos nunca decresce de uma iteração para outra, pois a cada iteração uma das arestas fica à sua capacidade máxima (saturada). Se o comprimento nunca decresce, então, para cada aresta (u,v)(u,v), o tamanho de um caminho mínimo que alcança vv não pode ultrapassar o tamanho máximo para tais caminhos, que ocorre quando não repetimos vértices (sem ciclos). Como isso vale para qualquer aresta (u,v)(u,v), cada aresta fica saturada, no máximo, O(n)O(n) vezes; portanto, há no máximo O(mn)O(mn) iterações, pois cada uma das mm arestas satura O(n)O(n) vezes. Como O(m)O(m) é o custo de encontrar os caminhos e atualizar GfG_f, a conclusão é O(m2n)O(m^2 n).


5.9.6 Execução passo a passo

Vamos executar o algoritmo sobre o exemplo clássico do CLRS 3ed. (capítulo 26). Inicialmente, todos os fluxos são 0, de modo que a rede residual GfG_f é exatamente o próprio GG. A figura abaixo mostra a rede residual após cada iteração; em cada painel, o caminho de aumento encontrado naquela rede residual está destacado:

Execução passo a passo: rede residual inicial e redes residuais após cada uma das três iterações

Execução passo a passo: rede residual inicial e redes residuais após cada uma das três iterações

Após a terceira iteração, a rede residual não possui caminho de aumento, e o fluxo abaixo, com ∣f∗∣=23|f^*| = 23, é máximo:

Fluxo máximo da rede de exemplo, com f* = 23

Fluxo máximo da rede de exemplo, com |f*| = 23


5.9.7 Fluxo máximo e corte mínimo

Um corte (S,T)(S,T) de GG é uma partição de VV, isto é, S∪T=VS \cup T = V e S∩T=∅S \cap T = \emptyset, com s∈Ss \in S e t∈Tt \in T. A capacidade do corte considera apenas as arestas que vão de SS para TT:

c(S,T)=∑u∈S∑v∈Tc(u,v)c(S,T) = \sum_{u \in S} \sum_{v \in T} c(u,v)

O fluxo através do corte é o fluxo líquido de SS para TT, em que as arestas de TT para SS contam negativamente; ele é sempre igual ao valor do fluxo: f(S,T)=∣f∣f(S,T) = |f|.

Teorema (fluxo máximo / corte mínimo). As seguintes afirmações são equivalentes (CLRS 3ed., capítulo 26):

Em particular, qualquer corte limita superiormente o valor do fluxo: ∣f∣≤c(S,T)|f| \le c(S,T).

Cortes em uma rede: à esquerda, um fluxo não ótimo limitado por um corte de capacidade 26; à direita, o fluxo ótimo, que atinge o corte mínimo, de capacidade 23

Cortes em uma rede: à esquerda, um fluxo não ótimo limitado por um corte de capacidade 26; à direita, o fluxo ótimo, que atinge o corte mínimo, de capacidade 23

Exemplo (fluxo não ótimo). No painel da esquerda, o fluxo tem ∣f∣=19|f| = 19 e o corte tracejado separa S={s,v1,v2}S = \{s, v_1, v_2\} de T={v3,v4,t}T = \{v_3, v_4, t\}: as arestas (v1,v3)(v_1,v_3) e (v2,v4)(v_2,v_4) vão de SS para TT, e a aresta (v3,v2)(v_3,v_2) vai de TT para SS. Portanto, f(S,T)=(12+11)−4=19f(S,T) = (12 + 11) - 4 = 19 e c(S,T)=12+14=26c(S,T) = 12 + 14 = 26. Como ∣f∣<c(S,T)|f| < c(S,T) e ainda há caminhos de aumento, esse fluxo não é máximo.

Exemplo (fluxo ótimo). No painel da direita, o fluxo f∗f^*, com ∣f∗∣=23|f^*| = 23, atinge a capacidade de um corte: para S∗={s,v1,v2,v4}S^* = \{s, v_1, v_2, v_4\} e T∗={v3,t}T^* = \{v_3, t\}, as arestas de S∗S^* para T∗T^* são (v1,v3)(v_1,v_3), (v4,v3)(v_4,v_3) e (v4,t)(v_4,t), de modo que c(S∗,T∗)=12+7+4=23=∣f∗∣c(S^*,T^*) = 12 + 7 + 4 = 23 = |f^*|. Esse é o corte mínimo da rede: o valor do fluxo máximo é exatamente a capacidade do corte mínimo.


5.10 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.10.1 Definições importantes


5.10.2 Grafos eulerianos

Teorema 5.1. Um grafo G=(V,E)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.

Algoritmo de Fleury

CICLO-EULERIANO-FLEURY(G(V, E))
// argumentos:
// G(V, E): grafo euleriano com vértices V e arestas E

seja s in V um vértice inicial qualquer
u = s // vértice corrente no percurso
while existirem arestas no grafo
   if d(u) == 1 // grau de u
      escolha a única aresta possível (u, v) in E
   else
      escolha (u, v) in E tal que mesmo que (u, v) seja removida,
                       s continua na mesma componente do restante das arestas
   adicione (u, v) ao percurso
   remova a aresta (u, v) do grafo
   u = v
retorne a sequência de arestas

Algoritmo de Hierholzer

O algoritmo de Hierholzer é uma alternativa ao de Fleury, oferecendo uma abordagem mais eficiente para encontrar ciclos eulerianos. Em vez de verificar se uma aresta é uma ponte a cada passo (operação custosa), Hierholzer utiliza uma pilha (stack) para explorar arestas de forma sistemática. A ideia central é seguir arestas até formar um ciclo fechado, depois retroceder e continuar de vértices que ainda possuem arestas não utilizadas.

Complexidade: O(n + m) para grafos implementados com lista de adjacência e marcação de arestas via set.

CICLO-EULERIANO-HIERHOLZER(G(V, E))
// argumentos:
// G: grafo euleriano com vértices V e lista de adjacências G.AdjList

  seja s in V um vértice inicial qualquer
  G' = copy of G
  S = stack vazio
  C = lista vazia
  push(S, s)
  while S nao-vazio
    u = top(S)
    if G'.AdjList[u] is not empty
      v = remove first edge from G'.AdjList[u]
      remove edge (v, u) from G'.AdjList[v]
      push(S, v)
    else
      pop(S)
      append(C, u)
  return reverse(C)

Análise de complexidade de Fleury vs. Hierholzer

Hierholzer: O(n + m)

Comparação com Fleury: O(n + m) vs O(m²)

O algoritmo de Fleury possui complexidade O(m⋅(n+m))O(m \cdot (n + m)), que em grafos densos reduz-se a O(m2)O(m^2). A razão reside na verificação de ponte a cada iteração: para evitar remover uma aresta que desconecta o grafo, Fleury deve testar se a aresta é crítica (uma operação que requer DFS ou BFS, custando O(n+m)O(n + m)). Como Fleury executa mm iterações, o custo total é O(m⋅(n+m))O(m \cdot (n + m)). Hierholzer evita completamente essa verificação ao remover arestas conforme as utiliza, eliminando a possibilidade de ficar preso.

Implementação eficiente de remoção em O(1)O(1):

Para remover arestas da lista de adjacência em tempo O(1)O(1) amortizado (sem busca linear), use uma das estratégias:

  1. Ponteiros bidireciais (forward/backward links): Cada aresta (u,v)(u, v) armazena referências para sua posição em G.AdjList[u] e sua aresta reversa em G.AdjList[v]. Remover é então atualizar ponteiros (similar a remoção de nó em lista ligada duplamente).

  2. Índices com marcação: Manter um array paralelo marked[] que marca arestas como removidas. Ao iterar G.AdjList[u], pule arestas marcadas. A cópia inicial custa O(n+m)O(n + m), e cada remoção é O(1)O(1).

Algoritmos para o problema do carteiro chinês

Se trata de um problema de otimização associado ao problema de encontrar ciclos eulerianos. A premissa principal é que se tenha um grafo ponderado, não necessariamente euleriano, com o objetivo de encontrar uma trilha fechada de menor custo. Existe uma sutileza aqui: se o grafo não é euleriano precisamos “repetir” arestas para completar a trilha fechada e, por isso, repetindo o custo daquela aresta específica. A ideia é ser capaz de encontrar essa trilha de forma a minimizar o custo total do passeio.

CARTEIRO-CHINES(G(V, E))
// argumentos:
// G(V, E): grafo com vértices V e arestas E

if G nao-euleriano
   seja I o subconjunto de V dos vertices de grau impar
   for each u in I
      descubra os caminhos minimos d_uv a partir de u // usando Dijkstra, por exemplo
      d_uu = infinity
   P = pares de vertices u, v in I cuja soma das distancias d_uv seja minima // Algoritmo hungaro
   for each (u, v) in P
      adicionar aresta artificial (u, v) em G com custo d_uv
C = CICLO-EULERIANO-FLEURY(G(V, E))
for each aresta artificial (u, v) in C
   substitua em C a aresta (u, v) pelo caminho minimo u -> v
retorne C
CARTEIRO-CHINES-DIRECIONADO(G(V, E))
// argumentos:
// G(V, E): grafo direcionado com vértices V e arestas E

if G nao-euleriano
   seja S o subconjunto de V dos vertices u tal que d+(u) - d-(u) > 0
   seja T o subconjunto de V dos vertices u tal que d+(u) - d-(u) < 0
   for each u in S
      descubra os caminhos minimos d_uv a partir de u para todo v in T // Algoritmo Dijkstra
      d_uu = infinity
   S' = REPLICA-VERTICES(S) // w^(u) denota uma copia de u in S
   T' = REPLICA-VERTICES(T) // w^(u) denota uma copia de u in T
   PREENCHE-DISTANCIAS-REPLICAS(S', T', S, T)
   P = pares u in (S union S'), v in (T union T') cuja soma das distancias d_uv seja minima // Algoritmo hungaro
   for each (w, z) in P
      if w e replica w^(r) entao u = r senao u = w
      if z e replica z^(r) entao v = r senao v = z
      adicionar aresta artificial (u, v) em G com custo d_uv
C = CICLO-EULERIANO-FLEURY(G(V, E))
for each aresta artificial (u, v) in C
   substitua em C a aresta (u, v) pelo caminho minimo u -> v
retorne C
REPLICA-VERTICES(V)
// argumentos:
// V: conjunto de vértices

V' = {}
for each u in V
   for i = 2 to |d+(u) - d-(u)|
      seja w^(u) uma copia de u
      V' = V' union {w^(u)}
retorne V'
PREENCHE-DISTANCIAS-REPLICAS(S', T', S, T)
// argumentos:
// S', T': conjuntos de vértices replicados
// S, T: conjuntos de vértices originais

for each w^(u) in S'
   for each z^(v) in T'
      d_{w^(u)z^(v)} = d_uv
for each w^(u) in S'
   for each v in T
      d_{w^(u)v} = d_uv
for each u in S
   for each z^(v) in T'
      d_{uz^(v)} = d_uv

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


5.10.3 Grafos hamiltonianos

Um ciclo hamiltoniano é um ciclo que visita cada vértice do grafo exatamente uma vez, retornando ao vértice de partida. Diferentemente dos ciclos eulerianos, para os quais existe uma caracterização simples (teorema 5.1), não se conhece condição necessária e suficiente simples para a existência de ciclos hamiltonianos: o problema de decisão é NP-completo. Uma variante de otimização é o problema do caixeiro viajante (PCV): dado um grafo ponderado, encontrar o ciclo hamiltoniano de menor custo total. No PCV assume-se que o grafo é completo: toda aresta que não existia originalmente é acrescentada com custo infinito (ou suficientemente grande), de modo que um ciclo de custo mínimo sempre evita tais arestas, salvo quando o grafo original não possui ciclo hamiltoniano algum.

Uma abordagem exata para o PCV é a busca por backtracking: a partir de um vértice inicial fixo ss, o algoritmo estende recursivamente um caminho elementar (sem repetição de vértices), mantendo o custo do melhor ciclo completo encontrado até o momento. Quando o caminho corrente contém todos os nn vértices, ele é fechado com a aresta de volta a ss, formando um ciclo candidato a solução ótima. Ao retornar de cada chamada recursiva, a marcação do vértice é desfeita, permitindo que ele participe de outros caminhos.

pcv-backtracking(G, u, s, visited, d)
// argumentos:
// G: grafo ponderado completo com vértices V e listas de adjacências G.AdjList,
//    com n = |V| e w(u, v) o peso da aresta (u, v)
//    (arestas inexistentes no grafo original têm w = infinity)
// u: vértice corrente do caminho sendo construído
// s: vértice inicial do ciclo (fixo)
// visited: vetor booleano de tamanho n, inicialmente todo false
// d: quantidade de arestas no caminho corrente de s até u

  visited[u] = true
  if d == n - 1
     visited[u] = false
     return (w(u, s), [s])
  mincost = infinity
  bestpath = NIL
  for each v in G.AdjList[u]
     if visited[v] == false
        (cost, path) = pcv-backtracking(G, v, s, visited, d + 1)
        if cost + w(u, v) < mincost
           mincost = cost + w(u, v)
           bestpath = [v] concatenado com path
  visited[u] = false
  return (mincost, bestpath)

Como o grafo é completo, todo caminho elementar com nn vértices pode ser fechado em um ciclo: arestas artificiais contribuem com custo infinito e naturalmente nunca aparecem na solução de custo mínimo, a menos que o grafo original não admita ciclo hamiltoniano. Assim, não é preciso testar a existência da aresta de fechamento nem a validade do caminho retornado: as comparações de custo fazem esse papel.

A chamada inicial é pcv-backtracking(G, s, s, visited, 0) para um vértice ss qualquer, com visited[u] = false para todo uu in VV. O retorno é o par (custo, caminho) do ciclo hamiltoniano mínimo; se o custo for infinito, o grafo original não possui ciclo hamiltoniano.

Exemplo de execução

Considere o grafo completo de 4 vértices abaixo, com os pesos indicados nas arestas:

Grafo completo de 4 vértices com pesos nas arestas

Grafo completo de 4 vértices com pesos nas arestas

A figura a seguir mostra a árvore de recursão do algoritmo a partir do vértice s=1s = 1, explorando os vizinhos em ordem crescente de rótulo. Cada nível corresponde a uma profundidade dd do caminho sendo construído, e as arestas da árvore são anotadas com o peso da aresta percorrida no grafo. As folhas representam o fechamento do ciclo com a aresta de volta a 1, com o custo total anotado abaixo de cada uma. Os vértices em vermelho formam o ciclo de custo mínimo: 1→2→4→3→11 \to 2 \to 4 \to 3 \to 1, com custo 5+1+3+2=115 + 1 + 3 + 2 = 11. Note que o primeiro ramo explorado pela busca (1→2→3→4→11 \to 2 \to 3 \to 4 \to 1, custo 24) não é o ótimo, que só é descoberto no ramo seguinte.

Árvore de recursão do pcv-backtracking

Árvore de recursão do pcv-backtracking

O segundo exemplo ilustra o papel das arestas artificiais. Considere o grafo de 5 vértices abaixo, que não é completo (não existem as arestas (1,3)(1,3), (1,4)(1,4) e (2,5)(2,5)):

Grafo de 5 vértices não completo com pesos nas arestas

Grafo de 5 vértices não completo com pesos nas arestas

Como o PCV assume o grafo completo, o algoritmo explora normalmente os vértices ausentes como vizinhos, mas qualquer ramo que usa uma aresta artificial acumula custo infinito. Na árvore de recursão abaixo, esses ramos aparecem anotados com ∞\infty: das 4!=244! = 24 permutações, apenas 4 correspondem a ciclos com custo finito no grafo original. Os vértices em vermelho indicam o ciclo de custo mínimo, 1→2→4→3→5→11 \to 2 \to 4 \to 3 \to 5 \to 1, com custo 1+1+3+1+5=111 + 1 + 3 + 1 + 5 = 11. O primeiro ramo completamente explorado, 1→2→3→4→5→11 \to 2 \to 3 \to 4 \to 5 \to 1, tem custo 18.

Árvore de recursão do pcv-backtracking para grafo não completo

Árvore de recursão do pcv-backtracking para grafo não completo

Complexidade: no pior caso, a partir do vértice inicial o algoritmo explora todas as permutações dos n−1n - 1 vértices restantes, isto é, (n−1)!(n - 1)! caminhos candidatos. Como cada caminho é processado em tempo polinomial, a complexidade total é O(n!)O(n!) no pior caso. Na prática, ramos que acumulam arestas de custo infinito deixam de ser competitivos cedo nas comparações, mas o crescimento fatorial inviabiliza instâncias grandes, o que motiva o uso de podas (branch and bound), programação dinâmica ou heurísticas aproximadas.


5.10.4 PCV com podas (branch and bound)

O backtracking puro da seção anterior só compara custos de ciclos completos: um ramo que já acumulou um custo parcial maior que o melhor ciclo conhecido continua sendo explorado até o fim. A versão com podas elimina esse desperdício com duas mudanças:

  1. o algoritmo passa a carregar o custo parcial cc do caminho s⇝us \rightsquigarrow u construído até o momento;

  2. o melhor custo conhecido é mantido em uma variável global bestbest, compartilhada por todas as chamadas: sempre que um ciclo completo melhor é encontrado, bestbest é atualizado imediatamente, e qualquer chamada cujo custo parcial já atingiu bestbest é interrompida na hora (poda), pois nenhuma extensão desse caminho pode melhorar a solução (os pesos são não negativos).

best = infinity    // variável global: custo do melhor ciclo conhecido
bestcycle = NIL    // variável global: melhor ciclo conhecido

pcv-backtracking-poda(G, u, s, visited, d, c)
// argumentos:
// G: grafo ponderado completo com vértices V e listas de adjacências G.AdjList,
//    com n = |V| e w(u, v) o peso da aresta (u, v)
//    (arestas inexistentes no grafo original têm w = infinity)
// u: vértice corrente do caminho sendo construído
// s: vértice inicial do ciclo (fixo)
// visited: vetor booleano de tamanho n, inicialmente todo false
// d: quantidade de arestas no caminho corrente de s até u
// c: custo acumulado do caminho de s até u

  visited[u] = true
  if d == n - 1
     if c + w(u, s) < best
        best = c + w(u, s)
        bestcycle = caminho de s até u concatenado com [s]  // recuperável com vetor de predecessores
     visited[u] = false
     return
  for each v in G.AdjList[u]
     if visited[v] == false
        if c + w(u, v) < best    // poda: ramo não pode melhorar o melhor ciclo
           pcv-backtracking-poda(G, v, s, visited, d + 1, c + w(u, v))
  visited[u] = false

A chamada inicial é pcv-backtracking-poda(G, s, s, visited, 0, 0); ao final, best e bestcycle guardam a solução (com best = infinity se não houver ciclo hamiltoniano no grafo original). Dois pontos merecem atenção:

No pior caso nenhuma poda ocorre e a complexidade permanece O(n!)O(n!), mas na prática o corte de ramos reduz drasticamente o número de caminhos explorados. O best também pode começar inicializado com o custo de uma solução heurística qualquer (por exemplo, vizinho mais próximo), podando desde a primeira chamada.

Exemplo de execução com podas

A seguir o mesmo exemplo anterior, mas com o algoritmo que usa podas. O pior caso do algoritmo continua sendo percorrer todos os caminhos possíveis.

Árvore de recursão do pcv-backtracking com podas

Árvore de recursão do pcv-backtracking com podas

Árvore de recursão do pcv-backtracking com podas para grafo não completo

Árvore de recursão do pcv-backtracking com podas para grafo não completo


5.10.5 Heurísticas para o PCV

Os métodos exatos vistos até aqui têm complexidade fatorial no pior caso, o que os inviabiliza para instâncias grandes. Uma alternativa prática são as heurísticas construtivas: algoritmos polinomiais que constroem um ciclo hamiltoniano de forma incremental, fazendo escolhas localmente boas, sem garantia de otimalidade. A seguir, três heurísticas clássicas para o PCV, sendo que a proposta de implementação/pseudocódigo fica a cargo do leitor:

Vizinho mais próximo. começamos de um vértice inicial qualquer e, a cada passo, o caminho é estendido para o vértice ainda não visitado mais próximo do vértice corrente. Quando todos os vértices tiverem sido visitados, o ciclo é fechado com a aresta de volta ao vértice inicial. A ideia captura a intuição de que deslocamentos curtos tendem a compor um ciclo barato, mas a escolha míope pode deixar vértices distantes para o final, quando não há mais alternativa barata para inseri-los. A complexidade é O(n2)O(n^2) (tem como melhorar uma implementação quadrática?).

Inserção mais próxima. ao invés de estender um caminho por uma extremidade, a heurística mantém um ciclo parcial que cresce por inserções. Inicia-se com dois vértices e o ciclo entre eles (ida e volta pela mesma aresta). Enquanto existirem vértices fora do ciclo, escolhe-se o par (vértice não visitado, posição entre dois vértices consecutivos do ciclo corrente) cuja inserção gere o menor custo total do ciclo, isto é, o vértice uu e a aresta (v,w)(v, w) do ciclo que minimizam o acréscimo w(v,u)+w(u,w)−w(v,w)w(v, u) + w(u, w) - w(v, w). O vértice escolhido é inserido entre os dois vértices da posição escolhida, e o processo se repete até que o ciclo contenha todos os vértices. A inserção tende a acomodar cada vértice onde ele “menos atrapalha” o ciclo, o que costuma produzir soluções melhores que o vizinho mais próximo, ao custo de uma complexidade maior, O(n3)O(n^3).

Escolha gulosa de arestas. esta o constrói aresta a aresta. As arestas são consideradas em ordem crescente de peso, e cada aresta é incorporada à solução desde que duas restrições sejam respeitadas: (1) a aresta não pode fechar um ciclo que não contenha todos os vértices (nenhum ciclo prematuro); (2) a aresta não pode dar grau maior que 2 a nenhum vértice (em um ciclo hamiltoniano, todo vértice incide em exatamente duas arestas). As arestas rejeitadas são descartadas, e o processo termina quando nn arestas tiverem sido selecionadas, formando o ciclo. A semelhança com o algoritmo de Kruskal não é coincidência: a ideia é a mesma, mas enquanto Kruskal proíbe qualquer ciclo (buscando uma árvore), aqui apenas ciclos prematuros e graus excessivos são proibidos, pois o objetivo é justamente terminar com um único ciclo. Com arestas pré-ordenadas, a seleção custa O(n2)O(n^2) e a verificação de ciclos pode ser feita com uma estrutura de conjuntos disjuntos (union-find), como em Kruskal.

As três heurísticas são rápidas e fáceis de implementar, mas podem produzir soluções arbitrariamente distantes do ótimo em instâncias adversas. Na prática, elas são úteis tanto como soluções finais aproximadas quanto como ponto de partida: o custo de um ciclo heurístico inicializa a variável best do branch and bound (seção 5.10.4), permitindo podas desde a primeira chamada recursiva.

Exemplo de execução: grafo completo de 4 vértices

O primeiro exemplo é o grafo completo de 4 vértices da seção 5.10.3, cujo ciclo ótimo é 1→2→4→3→11 \to 2 \to 4 \to 3 \to 1 (custo 11). Os passos das três heurísticas, partindo do vértice 1:

Vizinho mais próximo

DecisãoCaminho parcial
aresta (1,3)(1, 3), peso 21→31 \to 3
aresta (3,4)(3, 4), peso 31→3→41 \to 3 \to 4
aresta (4,2)(4, 2), peso 11→3→4→21 \to 3 \to 4 \to 2
fechamento com (2,1)(2, 1), peso 51→3→4→2→11 \to 3 \to 4 \to 2 \to 1 (custo 11)

Inserção mais próxima

DecisãoCiclo parcial
ciclo inicial com os dois vértices mais próximos: (1,3)(1, 3), peso 21→3→11 \to 3 \to 1 (custo 4)
insere 4 entre 1 e 3, acréscimo 8+3−2=98 + 3 - 2 = 91→4→3→11 \to 4 \to 3 \to 1 (custo 13)
insere 2 entre 1 e 4, acréscimo 5+1−8=−25 + 1 - 8 = -21→2→4→3→11 \to 2 \to 4 \to 3 \to 1 (custo 11)

Escolha gulosa de arestas

DecisãoCaminho parcial
aresta (2,4)(2, 4), peso 12→42 \to 4
aresta (1,3)(1, 3), peso 22→42 \to 4, 1→31 \to 3
aresta (3,4)(3, 4), peso 31→3→4→21 \to 3 \to 4 \to 2
aresta (1,2)(1, 2), peso 51→3→4→2→11 \to 3 \to 4 \to 2 \to 1 (custo 11)

No grafo completo, as três heurísticas encontram o ciclo ótimo. Na inserção mais próxima, note o acréscimo negativo do segundo passo: inserir 2 entre 1 e 4 troca a aresta cara (1,4)(1, 4), de peso 8, pelas baratas (1,2)(1, 2) e (2,4)(2, 4).

Exemplo de execução: grafo não completo de 5 vértices

O segundo exemplo é o grafo de 5 vértices da seção 5.10.3 (sem as arestas (1,3)(1,3), (1,4)(1,4) e (2,5)(2,5)), cujo ciclo ótimo é 1→2→4→3→5→11 \to 2 \to 4 \to 3 \to 5 \to 1 (custo 11):

Vizinho mais próximo

DecisãoCaminho parcial
aresta (1,2)(1, 2), peso 11→21 \to 2
aresta (2,4)(2, 4), peso 11→2→41 \to 2 \to 4
aresta (4,3)(4, 3), peso 31→2→4→31 \to 2 \to 4 \to 3
aresta (3,5)(3, 5), peso 11→2→4→3→51 \to 2 \to 4 \to 3 \to 5
fechamento com (5,1)(5, 1), peso 51→2→4→3→5→11 \to 2 \to 4 \to 3 \to 5 \to 1 (custo 11)

Inserção mais próxima

DecisãoCiclo parcial
ciclo inicial com os dois vértices mais próximos: (1,2)(1, 2), peso 11→2→11 \to 2 \to 1 (custo 2)
insere 3 entre 1 e 2, acréscimo ∞\infty (usa a aresta artificial (1,3)(1, 3))1→3→2→11 \to 3 \to 2 \to 1 (custo ∞\infty)
insere 5 entre 1 e 3, eliminando a artificial (1,3)(1, 3)1→5→3→2→11 \to 5 \to 3 \to 2 \to 1 (custo 9)
insere 4 entre 3 e 2, acréscimo 3+1−2=23 + 1 - 2 = 21→5→3→4→2→11 \to 5 \to 3 \to 4 \to 2 \to 1 (custo 11)

Escolha gulosa de arestas

DecisãoCaminho parcial
aresta (1,2)(1, 2), peso 11→21 \to 2
aresta (2,4)(2, 4), peso 11→2→41 \to 2 \to 4
aresta (3,5)(3, 5), peso 11→2→41 \to 2 \to 4, 3→53 \to 5
rejeita (2,3)(2, 3), peso 2: grau de 2 ficaria maior que 21→2→41 \to 2 \to 4, 3→53 \to 5
aresta (3,4)(3, 4), peso 31→2→4→3→51 \to 2 \to 4 \to 3 \to 5
aresta (1,5)(1, 5), peso 51→2→4→3→5→11 \to 2 \to 4 \to 3 \to 5 \to 1 (custo 11)

5.11 Isomorfismo

5.11.1 Isomorfismo de grafos

A palavra vem do grego: isos (igual) e morphe (forma). Dois grafos isomorfos têm a mesma estrutura, diferindo apenas nos nomes dos vértices e no desenho.

Dois grafos G1=(V1,E1)G_1 = (V_1, E_1) e G2=(V2,E2)G_2 = (V_2, E_2) são isomorfos se existe uma função bijetora f:V1→V2f : V_1 \to V_2 tal que:

u,v∈V1u, v \in V_1 são adjacentes em G1G_1 se, e somente se, f(u)f(u) e f(v)f(v) são adjacentes em G2G_2.

Para multigrafos (como no exemplo 2), ff também deve preservar a multiplicidade das arestas entre cada par de vértices.

Para verificar um isomorfismo dado, basta checar que ff é bijetora e que {u,v}∈E1  ⟺  {f(u),f(v)}∈E2\{u,v\} \in E_1 \iff \{f(u), f(v)\} \in E_2. Como ff é bijetora, isso equivale a verificar que ∣E1∣=∣E2∣|E_1| = |E_2| e que toda aresta de G1G_1 é levada em uma aresta de G2G_2.

Exemplo 1: ciclo C5C_5 e pentagrama

G1G_1 é o ciclo C5C_5 (pentágono) com vértices v1,…,v5v_1, \dots, v_5 e arestas (vi,vi+1)(v_i, v_{i+1}), com v6=v1v_6 = v_1. G2G_2 é o pentagrama com vértices a,b,c,d,ea, b, c, d, e e arestas (a,c),(c,e),(e,b),(b,d),(d,a)(a,c), (c,e), (e,b), (b,d), (d,a).

Exemplo 1 de isomorfismo: pentágono e pentagrama

Exemplo 1 de isomorfismo: pentágono e pentagrama

Mapeamento: f(v1)=af(v_1) = a, f(v2)=df(v_2) = d, f(v3)=bf(v_3) = b, f(v4)=ef(v_4) = e, f(v5)=cf(v_5) = c.

Verificação das arestas de G1G_1: (v1,v2)↦(a,d)(v_1,v_2) \mapsto (a,d), (v2,v3)↦(d,b)(v_2,v_3) \mapsto (d,b), (v3,v4)↦(b,e)(v_3,v_4) \mapsto (b,e), (v4,v5)↦(e,c)(v_4,v_5) \mapsto (e,c), (v5,v1)↦(c,a)(v_5,v_1) \mapsto (c,a). Todas são arestas de G2G_2, e ambos têm 5 arestas.

Exemplo 2: multigrafos

O grafo da esquerda tem vértices a,b,c,d,ea, b, c, d, e. O vértice aa é adjacente a todos os demais, a,b,ca, b, c formam um triângulo e dd e ee são ligados por duas arestas paralelas. O grafo da direita tem vértices x,y,z,w,vx, y, z, w, v, com zz adjacente a todos os demais, triângulo z,w,vz, w, v e duas arestas paralelas entre xx e yy.

Exemplo 2 de isomorfismo: multigrafos

Exemplo 2 de isomorfismo: multigrafos

Função bijetora: f(a)=zf(a) = z, f(b)=wf(b) = w, f(c)=vf(c) = v, f(d)=xf(d) = x, f(e)=yf(e) = y. As arestas (a,b),(a,c),(b,c)(a,b), (a,c), (b,c) vão em (z,w),(z,v),(w,v)(z,w), (z,v), (w,v), as arestas (a,d),(a,e)(a,d), (a,e) vão em (z,x),(z,y)(z,x), (z,y) e as duas arestas (d,e)(d,e) vão nas duas arestas (x,y)(x,y).

Exemplo 3: o grafo do cubo

À esquerda, o cubo é desenhado com um quadrado externo a,b,c,da, b, c, d e um quadrado interno g,f,e,hg, f, e, h (ambos em sentido horário), ligados pelas arestas (a,g),(b,f),(c,e),(d,h)(a,g), (b,f), (c,e), (d,h). À direita, o mesmo grafo é desenhado com os quadrados lado a lado.

Exemplo 3 de isomorfismo: duas representações do cubo

Exemplo 3 de isomorfismo: duas representações do cubo

Função bijetora: f(a)=bf(a) = b, f(b)=df(b) = d, f(c)=hf(c) = h, f(d)=gf(d) = g, f(e)=jf(e) = j, f(f)=if(f) = i, f(g)=ff(g) = f, f(h)=af(h) = a.

As 12 arestas do grafo da esquerda são levadas em:

aresta em G1G_1imagem em G2G_2
(a,b),(b,c),(c,d),(d,a)(a,b), (b,c), (c,d), (d,a)(b,d),(d,h),(h,g),(g,b)(b,d), (d,h), (h,g), (g,b)
(g,f),(f,e),(e,h),(h,g)(g,f), (f,e), (e,h), (h,g)(f,i),(i,j),(j,a),(a,f)(f,i), (i,j), (j,a), (a,f)
(a,g),(b,f),(c,e),(d,h)(a,g), (b,f), (c,e), (d,h)(b,f),(d,i),(h,j),(g,a)(b,f), (d,i), (h,j), (g,a)

Esse conjunto é exatamente o conjunto de arestas do grafo da direita (dois quadrados f,b,d,if,b,d,i e a,g,h,ja,g,h,j, ligados por (f,a),(b,g),(d,h),(i,j)(f,a), (b,g), (d,h), (i,j)), o que confirma o isomorfismo.

Invariantes de isomorfismo

Se G1G_1 e G2G_2 são isomorfos, então ambos satisfazem simultaneamente:

  1. mesmo número de vértices, ∣V1∣=∣V2∣|V_1| = |V_2|;

  2. mesmo número de arestas, ∣E1∣=∣E2∣|E_1| = |E_2|;

  3. mesma sequência de graus (mesma quantidade de vértices de grau kk, para todo kk);

  4. mesma quantidade de ciclos de cada tamanho kk;

  5. mesma conectividade (ambos conexos, ou o mesmo número de componentes conexas);

  6. existência (ou ausência) de circuito euleriano e de ciclo hamiltoniano;

  7. para todo subgrafo S1⊆G1S_1 \subseteq G_1, existe um subgrafo de G2G_2 isomorfo a S1S_1.

Essas propriedades são condições necessárias, mas não suficientes. Se alguma delas falha, os grafos não são isomorfos. Se todas as testadas passam, nada se conclui.

5.11.2 Algoritmo de força bruta

Este algoritmo é para grafos simples e não direcionados (sem laços, sem arestas paralelas e sem orientação). Para esses grafos, com vértices numerados 1,…,n1, \dots, n, testamos todas as bijeções f:V1→V2f : V_1 \to V_2 (as n!n! permutações). Os invariantes mais baratos (números de vértices e de arestas, sequência de graus) servem de filtro inicial.

Para uma bijeção ff fixada (a rotina valid-iso confere explicitamente que ff é injetora e que suas imagens estão em V2V_2), basta verificar que toda aresta de G1G_1 é levada em uma aresta de G2G_2. Como ∣E1∣=∣E2∣|E_1| = |E_2|, ff leva as arestas de G1G_1 em arestas distintas de G2G_2 e, portanto, em todas elas. Sem a igualdade do número de arestas, essa verificação aceitaria um subgrafo de G2G_2 como se fosse isomorfo a G2G_2 (por exemplo, um grafo sem arestas e KnK_n).

graph-iso(G1, G2)
// argumentos:
// G1: grafo simples e não direcionado com vértices 1..n e arestas E1
// G2: grafo simples e não direcionado com vértices 1..n e arestas E2

  if |G1.V| != |G2.V| or |G1.E| != |G2.E|
    return NIL
  if degree-sequence(G1) != degree-sequence(G2)
    return NIL
  for each permutation f of 1..n
    if valid-iso(G1, G2, f)
      return f
  return NIL

valid-iso(G1, G2, f)
// argumentos:
// G1, G2: grafos simples e não direcionados, com o mesmo número de vértices e de arestas
// f: mapeamento de G1.V em G2.V, com f[u] sendo a imagem de u

  // f deve ser bijetora: cada vértice de G2 é imagem de exatamente um vértice de G1
  for each x in G2.V
    used[x] = false
  for each u in G1.V
    if f[u] not in G2.V or used[f[u]]
      return false
    used[f[u]] = true
  // adjacências: toda aresta de G1 deve ser levada em uma aresta de G2
  for each u in G1.V
    for each v in G1.AdjList[u]
      if f[v] not in G2.AdjList[f[u]]
        return false
  return true

Aqui degree-sequence(G) devolve os graus dos vértices de GG em ordem não crescente.

No pior caso, são testadas n!n! permutações, cada uma em tempo O(n+m)O(n + m) se o teste de pertinência a G2.AdjList for feito em tempo constante (por exemplo, consultando a matriz de adjacências de G2G_2), totalizando O(n!⋅(n+m))O(n! \cdot (n + m)). Não se conhece algoritmo polinomial para o problema em geral. Na prática, algoritmos como VF2, VF2++ e nauty podam a árvore de busca usando invariantes locais a cada passo.

5.11.3 Invariantes não bastam: prisma triangular e K3,3K_{3,3}

Considere o prisma triangular G1G_1 (dois triângulos {1,2,3}\{1,2,3\} e {4,5,6}\{4,5,6\} ligados pelas arestas (1,4),(2,5),(3,6)(1,4), (2,5), (3,6)) e o grafo bipartido completo K3,3K_{3,3} G2G_2 (todo vértice de {1,2,3}\{1,2,3\} adjacente a todo vértice de {4,5,6}\{4,5,6\}).

Prisma triangular e K3,3

Prisma triangular e K3,3

InvarianteG1G_1 (prisma)G2G_2 (K3,3K_{3,3})Igual?
Vértices66sim
Arestas99sim
Sequência de graus(3,3,3,3,3,3)(3,3,3,3,3,3)(3,3,3,3,3,3)(3,3,3,3,3,3)sim
Conectividadeconexoconexosim
Ciclo hamiltonianosim, 1,2,3,6,5,4,11,2,3,6,5,4,1sim, 1,4,2,5,3,6,11,4,2,5,3,6,1sim
Ciclos de tamanho 4simsimsim
Ciclos de tamanho 3sim, 1,2,3,11,2,3,1nãonão
Planaridadeplanarnão planarnão

Todos os invariantes básicos coincidem, mas os grafos não são isomorfos: G2G_2 é bipartido, logo só tem ciclos de tamanho par e nenhum triângulo, enquanto G1G_1 tem o triângulo {1,2,3}\{1,2,3\}. Isso viola o invariante 4 (e o 7, pois o triângulo é um subgrafo de G1G_1 sem correspondente em G2G_2).

Há ainda uma diferença mais profunda: G1G_1 pode ser desenhado no plano sem cruzamento de arestas (é planar), enquanto K3,3K_{3,3} não pode. Esse é um dos grafos proibidos do teorema de Kuratowski, assunto da próxima seção.

Aplicação: moléculas como grafos. Uma molécula é naturalmente um grafo: átomos são vértices (rotulados pelo elemento) e ligações químicas são arestas; duas estruturas representam a mesma molécula se, e somente se, seus grafos moleculares são isomorfos. Bancos de dados químicos decidem isso em escala de milhões de compostos: no ChEMBL, do EMBL-EBI, um banco curado de moléculas bioativas com propriedades de fármacos, cada composto recebe uma representação canônica (como o InChI), e a busca por identidade se reduz a comparar essas representações. A busca por estrutura que orienta o desenvolvimento de fármacos é uma variação ainda mais geral do problema desta seção: encontrar todas as moléculas que contêm um dado esqueleto químico (por exemplo, um anel benzênico) é o isomorfismo de subgrafos, em que queremos saber quais grafos do banco contêm o grafo de consulta.

5.12 Planaridade

Em muitas aplicações, o cruzamento de arestas tem algum custo ou relevância (construção de circuitos impressos, desenho de grafos, mapas). Um grafo é planar se pode ser representado no plano sem nenhum cruzamento de arestas. Planaridade é uma propriedade do grafo, não do desenho: um mesmo grafo planar pode ter desenhos com cruzamentos.

Exemplos de grafos planares

Exemplos de grafos planares

Os quatro desenhos acima mostram grafos planares: o ciclo C4C_4, o grafo completo K4K_4, o cubo e novamente K4K_4 desenhado com um cruzamento (basta redesenhá-lo sem cruzamentos, como no segundo painel).

O exemplo clássico de grafo que não é planar é o problema das três casas e três serviços (gás, água e energia): é possível ligar cada casa a cada serviço sem que as ligações se cruzem? Isso equivale a desenhar K3,3K_{3,3} sem cruzamentos.

Problema das casas e serviços

Problema das casas e serviços

Para praticar a intuição, o jogo Planarity, de Jason Davies, apresenta grafos planares desenhados com cruzamentos e pede que o jogador arraste os vértices até que nenhuma aresta se cruze. Ele também oferece variantes em que o grafo é desenhado no cilindro, na faixa de Möbius, no toro e na garrafa de Klein.

5.12.1 Faces e fórmula de Euler

Um desenho planar divide o plano em regiões chamadas faces, incluindo a face externa (ilimitada). No cubo, há 6 faces: a interna (1), as quatro laterais (2 a 5) e a externa (6).

Faces do cubo

Faces do cubo

Teorema de Euler. Se GG é um grafo planar conexo com nn vértices, mm arestas e ff faces, então

n−m+f=2.n - m + f = 2.

No cubo, 8−12+6=28 - 12 + 6 = 2.

Exemplo. Se um grafo planar conexo possui 30 vértices, todos de grau 3, quantas faces ele tem? Como a soma dos graus é 2m2m, temos m=30⋅3/2=45m = 30 \cdot 3 / 2 = 45. Pela fórmula de Euler, 30−45+f=230 - 45 + f = 2, logo f=17f = 17.

5.12.2 Teoremas sobre grafos planares

Teorema 1. Se GG é um grafo planar simples com n≥3n \ge 3 vértices e mm arestas, então m≤3n−6m \le 3n - 6.

Ideia da prova (para GG conexo). Em um grafo simples com n≥3n \ge 3, cada face é delimitada por pelo menos 3 arestas, e cada aresta delimita no máximo 2 faces. Logo 3f≤2m3f \le 2m. Substituindo f≥2−n+mf \ge 2 - n + m pela fórmula de Euler, obtemos 3(2−n+m)≤2m3(2 - n + m) \le 2m, ou seja, m≤3n−6m \le 3n - 6.

Exemplos:

Teorema 2. Se GG é um grafo planar simples, então GG contém um vértice uu com d(u)≤5d(u) \le 5.

Ideia da prova. Se todos os vértices tivessem grau pelo menos 6, teríamos 2m≥6n2m \ge 6n, isto é, m≥3n>3n−6m \ge 3n > 3n - 6, contradizendo o teorema 1. Novamente, K3,3K_{3,3} satisfaz a conclusão (todos os graus são 3) e não é planar.

Teorema 3. K3,3K_{3,3} não é planar.

Ideia da prova. K3,3K_{3,3} é bipartido, logo não tem triângulos, e toda face é delimitada por pelo menos 4 arestas. Então 4f≤2m4f \le 2m, e a fórmula de Euler dá 2=n−m+f≤n−m/22 = n - m + f \le n - m/2, ou seja, m≤2n−4=8m \le 2n - 4 = 8. Mas K3,3K_{3,3} tem 9 arestas.

Teorema 4. K5K_5 não é planar. Isso decorre do teorema 1, como visto acima.

5.12.3 Teorema de Kuratowski

Uma subdivisão elementar de um grafo troca uma aresta (u,v)(u, v) pelas arestas (u,w)(u, w) e (w,v)(w, v), onde ww é um novo vértice. Em outras palavras, o caminho u−vu - v passa a ser u−w−vu - w - v.

Dois grafos G1G_1 e G2G_2 são homeomorfos se podem ser obtidos a partir de um mesmo grafo GG por sucessivas subdivisões elementares. Em particular, um grafo e uma subdivisão dele são homeomorfos.

Teorema de Kuratowski. Um grafo GG é planar se, e somente se, GG não contém subgrafo homeomorfo a K3,3K_{3,3} ou a K5K_5.

Exemplo 1: subgrafo homeomorfo a K5K_5. O grafo GG abaixo tem os vértices a,b,c,g,ia, b, c, g, i, o caminho g−f−e−d−cg - f - e - d - c e os vértices adicionais k,h,jk, h, j (em cinza), ligados por (k,a)(k,a), (k,h)(k,h), (h,j)(h,j) e (j,i)(j,i). Removendo k,h,jk, h, j, obtemos o subgrafo HH, que é K5K_5 em {a,b,c,g,i}\{a, b, c, g, i\} com a aresta (g,c)(g, c) subdividida pelos vértices f,e,df, e, d. Suavizando os vértices de grau 2 (ff, ee e dd), recuperamos K5K_5.

Subgrafo homeomorfo a K5

Subgrafo homeomorfo a K5

Como GG contém um subgrafo homeomorfo a K5K_5, GG não é planar.

Exemplo 2: subgrafo homeomorfo a K3,3K_{3,3}. O grafo GG abaixo, desenhado em formato triangular, tem arestas entre cada vértice de {a,d,f}\{a, d, f\} e cada vértice de {b,c,e}\{b, c, e\}. Redesenhado com as duas partições em linhas, vemos que é exatamente K3,3K_{3,3} (e, portanto, isomorfo a ele). GG não é planar.

Grafo redesenhado como K3,3

Grafo redesenhado como K3,3

Exemplo 3: grafo de Petersen. O grafo de Petersen tem um pentágono externo a,b,c,d,ea, b, c, d, e e uma estrela interna f,g,h,i,jf, g, h, i, j, ligados pelas arestas (a,f),(b,g),(c,h),(d,i),(e,j)(a,f), (b,g), (c,h), (d,i), (e,j). Tomando as partições {f,j,d}\{f, j, d\} e {e,i,h}\{e, i, h\} e usando os vértices aa (entre ff e ee), gg (entre jj e ii) e cc (entre dd e hh) como vértices de subdivisão, obtemos um subgrafo homeomorfo a K3,3K_{3,3}. O vértice bb e suas arestas (a,b)(a,b), (b,c)(b,c), (b,g)(b,g) (tracejadas) não fazem parte do subgrafo. Logo, o grafo de Petersen não é planar.

Subgrafo do grafo de Petersen homeomorfo a K3,3

Subgrafo do grafo de Petersen homeomorfo a K3,3

5.12.4 Grafo dual

Dado um grafo planar GG (com um desenho planar fixado), o grafo dual G∗G^* é construído assim:

  1. Cada face de GG vira um vértice de G∗G^*.

  2. a) Para cada aresta de GG que separa duas faces distintas, há em G∗G^* uma aresta entre os vértices dessas faces. b) Para cada aresta de GG que não separa duas faces distintas (a mesma face está dos dois lados), há em G∗G^* um laço no vértice dessa face.

Note que G∗G^* pode ter arestas paralelas e laços, isto é, é em geral um multigrafo.

Exemplo 1: triângulo com duas arestas pendentes. GG é um triângulo com uma aresta pendente para dentro (face 1) e outra para fora (face 2). O dual G∗G^* tem dois vértices, 1 e 2:

Dual do triângulo com arestas pendentes

Dual do triângulo com arestas pendentes

Conferência: GG tem 5 vértices, 5 arestas e 2 faces (5−5+2=25 - 5 + 2 = 2), e G∗G^* tem 2 vértices e 5 arestas, uma por aresta de GG.

Exemplo 2: K4K_4. GG é K4K_4 desenhado como um triângulo com um vértice central, o que produz 4 faces triangulares: as internas 1,2,31, 2, 3 e a externa 4. Como duas faces quaisquer compartilham exatamente uma aresta, G∗G^* tem os 4 vértices ligados dois a dois, isto é, G∗G^* é isomorfo a K4K_4. Dizemos que K4K_4 é autodual.

Dual de K4

Dual de K4