Algoritmos em Grafos  |  Livros  |  WWW  |  Índice de Termos

 

Par disjunto de caminhos (= 2-fluxo)

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 um determinado problema desse tipo?

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. 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, seja D um caminho de r a s disjunto de C. Devolva C e 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.  Uma observação fácil de verificar:  se gs(X) < 2 para algum separador X de rs então não existe um par disjunto de caminhos de r a 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á

• um par disjunto de caminhos de r a s ou
• um separador de rs que tem capacidade menor que 2.

Exercícios

3. 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 Fs(v) o conjunto dos arcos de F que saem de v e por Fe(v) o conjunto dos arcos de F que entram em v.  [O "s" em "Fs" é a inicial da palavra saída e não tem nenhuma relação com o vértice s.]   De modo mais geral, para qualquer conjunto X de vértices, Fs(X) é o conjunto dos arcos de F que saem de X e Fe(X) o conjunto dos arcos de F que entram em X.

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

|Fe(v)|  =  |Fs(v)|

para todo vértice v distinto de r e de s.  A intensidade de um fluxo F é o número  |Fs(r)|  –  |Fe(r)| .   Em geral (mas nem sempre), temos |Fe(r)| = 0;  nesse caso, a intensidade do fluxo é |Fs(r)|.   No presente capítulo, só estamos interessados em fluxos de intensidade 0, 1 e 2.  [A propósito, há quem goste de dizer "k-fluxo" no lugar de "fluxo de intensidade k".]   [Cuidado! Não confunda intensidade de fluxo com capacidade de separador. O primeiro é uma diferença entre saída e entrada. O segundo é simplesmente conta apenas a saída.]  

Um 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 mais interessante: 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 disjuntos 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 o problema sempre tem solução.

Exercícios

4. Suponha que um conjunto F de arcos de um grafo do SGB é marcado por meio de um utility field flx:  digamos que a–>flx = 1 se o arco a está em F e a–>flx = 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, determine a intensidade do fluxo.

5. 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 a–>flx = NULL senão a–>flx é 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, determine a intensidade do fluxo. 

6. Suponha que F é um fluxo de intensidade k de r a s.  Mostre que  |Fe(s)| – |Fs(s)|  =  k.

7. Suponha que F é um fluxo de intensidade k de r a s e X um separador de rs. Mostre que  |Fs(X)| – |Fe(X)|  =  k. 

8. Escreva um algoritmo para encontrar um fluxo de intensidade 1 de r a s.

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

   Como representar o caminho? Você pode, por exemplo, adotar um utility field prox de vértices para apontar o vértice seguinte do caminho. Assim, um caminho de r a s teria a forma  r, r–>prox, r–>prox–>prox, . . . , s.   Outra idéia, quem sabe melhor: adote um utility field cam de vértices para apontar o arco seguinte do caminho. Assim, um caminho de r a s terá a forma  r, r–>cam, r–>cam–>tip, r–>cam–>tip–>cam, r–>cam–>tip–>cam–>tip, . . . , s.

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

Seqüências de aumento

Suponha que F é um fluxo de r a s.  Uma seqüência alternante para F é uma seqüê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  v[i–1]  a  vi  ou
o arco  ai  está em  F  e vai de  vi  a  v[i–1].

Em geral, uma seqüê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 seqüência de aumento (= augmenting path) para F é uma seqüência alternante para F que termina em s.  (Note que toda seqüência alternante começa em r.)

Fato Básico:  Se F é um fluxo de intensidade 1 de r a s e Z é uma seqüê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 dos arcos que estão em  AZ  ou  em F  mas não em ambos.

Exercícios

11. Prove o Fato Básico.

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

13. Seja G o grafo definido pela matriz abaixo (tomei a liberdade de escrever os nomes dos arcos na matriz). 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 seqüê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	-	-	-	-	-	-	-	-	-	-

    
    

14. Seja F um fluxo de intensidade 1 de r e s. Seja X o conjunto dos términos de todas as seqüê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 F1 de intensidade 1 de r a s,
2. encontre uma seqüência de aumento para o fluxo F1,
3. combine a seqüência de aumento com o fluxo para obter um novo fluxo F2, de intensidade 2,
4. extraia de F2 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 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 w–>pred = v e w–>apred = a.

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

Exercícios

15. 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 tem capacidade menor que 2.

16. Desafio: Escreva um algoritmo que ao receber um grafo g e vértices r e s determine 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).]

Mais exercícios

17. [Seqüência Euleriana]  Escreva uma função que encontre uma seqüência euleriana em um grafo dado.  Uma seqüência  (v[0], a[1], v[1], a[2], v[2], . . . , a[m], v[m])  é euleriana se tem as seguintes propriedades:     cada a[i] é um arco que vai de v[i–1] a v[i] ;
       v[m] = v[0];
       os arcos a[1] , . . . , a[m] são distintos dois a dois;
       a seqüência contém todos os arcos do grafo.
    (Esse é famoso problema das pontes de Königsberg, resolvido por Leonhard Euler.)

    

    Nem todo grafo tem uma seqüência euleriana; faz parte do problema mostrar que o grafo dado não tem uma seqüência euleriana se esse for o caso. Para simplificar, você pode supor que o grafo dado é fortemente conexo. 

    Sugestão:  Represente a seqüência euleriana por uma lista de arcos,  digamos a , a–>seg , a–>seg–>seg , . . . ,  onde  a == a₁ , a–>seg == a₂ , a–>seg–>seg == a₃ , etc.