Graph Labs

Referência dos algoritmos

Pseudocódigo, invariantes e erros comuns de cada método implementado no estúdio, na mesma notação usada em sala. É exatamente essa formulação que a simulação executa passo a passo.

Busca em grafos

Busca em Profundidade

Escolhe sempre o vértice marcado mais recentemente alcançado, registrando tempo de descoberta TD e tempo de término TT.

O(n + m)

Ideia central

Busca genérica em que, dentre todos os vértices marcados e incidentes a alguma aresta ainda não explorada, escolhe-se sempre o mais recentemente alcançado. Cada vértice recebe um tempo de descoberta TD[v] e um tempo de término TT[v], marcados por um contador global t.

Invariante

Os intervalos de vida I(v) = [TD[v], TT[v]] são encaixados ou disjuntos, nunca se cruzam parcialmente. O vértice w é descendente de v se e somente se I(w) está contido em I(v).

Requisitos do grafo

Aceita arestas direcionadas e não direcionadasEm grafo não direcionado: arestas de árvore e de retornoEm grafo direcionado: árvore, retorno, avanço e cruzamento

Erros comuns

  • Em grafo não direcionado só existem arestas de árvore e de retorno; avanço e cruzamento só aparecem em grafo direcionado.
  • Esquecer a condição w ≠ pai[v]: a aresta usada para chegar em v não é aresta de retorno.
  • Toda aresta de retorno evidencia um ciclo no grafo original. Em grafo direcionado, ela é a única evidência necessária.
Inicialização / Chamada inicial
  t ← 0
  para todo vértice v ∈ V(G) faça
    TD[v] ← 0; TT[v] ← 0; pai[v] ← nulo
  enquanto existir algum vértice v tal que TD[v] = 0 efetuar
    Executar Busca_Profundidade(v)   // v é a raiz da busca
 
Busca_Profundidade(v)                 // grafo não direcionado
  t ← t + 1; TD[v] ← t
  para todo vértice w ∈ Γ(v) faça
    se TD[w] = 0 então              // aresta de árvore
      pai[w] ← v; Executar Busca_Profundidade(w)
    senão se TT[w] = 0 e w ≠ pai[v] então
      Visitar aresta de retorno {v, w}
  t ← t + 1; TT[v] ← t
 
Busca_Profundidade(v)                 // grafo direcionado
  para todo vértice w ∈ Γ⁺(v) faça
    se TD[w] = 0 então  aresta de árvore (v, w); pai[w] ← v; ...
    senão se TT[w] = 0 então          aresta de retorno (v, w)
    senão se TD[v] < TD[w] então      aresta de avanço (v, w)
    senão                             aresta de cruzamento (v, w)

Busca em grafos

Busca em Largura

Escolhe sempre o vértice marcado menos recentemente alcançado, usando uma fila, e define o nível de cada vértice.

O(n + m)

Ideia central

Busca genérica em que, dentre todos os vértices marcados e incidentes a alguma aresta ainda não explorada, escolhe-se sempre o menos recentemente alcançado, critério implementado por uma fila. Cada vértice recebe um índice L[v] (ordem de descoberta) e um nível[v] (distância à raiz em número de arestas).

Invariante

nível[w] = nível[pai[w]] + 1 para todo w ≠ raiz. Assim, no momento em que w é marcado, nível[w] já é a distância (número de arestas) entre a raiz da busca e w.

Requisitos do grafo

Aceita arestas direcionadas e não direcionadasIgnora os pesos das arestasClassifica as arestas em pai, tio, irmão e primo

Erros comuns

  • Marcar o vértice (atribuir L[w]) apenas quando ele sai da fila, e não quando entra: o mesmo vértice acabaria enfileirado várias vezes.
  • Esquecer a condição L[w] > L[v] ao classificar arestas de irmão e de primo: ela garante que cada aresta seja explorada uma única vez.
  • Em grafo ponderado, a busca em largura só devolve caminho de peso mínimo se todos os pesos forem iguais; ela minimiza o número de arestas, não o peso.
Inicialização / Chamada inicial
  t ← 0; Fila ← ∅
  para todo vértice v ∈ V(G) faça
    L[v] ← 0; nível[v] ← 0; pai[v] ← nulo
  enquanto existir algum vértice v tal que L[v] = 0 efetuar
    t ← t + 1; L[v] ← t          // v é a raiz da busca
    Fila.Insere(v)
    Executar Busca_Largura()
 
