Grafos com SGB | Índice de Termos

Par disjunto de caminhos (ou 2-fluxo) em grafos

Um par de caminhos em um grafo é disjunto se os caminhos não têm arcos em comum, ou seja, se nenhum arco do grafo é usado por ambos os caminhos.

Problema do Par Disjunto de Caminhos: Dados vértices r e s de um grafo, encontrar um par disjunto de caminhos de r a s.

É claro que o problema pode não ter solução. Desafio: como tornar evidente a inexistência de solução de uma dada instância do problema?

Exemplo: No grafo definido abaixo, os caminhos (1, a, 2, c, 4) e (1, b, 3, d, 4) são disjuntos. Já os caminhos (1, a, 2, e, 3, d, 4) e (1, b, 3, d, 4) não são disjuntos.

ponta inicial 1 1 2 3 2
arco a b c d e
ponta final 2 3 4 4 3

Exercícios 1

  1. Discuta o seguinte algoritmo, que pretende resolver o problema. Seja C um caminho de r a s. Se não existe caminho de r a s que seja disjunto de C então pare. Senão, encontre um caminho D de r a s que seja disjunto de C e devolva o par (C, D).
  2. Repita o exercício anterior supondo que o caminho C é mínimo (número mínimo de arcos).

Separadores

Um conjunto X de vértices separa r de s se r está em X enquanto s está fora de X. Um separador de rs é um conjunto de vértices que separa r de s. A capacidade de um separador X é o número

gs(X),

ou seja, o grau de saída de X. É fácil verificar a seguinte observação: se algum separador de rs tem capacidade menor que 2 então não existe um par disjunto de caminhos de r a s. (Note que o s na expressão gs não tem qualquer relação com o vértice s.)

Nossa solução do problema do par de caminhos mostrará que a recíproca também vale. O algoritmo que resolve o problema do par disjunto de caminhos terá a seguinte especificação: ao receber vértices r e s, o algoritmo devolverá

Exercícios 2

  1. Que aparência tem, na matriz de adjacências do grafo, um separador de capacidade 1?

Fluxos

Para qualquer conjunto F de arcos e qualquer vértice v, denotaremos por gsF(v) o número de arcos de F que saem de v e por geF(v) o número de arcos de F que entram em v. (O s em gs é a inicial de saída e não tem relação com o vértice s.) De modo mais geral, para qualquer conjunto X de vértices, gsF(X) é o número de arcos de F que saem de X e geF(X) o número de arcos de F que entram em X.

O seguinte conceito não é indispensável, mas ajuda muito a resolver nosso problema. Um fluxo de r a s é um conjunto F de arcos tal que

geF(v) ≡ gsF(v)

para todo vértice v distinto de r e de s. A intensidade de um fluxo F é o número gsF(r) − geF(r). Se geF(r) ≡ 0 (como muitas vezes acontece) então a intensidade do fluxo é gsF(r). (Cuidado! Não confunda intensidade de fluxo com capacidade de separador. O primeiro é uma diferença entre saída e entrada; o segundo conta somente a saída.) (A propósito, há quem diga k-fluxo no lugar de fluxo de intensidade k.) No presente capítulo, só estamos interessados em fluxos de intensidade 0, 1 ou 2. 

O seguinte fato básico é fácil de verificar: Se F é o conjunto de arcos de um caminho de r a s então F é um fluxo de intensidade 1. Reciprocamente, se F é um fluxo de intensidade 1 de r a s então existe um caminho de r a s cujos arcos estão em F.

Outro fato básico, um pouco menos óbvio: Se F é o conjunto dos arcos de um par disjunto de caminhos de r a s então F é um fluxo de intensidade 2. Reciprocamente, se F é um fluxo de intensidade 2 de r a s então existe um par disjunto de caminhos de r a s cujos arcos estão em F.

Nosso problema do par disjunto de caminhos pode ser reformulado assim:

Dados vértices r e s de um grafo, encontrar um fluxo de intensidade 2 de r a s ou um separador de rs que tenha capacidade menor que 2.

Não está claro, por enquanto, se toda instância do problema tem solução.

Exercícios 3

  1. Suponha que um conjunto F de arcos de um grafo do SGB é marcado por meio de um utility field flx. Digamos que aflx ≡ 1 se o arco a está em F e aflx ≡ 0 em caso contrário. Escreva uma função que decida se F é ou não é um fluxo de r a s. Em caso afirmativo, calcule a intensidade do fluxo.
  2. Suponha que um conjunto F de arcos de um grafo do SGB é marcado por meio de um utility field flx: se a não está em F então aflx ≡ NULL senão aflx é a ponta inicial de a. Escreva uma função que decida se F é ou não é um fluxo de r a s. Em caso afirmativo, encontre a intensidade do fluxo.
  3. Suponha que F é um fluxo de intensidade k de r a s. Mostre que geF(s) − gsF(s) ≡ k.
  4. Suponha que F é um fluxo de intensidade k de r a s e X um separador de rs. Mostre que gsF(X) − geF(X) ≡ k.
  5. Escreva um algoritmo para encontrar um fluxo de intensidade 1 de r a s.
  6. Escreva um algoritmo que receba um par rs de vértices e um fluxo F de intensidade 1 de r a s e devolva um caminho de r a s cujos arcos estão em F. Para representar o caminho, você pode usar um utility field prox para apontar o vértice seguinte do caminho. Assim, um caminho de r a s teria a forma r, rprox, rproxprox, … , s. Outra idéia, quem sabe melhor: adote um utility field cam para apontar o arco seguinte do caminho. Assim, um caminho de r a s terá a forma r, rcam, rcamtip, rcamtipcam, rcamtipcamtip, … , s.
  7. Escreva um algoritmo que receba um par rs de vértices e um fluxo F de intensidade 2 de r a s e devolva um par disjunto de caminhos de r a s cujos arcos estão em F.