Busca_Largura()
  enquanto not Fila.Vazia() efetuar
    v ← Fila.Remove()
    para todo vértice w ∈ Γ(v) faça
      se L[w] = 0 então          // aresta de árvore (ou pai)
        pai[w] ← v; nível[w] ← nível[v] + 1
        t ← t + 1; L[w] ← t; Fila.Insere(w)
      senão se nível[w] = nível[v] + 1 então
        Visitar aresta de tio {v, w}
      senão se nível[w] = nível[v] e pai[v] = pai[w] e L[w] > L[v] então
        Visitar aresta de irmão {v, w}
      senão se nível[w] = nível[v] e pai[v] ≠ pai[w] e L[w] > L[v] então
        Visitar aresta de primo {v, w}

Conectividade

Método de Kosaraju

Encontra os componentes fortemente conexos (f-conexos) com duas buscas em profundidade: uma em G e outra no grafo reverso Gᴿ.

O(n + m)

Ideia central

Uma primeira busca em profundidade em G registra os tempos de término TT. A segunda busca, feita no grafo reverso Gᴿ e tomando os vértices em ordem decrescente de TT, produz uma floresta em que cada árvore é exatamente um componente fortemente conexo (f-conexo).

Invariante

A ordem decrescente de tempo de término garante que a busca em Gᴿ iniciada em um vértice nunca escapa do componente f-conexo a que ele pertence.

Requisitos do grafo

Exige grafo direcionadoIgnora os pesos das arestas

Erros comuns

  • Esquecer de construir o grafo reverso Gᴿ antes da segunda busca.
  • Percorrer a segunda busca na ordem crescente de TT em vez da decrescente.
  • Confundir os três níveis de conectividade de um grafo direcionado conexo: s-conexo (grafo subjacente conexo), sf-conexo (para todo par, um alcança o outro) e f-conexo (todos mutuamente alcançáveis).
Método de Kosaraju
  1. Fazer busca em profundidade em G
       // salvar os tempos de término TT de cada vértice
  2. Construir o grafo reverso (ou transposto) Gᴿ
       // se (v, w) ∈ E(G) então (w, v) ∈ E(Gᴿ)
  3. Fazer busca em profundidade em Gᴿ tomando os vértices
     em ordem decrescente de TT
 
  Cada árvore da floresta de profundidade obtida no passo 3
  corresponde a um componente fortemente conexo de G.

Grafos eulerianos

Método de Fleury

Constrói um trajeto euleriano caminhando pelo grafo e evitando atravessar uma ponte enquanto houver outra aresta disponível.

O(m² )

Ideia central

Um grafo conexo é euleriano se e somente se todos os seus vértices tiverem grau par (Teorema de Euler), e semi-euleriano se existirem exatamente dois vértices de grau ímpar. O método caminha pelo grafo removendo as arestas percorridas e evita atravessar uma ponte enquanto houver outra opção.

Invariante

O trajeto construído nunca repete arestas e, ao evitar pontes, mantém as arestas restantes de G' conexas, garantindo que a caminhada só termine quando todas tiverem sido percorridas.

Requisitos do grafo

Exige grafo não direcionado e conexoNo máximo 2 vértices de grau ímparIgnora os pesos das arestas

Erros comuns

  • Atravessar uma ponte enquanto existe outra aresta disponível: as arestas do outro lado ficam inalcançáveis e o trajeto termina cedo.
  • Começar por um vértice de grau par em grafo semi-euleriano: o trajeto precisa partir de um dos dois vértices de grau ímpar.
  • Confundir com grafo hamiltoniano: euleriano passa por cada aresta uma vez (trajeto), hamiltoniano por cada vértice uma vez (caminho).
Método de Fleury
  1. se V(G) possuir 3 ou mais vértices de grau ímpar então PARE
  2. Seja G' = (V', E') tal que V' ← V(G) e E' ← E(G)
  3. Selecionar vértice inicial v ∈ V'
       (escolher v cujo grau seja ímpar, se houver)
  4. enquanto E' ≠ ∅ efetuar
     a. se d(v) > 1 então
          Selecionar aresta {v, w} que não seja ponte em G'
        senão
          Selecionar a única aresta {v, w} disponível em G'
     c. v ← w;   E' ← E' − {v, w}
 
  // Caminhar de v para w e eliminar a aresta percorrida

Árvore geradora mínima

Método de Prim

Inclui vértices um a um: a cada passo acrescenta a aresta de menor peso entre V(T) e os vértices ainda não selecionados.

O(m log n)

Ideia central

Constrói a AGM incluindo vértices, um a um, de forma gulosa. Partindo de uma raiz r, a cada passo acrescenta a aresta de menor peso com uma extremidade em V(T) (já selecionados) e a outra fora de V(T).

Invariante

A cada iteração, T = (V(T), E(T)) é uma árvore e está contida em alguma árvore geradora mínima de G.

Requisitos do grafo

Exige grafo não direcionadoExige grafo ponderado com peso w(e) > 0Só existe árvore geradora se o grafo for conexo

Erros comuns

  • Comparar o peso da aresta com a distância acumulada desde a raiz em vez do peso da própria aresta, o que transformaria Prim em Dijkstra.
  • Aplicar Prim em grafo direcionado: o problema correto passa a ser o de arborescência de peso mínimo.
  • Em grafo desconexo não existe árvore geradora: um grafo G possui árvore geradora se e somente se G for conexo.
Método de Prim
  1. Escolher um vértice qualquer r ∈ V(G)   // raiz
  2. V(T) ← { r }        // conj. de vértices selecionados
  3. E(T) ← ∅            // conj. de arestas da AGM
  4. enquanto V(T) ≠ V(G) efetuar
     a. Encontrar a aresta {v, w} de menor peso tal que
        v ∈ V(T) e w ∉ V(T)
     b. Acrescentar w a V(T)
     c. Acrescentar {v, w} a E(T)
 
  Peso total: C(T) = Σ  w  , para e ∈ E(T)
                         e

Árvore geradora mínima

Método de Kruskal

Inclui arestas, e não vértices: ordena as arestas por peso não decrescente e aceita cada uma que não forme ciclo com as já inseridas em E(T).

O(m log m)

Ideia central

Constrói a AGM incluindo arestas, e não vértices como em Prim. Ordena as arestas em ordem não decrescente de peso e aceita, a cada iteração, a aresta de menor peso que não forme ciclo com as já inseridas em E(T).

Invariante

A cada iteração, T = (V(T), E(T)) é uma floresta geradora contida em alguma árvore geradora mínima de G.

Requisitos do grafo

Exige grafo não direcionadoExige grafo ponderado com peso w(e) > 0Em grafo desconexo produz uma floresta geradora mínima

Erros comuns

  • Supor que bastam n − 1 iterações: são necessárias pelo menos n − 1, mas podem ser mais, pois arestas que formam ciclo precisam ser ignoradas.
  • Aceitar uma aresta cujos extremos já estão ligados por arestas de E(T): ela fecharia um ciclo.
  • Em grafo desconexo o resultado é uma floresta geradora mínima, não uma árvore geradora.
Método de Kruskal
  1. Ordenar as arestas em ordem não decrescente de peso:
     e₁, e₂, e₃, . . .
  2. V(T) ← V(G)      // todos os vértices entram na AGM
  3. E(T) ← { e₁ }
  4. j ← 2            // aresta a ser analisada
  5. enquanto | E(T) | < | V(T) | − 1 efetuar
     a. se a aresta e  não forma ciclo com as arestas de E(T)
                     j
        então Acrescentar e  a E(T)
                           j
     b. j ← j + 1

Caminho mínimo

Método de Dijkstra

"Fecha" um vértice por iteração, sempre o de menor dist, e relaxa as arestas tensas que saem dele.

O(n²)

Ideia central

Resolve o problema de caminho mínimo a partir de uma única raiz s. Baseia-se no princípio da relaxação e "fecha" um vértice por iteração: escolhe o vértice ainda não fechado com o menor valor de dist e relaxa as arestas tensas que saem dele.

Invariante

Para todo v ∈ S, dist[v] já é o peso do caminho mínimo da raiz até v. Ao final, dist[ ] guarda os pesos dos caminhos mínimos; os caminhos em si são recuperados pela lista de predecessores pred[ ].

Requisitos do grafo

Aceita arestas direcionadas e não direcionadasExige pesos não negativosBaseia-se no princípio da relaxação

Erros comuns

  • Aplicar o método em grafo com aresta de peso negativo: ele falha. Reponderar, adicionando uma constante a todas as arestas, também pode falhar.
  • Reabrir um vértice que já pertence a S: uma vez fechado, seu dist não muda mais.
  • Achar que dist[ ] devolve os caminhos: sem pred[ ] obtêm-se apenas os pesos.