Sequências de aumento

Suponha que F é um fluxo de r a s. Uma sequência alternante para F é uma sequência da forma

(v0, a1, v1, a2, v2, … , am, vm)

onde os vi são vértices distintos dois a dois, v0 ≡ r e

o arco ai está fora de F e vai de vi−1 a vi ou
o arco ai está em F e vai de vi a vi−1.

Em geral, uma sequência alternante não é um caminho, pois nem todos os arcos apontam pra frente. Ela só é um caminho se não tem arcos em F, em particular se F é vazio.

Uma sequência de aumento (= augmenting path) para F é uma sequência alternante para F que termina em s. (Note que toda sequência alternante começa em r.)

Fato Básico: Se F é um fluxo de intensidade 1 de r a s e Z é uma sequência de aumento para F então AZ ⊕ F é um fluxo de intensidade 2 de r a s.

Aqui, AZ é o conjunto dos arcos de Z e a expressão AZ ⊕ F representa o conjunto de todos os arcos que estão em AZ ∪ F mas não em AZ ∩ F.

Exercícios 4

  1. Prove o Fato Básico.
  2. Mostre a seguinte generalização do Fato Básico: se F é um fluxo de intensidade k então AZ ⊕ F é um fluxo de intensidade k+1.
  3. Seja G o grafo definido pela matriz abaixo. Faça um desenho do grafo. Seja F o conjunto de arcos { a, b, c, d, e, f, g, h, i }. Note que F é um fluxo de intensidade 1 de 0 a 9. Encontre uma sequência de aumento para F que comece em 0 e termine em 9.
      0 1 2 3 4 5 6 7 8 9
    0 - a j - - - - - - -
    1 - - b - k - - - - -
    2 - - - c - - - - - -
    3 - - - - d - l - - -
    4 - - - - - e - - - -
    5 - - - - - - f - m -
    6 - - - - - - - g - -
    7 - - - - - - - - h n
    8 - - - - - - - - - i
    9 - - - - - - - - - -
  4. Seja F um fluxo de intensidade 1 de r e s. Seja X o conjunto dos términos de todas as sequências alternantes para F. Suponha que s não está em X, ou seja, que X é um separador de rs. Mostre que a capacidade de X é igual a 1.

Algoritmo

Eis um esboço de um algoritmo para o Problema do Par Disjunto de Caminhos:

  1. encontre um fluxo F' de intensidade 1 de r a s,
  2. encontre uma sequência de aumento para o fluxo F',
  3. combine a sequência de aumento com o fluxo para obter um novo fluxo F", de intensidade 2,
  4. extraia de F" um par disjunto de caminhos de r a s.

Se o primeiro passo for impossível, encontre um separador de capacidade 0. Se o segundo passo for impossível, encontre um separador de capacidade 1.

Para implementar o passo 2, basta fazer uma busca ligeiramente mais complexa que a busca que estudamos em outro capítulo. Além de marcar o vértice predecessor de cada vértice durante a busca, sugiro marcar também o arco predecessor. Por exemplo, se cheguei ao vértice w vindo do vértice v e andando sobre o arco a então faço wpred = v e wapred = a.

Sugiro também marcar os arcos do fluxo F' da seguinte maneira: se a não está em F' então aflx = NULL; senão aflx é a ponta inicial de a. Essa maneira de representar o fluxo deve tornar mais fácil a procura por uma sequência de aumento.

Exercícios 5

  1. Escreva, em C, o algoritmo que esboçamos acima. Ao receber um grafo g e vértices r e s, o algoritmo deverá devolver um par disjunto de caminhos de r a s ou um separador de rs que tenha capacidade menor que 2.
  2. [Desafio] Escreva um algoritmo que ao receber um grafo g e vértices r e s encontre uma coleção máxima de caminhos de r e s sem arcos em comum. Seu algoritmo também deve exibir um separador de rs de capacidade mínima para provar que a sua coleção de caminhos é de fato máxima. (Este é o famoso problema do fluxo máximo e corte mínimo (= max-flow min-cut).)

Exercícios 6

  1. [Sequência Euleriana] Escreva uma função que encontre uma sequência euleriana em um grafo dado. Uma sequência (v0, a1, v1, a2, v2, … , am, vm) é euleriana se tem as seguintes propriedades:
    • cada ai é um arco que vai de vi−1 a vi;
    • vm ≡ v0;
    • os arcos a1, … , am são distintos dois a dois;
    • a sequência contém todos os arcos do grafo.

    (Esse é famoso problema das pontes de Königsberg, resolvido por Leonhard Euler.)

    Königsberg

    Nem todo grafo tem uma sequência euleriana; faz parte do problema mostrar que o grafo dado não tem uma sequência euleriana se esse for o caso. Para simplificar, você pode supor que o grafo dado é fortemente conexo. (Sugestão: Represente a sequência euleriana por uma lista de arcos, digamos a, aseg, asegseg, … , onde a ≡ a1, aseg ≡ a2, asegseg ≡ a3, etc.)

www.ime.usp.br/~pf/algoritmos_em_grafos/
Atualizado em 2017-09-18
Paulo Feofiloff
IME-USP