Operação de relaxação
  se dist[v] + d    < dist[w] então   // aresta (v, w) está tensa?
                vw
    dist[w] ← dist[v] + d
                         vw
    pred[w] ← v
 
Método de Dijkstra
  1. para todo vértice v ∈ V(G) faça
       dist[v] ← ∞; pred[v] ← nulo
  2. dist[s] ← 0        // s é a raiz da busca
  3. S ← ∅              // conjunto dos vértices fechados
  4. enquanto S ≠ V(G) efetuar
     a. Escolher o vértice v ∉ S de menor dist[v]
     b. S ← S ∪ { v }                  // "fechar" o vértice v
     c. para todo vértice w ∈ Γ⁺(v) faça
          se dist[w] > dist[v] + d    então   // aresta tensa?
                                  vw
            dist[w] ← dist[v] + d
                                 vw
            pred[w] ← v

Caminho mínimo

Método de Bellman-Ford

Programação dinâmica: examina todas as arestas a cada iteração, relaxando as que estiverem tensas, por |V(G)| − 1 iterações.

O(n · m)

Ideia central

Calcula caminhos mínimos por programação dinâmica. Em vez de "fechar" um vértice por iteração, como Dijkstra, examina todas as arestas a cada iteração. Como qualquer caminho em um grafo com n vértices possui no máximo n − 1 arestas, n − 1 iterações bastam.

Invariante

Após a i-ésima iteração, dist[w] é no máximo o peso do menor caminho de s a w que usa até i arestas.

Requisitos do grafo

Admite arestas de peso negativoNão admite ciclo de peso negativoDetecta ciclo de peso negativo alcançável a partir da origem

Erros comuns

  • Se, em alguma iteração, nenhuma aresta estiver tensa, o algoritmo pode terminar: as iterações seguintes não trariam atualizações.
  • Havendo ciclo de peso negativo entre s e t, não existe caminho mínimo entre eles; sem esse ciclo, o caminho mínimo é simples (não repete vértices).
  • Aresta não direcionada com peso negativo já é, por si só, um ciclo de peso negativo.
Operação de relaxação
  se dist[v] + d    < dist[w] então   // aresta (v, w) está tensa?
                vw
    dist[w] ← dist[v] + d
                         vw
    pred[w] ← v
 
Método de Bellman-Ford
  1. para todo vértice v ∈ V(G) faça
       dist[v] ← ∞; pred[v] ← nulo
  2. dist[s] ← 0
  3. para i = 1, . . ., | V(G) | − 1 faça
       para cada (v, w) ∈ E(G) faça
         se dist[w] > dist[v] + d    então   // aresta tensa?
                                 vw
           dist[w] ← dist[v] + d
                                vw
           pred[w] ← v
 
  Se ainda houver aresta tensa após a última iteração,
  então existe um ciclo de peso negativo no grafo.

Caminho mínimo

Método de Floyd-Warshall

Caminhos mínimos entre todos os pares por programação dinâmica: a rodada k libera o vértice k como intermediário.

O(n³)

Ideia central

Programação dinâmica sobre o conjunto de vértices intermediários permitidos. Numerados os vértices de 1 a n, distᵏ[i, j] é a distância entre i e j usando como intermediários apenas os vértices de { 1, 2, . . ., k }.

Invariante

Ao final da rodada k, dist[i, j] é o peso do menor caminho de i a j que usa apenas { 1, . . ., k } como vértices intermediários; pred[i, j] guarda o penúltimo vértice desse caminho.

Requisitos do grafo

Admite arestas de peso negativoNão admite ciclo de peso negativoCalcula todos os pares de vértices de uma só vez

Erros comuns

  • Trocar a ordem dos laços: k precisa ser o laço mais externo.
  • Atualizar o predecessor com pred[i, k] em vez de pred[k, j]: pred[i, j] é o penúltimo vértice do caminho de i para j.
  • Entrada negativa na diagonal, isto é, dist[i, i] < 0, indica ciclo de peso negativo.
Relaxação do comprimento dos caminhos
  distᵏ[i, j] = min( distᵏ⁻¹[i, j],
                     distᵏ⁻¹[i, k] + distᵏ⁻¹[k, j] )
  com dist⁰[i, j] = d   se (i, j) ∈ E(G); ∞ caso contrário;
                     ij
  e dist⁰[i, i] = 0
 
Método de Floyd-Warshall
  1. para i = 1, . . ., n faça
       para j = 1, . . ., n | j ≠ i faça
         dist[i, j] ← ∞; pred[i, j] ← nulo
       dist[i, i] ← 0;   pred[i, i] ← i
  2. para toda aresta (i, j) ∈ E(G) faça
       dist[i, j] ← d  ;  pred[i, j] ← i
                     ij
  3. para k = 1, . . ., n faça   // cada possível intermediário
       para i = 1, . . ., n faça
         para j = 1, . . ., n faça
           se dist[i, j] > dist[i, k] + dist[k, j] então
             dist[i, j] ← dist[i, k] + dist[k, j]
             pred[i, j] ← pred[k, j]

Fluxo máximo

Método de Ford-Fulkerson

Enquanto existir algum caminho aumentante em G'(f), envia por ele o gargalo δ e atualiza a rede residual.

O(m · f) com capacidades inteiras

Ideia central

Enquanto existir caminho aumentante da fonte s ao sumidouro t na rede residual G′(f), envia-se por ele o máximo possível, o gargalo δ, e a rede residual é atualizada. As arestas reversas permitem desfazer envios anteriores.

Invariante

O fluxo f respeita sempre a condição de capacidade, 0 ≤ f(e) ≤ u(e), e a condição de conservação em todo nó interno. Pelo teorema do fluxo máximo e corte mínimo, ao final o valor do fluxo iguala a capacidade do corte s-t mínimo.

Requisitos do grafo

Exige rede de fluxo: grafo direcionado com capacidade u(e) > 0Requer uma fonte s e um sumidouro tO caminho aumentante é escolhido de forma arbitrária

Erros comuns

  • Esquecer de criar a aresta reversa na rede residual, o que impede desfazer envios feitos em iterações anteriores.
  • Escolher caminhos aumentantes arbitrários: com capacidades irracionais o método pode não terminar. Escolher sempre o caminho aumentante com menos arestas (busca em largura) é o método de Edmonds-Karp.
  • Assumir que o corte mínimo é qualquer corte: na solução ótima, S é o conjunto dos vértices alcançáveis a partir da fonte s na rede residual final.
Rede residual G′(f): V(G′) = V(G) e, para e = (v, w) ∈ E:
  se f(e) < u(e): aresta direta (v, w) com u (e) = u(e) − f(e)
                                            r
  se f(e) > 0:    aresta reversa (w, v) com capacidade f(e)
 
Método de Ford-Fulkerson
  1. para toda aresta e ∈ E(G) faça  f(e) ← 0
  2. Construir a rede residual G′(f)
  3. enquanto existir caminho aumentante P em G′(f) efetuar
     a. δ ← min { u (e) | e ∈ P }        // "gargalo" de P
                   r
     b. para cada aresta (v, w) ∈ P faça
        i.  se (v, w) for aresta direta então
              f(v, w) ← f(v, w) + δ      // aumentar fluxo
        ii. senão
              f(w, v) ← f(w, v) − δ      // reduzir fluxo
     c. Atualizar a rede residual G′(f)

Fluxo máximo

Método de Edmonds-Karp

Implementação eficiente de Ford-Fulkerson: a cada iteração escolhe o caminho aumentante mais curto, obtido por busca em largura.

O(n · m² )

Ideia central

Implementação eficiente do método de Ford-Fulkerson: a cada iteração seleciona o caminho aumentante da rede residual que seja mais curto, isto é, que use o menor número de arestas. Esse caminho é encontrado por uma busca em largura.

Invariante

O comprimento do caminho aumentante escolhido nunca diminui de uma iteração para a seguinte. O número máximo de caminhos aumentantes é O(n·m) e cada um é encontrado em O(m), donde O(n·m²).

Requisitos do grafo

Exige rede de fluxo: grafo direcionado com capacidade u(e) > 0Requer uma fonte s e um sumidouro tEscolhe sempre o caminho aumentante com menos arestas

Erros comuns

  • Usar busca em profundidade: volta-se ao método de Ford-Fulkerson genérico, que é apenas pseudopolinomial, O(m·f), com f igual ao valor do fluxo máximo.
  • Na rede com duas arestas de capacidade 100 ligadas por uma de capacidade 1, a escolha arbitrária pode exigir 200 iterações; a escolha do caminho mais curto exige 2.
  • Esquecer que o método foi publicado de forma independente por Dinitz (1970) e por Edmonds e Karp (1972).
Método de Edmonds-Karp
  1. para toda aresta e ∈ E(G) faça  f(e) ← 0
  2. Construir a rede residual G′(f)
  3. enquanto existir algum caminho aumentante P em G′(f) efetuar
     a. Seja P o caminho aumentante em G′(f) com menor número
        de arestas   // obtido por busca em largura
     b. δ ← min { u (e) | e ∈ P }
                   r
     c. para cada aresta (v, w) ∈ P faça
        i.  se (v, w) for aresta direta então
              f(v, w) ← f(v, w) + δ
        ii. senão
              f(w, v) ← f(w, v) − δ
     d. Atualizar a rede residual G′(f)

Fluxo máximo

Método de Dinic

A cada iteração constrói a rede em níveis GL a partir de G′(f) e determina nela um fluxo de bloqueio.

O(n² · m)

Ideia central

Em vez de aumentar um caminho por vez, constrói a rede em níveis GL a partir de G′(f) e determina nela um fluxo de bloqueio inteiro. Como o número de níveis cresce pelo menos uma unidade a cada iteração, existem no máximo n − 1 fluxos de bloqueio.

Invariante

dist(t) é estritamente crescente entre iterações, logo há no máximo n − 1 fluxos de bloqueio. Cada fluxo de bloqueio é obtido em O(n·m), donde O(n²·m).

Requisitos do grafo

Exige rede de fluxo: grafo direcionado com capacidade u(e) > 0Requer uma fonte s e um sumidouro tNo máximo n − 1 fluxos de bloqueio

Erros comuns

  • Buscar caminhos fora de GL: só valem as arestas (v, w) com dist(w) = dist(v) + 1.
  • Reconstruir a rede em níveis a cada caminho, e não a cada fluxo de bloqueio, pois é o fluxo de bloqueio completo que caracteriza uma iteração.
  • Parar quando um caminho satura: o fluxo de bloqueio só termina quando não existir mais nenhum caminho de s a t em GL.
Rede em níveis GL: V(GL) = V(G′) e, para (v, w) ∈ E(G′):
  (v, w) ∈ E(GL) com capacidade u (e) se dist(w) = dist(v) + 1,
                                 r
  em que dist(v) é a menor distância geodésica de s até v
 
Fluxo de bloqueio fb: fluxo em GL tal que, mantidas apenas as
  arestas com capacidade maior que fb, não exista mais
  caminho aumentante em GL
 
Método de Dinic
  1. para toda aresta e ∈ E(G) faça  f(e) ← 0
  2. Construir a rede residual G′(f)
  3. Construir a rede em níveis GL a partir de G′(f)
  4. enquanto dist(t) < ∞ efetuar
     a. Determinar um fluxo de bloqueio fb em GL
     b. Atualizar o fluxo f usando fb
     c. Atualizar a rede residual G′(f)
     d. Construir a rede em níveis GL a partir de G′(f)

Ordenação topológica

Método de Kahn

Determina a cada instante um vértice com grau de entrada zero, insere-o no fim do resultado e reduz o grau de entrada de seus sucessores.

O(n + m)

Ideia central

Determina a cada instante um vértice sem arestas de entrada, isto é, com d⁻(v) = 0, e o insere no fim do resultado. Em vez de remover as arestas, mantém e atualiza um mapa M com o grau de entrada de cada vértice.

Invariante

Um vértice só entra na fila quando todos os seus predecessores já estão em Ordena_Top, portanto ord(v) < ord(w) para toda aresta (v, w) ∈ E(G).

Requisitos do grafo

Exige grafo direcionadoSó existe ordenação topológica em grafo acíclicoDetecta a existência de ciclo

Erros comuns

  • Aplicar a grafo não direcionado ou com ciclo: não há como estabelecer relação de precedência, e a ordenação topológica não existe.
  • Interpretar a fila vazia com vértices pendentes como erro: é exatamente assim que o método detecta a existência de ciclo.
  • Supor que a ordenação é única: cada grafo acíclico direcionado pode ter várias ordenações topológicas válidas.
Método de Kahn
  1. para todo vértice v faça M[v] ← d⁻(v)
  2. Fila ← ∅; Ordena_Top ← ∅
  3. para todo vértice v tal que d⁻(v) = 0 faça
       Fila.Insere(v)
  4. enquanto not Fila.Vazia() efetuar
     a. v ← Fila.Remove()
     b. Ordena_Top.InsereNoFim(v)
     c. para todo vértice w ∈ Γ⁺(v) faça
        i.  M[w] ← M[w] − 1
        ii. se M[w] = 0 então Fila.Insere(w)
  5. Se todos os vértices forem processados, SUCESSO;
     caso contrário, existe um CICLO

Ordenação topológica

Ordenação topológica por busca em profundidade

Descrito por Tarjan em 1976: insere cada vértice no início do resultado somente depois de visitar todos os que dependem dele.

O(n + m)

Ideia central

Alternativa baseada na busca em profundidade, descrita por Tarjan em 1976. Cada vértice é inserido no resultado somente após todos os que dependem dele, e a inserção é feita no início da lista, daí a ordem reversa.

Invariante

Quando v recebe marca permanente, todos os vértices alcançáveis a partir de v já estão em Ordena_Top. Como v é inserido no início, ele precede todos eles na ordenação.

Requisitos do grafo

Exige grafo direcionadoSó existe ordenação topológica em grafo acíclicoMarca temporária reencontrada evidencia ciclo

Erros comuns

  • Inserir no fim em vez do início: a ordenação sai invertida. A ordem correta é a reversa da ordem de inserção, equivalente à ordem decrescente de tempo de término.
  • Não distinguir marca temporária de permanente: só a marca temporária reencontrada evidencia ciclo; a permanente indica um vértice já resolvido.
  • Confundir com a floresta de profundidade comum: aqui o que importa é a ordem de término, não a árvore.
Método por Busca em Profundidade
  1. para todo vértice v faça Marca[v] ← 0
  2. Ordena_Top ← ∅
  3. enquanto existir algum vértice v tal que Marca[v] = 0
     efetuar Visita(v)
 
Visita(v)
  1. se Marca[v] ≠ 2 então      // se v não for permanente
     a. se Marca[v] = 1 então CICLO   // marca temporária
     b. Marca[v] ← 1                  // marca temporária
     c. para todo vértice w ∈ Γ⁺(v) faça Visita(w)
     d. Marca[v] ← 2                  // marca permanente
     e. Ordena_Top.InsereNoInicio(v)

Emparelhamento

Método de Edmonds

Busca caminhos M-aumentantes entre vértices expostos, contraindo os botões (blossoms) que aparecem, até que não exista mais nenhum.

O(n² · m)

Ideia central

Pelo teorema de Berge, M tem cardinalidade máxima se e somente se não existe caminho M-aumentante. O método busca esses caminhos em uma floresta M-alternante; quando uma aresta liga dois vértices a distância par da mesma árvore, surge um ciclo ímpar, o botão (blossom), que é contraído em um pseudovértice.

Invariante

M ⊕ EP é sempre um emparelhamento com uma aresta a mais que M. Pelo teorema de Edmonds, M é máximo em G se e somente se M/B é máximo em G/B, o que legitima a contração dos botões.

Requisitos do grafo

Exige grafo não direcionadoIgnora os pesos das arestasTrata grafo genérico, não apenas bipartido

Erros comuns

  • Usar apenas busca em largura ou profundidade em grafo genérico: sem tratar os botões, caminhos M-aumentantes existentes deixam de ser encontrados.
  • Ignorar a aresta {v, w} quando dist(w, F.raiz[w]) for ímpar: ela não gera caminho aumentante.
  • Confundir emparelhamento maximal com máximo: maximal apenas não admite acrescentar arestas; máximo é o de maior cardinalidade. E emparelhamento máximo não implica casamento perfeito.
Emparelhamento_Máximo(G)
  1. M ← ∅
  2. P ← Encontra_Caminho_Aumentante(G, M)
  3. enquanto (P ≠ ∅) efetuar
     a. M ← M ⊕ EP
     b. P ← Encontra_Caminho_Aumentante(G, M)
 
Encontra_Caminho_Aumentante(G, M)
  1. F ← Inicializa_Floresta_Alternante(G, M)
  2. para todo vértice desmarcado v ∈ F tal que
     dist(v, F.raiz[v]) for par faça
     a. enquanto ∃ aresta e = {v, w} desmarcada efetuar
        i.   se w ∉ F então Adicionar_a_Floresta(M, F, v, w)
        ii.  senão se dist(w, F.raiz[w]) for par então
               retornar Obter_Novo_Caminho(G, M, F, v, w)
        iii. Marcar aresta e
     b. Marcar vértice v
  3. retornar ∅
 
Obter_Novo_Caminho(G, M, F, v, w)
  1. se F.raiz[v] ≠ F.raiz[w] então
       P ← ObterCaminho(F, F.raiz[v], v)
            + ObterCaminho(F, w, F.raiz[w])
  2. senão                          // botão (blossom)
     a. B ← ObterCaminho(F, v, w) + v
     b. G′ ← Contrair_Blossom_Grafo(G, B, z)
     c. M′ ← Contrair_Blossom_Emparelhamento(M, B, z)
     d. P ← Encontra_Caminho_Aumentante(G′, M′)
     e. se z ∈ P então P ← Expandir_Blossom(P, G, B, z)
  3. retornar P

Coloração

Método guloso

Percorre os vértices em uma ordem qualquer e atribui a cada um a cor de menor índice não utilizada por nenhum de seus vizinhos.

O(n + m)

Ideia central

Não há método eficiente para obter a coloração mínima de um grafo, mas é possível obter rapidamente uma coloração aproximada: percorrem-se os vértices em uma ordem qualquer, atribuindo a cada um a cor de menor índice não utilizada por seus vizinhos.

Invariante

A cada passo a coloração parcial é válida: cor(v) ≠ cor(w) para todo par de vértices adjacentes já coloridos. Como um vértice tem no máximo Δ(G) vizinhos, o método nunca usa mais que Δ(G) + 1 cores.

Requisitos do grafo

Exige grafo não direcionadoColoração aproximada, não necessariamente mínimaO resultado depende da ordem dos vértices

Erros comuns

  • Tomar o número de cores obtido como o número cromático: o resultado depende da ordem dos vértices e em geral χ(G) é menor.
  • Esquecer os limites conhecidos: ω(G) ≤ χ(G) ≤ Δ(G) + 1 e, pelo Teorema de Brooks, χ(G) ≤ Δ(G) se G for simples, não completo e não for ciclo ímpar.
  • Aplicar a grafo direcionado: a coloração de vértices é definida para grafo não direcionado.
Método Guloso
  1. Considerar os vértices do grafo em uma ordem qualquer
     v₁, v₂, . . ., vₙ
  2. Identificar as cores com índices, adicionando mais cores
     quando necessário
  3. Colorir v₁ com a primeira cor
  4. A cada iteração, atribuir ao vértice corrente a cor de
     menor índice não utilizada por nenhum de seus vizinhos

Coloração

Método de Welsh-Powell

Ordena os vértices em ordem não crescente de graus e colore, com uma mesma cor, todos os que não estiverem conectados a um vértice já colorido com ela.

O(n² )

Ideia central

Refinamento do método guloso: os vértices são ordenados em ordem não crescente de graus e cada cor é distribuída em uma passagem completa pela lista, colorindo todos os vértices que não estejam conectados a um já colorido com aquela cor.

Invariante

Cada cor forma um conjunto independente: nenhum par de vértices que recebem a mesma cor é adjacente. O método termina porque cada passagem colore pelo menos um vértice.

Requisitos do grafo

Exige grafo não direcionadoColoração aproximada, não necessariamente mínimaCostuma usar menos cores que o método guloso

Erros comuns

  • Tomar o resultado como ótimo: existe contraexemplo em que Welsh-Powell usa 3 cores num grafo bipartido, para o qual χ(G) = 2.
  • Abandonar a ordem por grau ao iniciar uma nova cor: a lista ordenada é percorrida do começo em cada passagem.
  • Colorir um vértice adjacente a outro já colorido com a cor da passagem atual: a verificação é contra os vértices já coloridos com aquela cor.
Método de Welsh-Powell
  1. Ordenar os vértices em ordem não crescente de graus
     v₁, v₂, . . ., vₙ
  2. Identificar as cores com índices, adicionando mais cores
     quando necessário
  3. Colorir v₁ com a primeira cor
  4. Seguir pela lista de vértices colorindo todos os vértices
     não conectados a um vértice já colorido, usando sempre
     a mesma cor
  5. Repetir o passo 4 para todos os vértices não coloridos
     usando uma nova cor, sempre respeitando a ordem não
     crescente de graus, até que todos estejam coloridos