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

 

Emparelhamentos

(Veja Matching na Wikipedia.)

Um emparelhamento (= matching) num grafo G não-dirigido é um conjunto M de arestas dotado da seguinte propriedade: todo vértice de G incide em no máximo um elemento de M.  (Um laço não pode fazer parte de um emparelhamento porque incide duas vezes em um mesmo vértice.)

Poderíamos dizer que um emparelhamento é um conjunto de arestas duas a duas independentes; um emparelhamento é, portanto, análogo a um conjunto estável de vértices.

Um emparelhamento M é máximo se não existe um emparelhamento M' tal que |M'| > |M|.  A propósito, um emparelhamento M é maximal se não existe um emparelhamento M' do qual M faça parte própria (portanto, M é maximal se não existe aresta a fora de M tal que M+{a} também é um emparelhamento).

Problema do Emparelhamento Máximo: Encontrar um emparelhamento máximo num grafo não-dirigido.

Exercícios

1. Escreva uma função que decida se um dado conjunto M de arestas é ou não é um emparelhamento. O conjunto M é dado por um utility field:  a–>emp vale 1 se o arco a faz parte de uma aresta que está em M e vale 0 em caso contrário. 

2. Suponha que emp é um utility field de vértices que aponta para arcos:  para cada vértice v, v–>emp é um arco que sai de v  ou vale NULL.  Que propriedades deve ter emp para que o conjunto de arcos da forma v–>emp seja um emparelhamento? 

3. Escreva uma função que calcule um emparelhamento maximal em um grafo não-dirigido dado.

Emparelhamentos perfeitos

Dizemos que um emparelhamento M satura um vértice v se alguma aresta de M incide em v.  Vértices não-saturados são às vezes chamados livres.  Um emparelhamento M é perfeito se satura todos os vértices do grafo. 

Eis um caso especial interessante do problema do emparelhamento máximo: encontrar um emparelhamento perfeito num grafo dado. É claro que nem todo grafo tem um emparelhamento perfeito; a dificuldade do problema está em decidir se o grafo tem ou não tem um emparelhamento perfeito.

Caminhos de aumento

O seguinte conceito é uma ferramenta muito útil para atacar o problema do emparelhamento máximo. Um caminho é alternante (= alternating) em relação a um emparelhamento M se começa em um vértice não-saturado e suas arestas estão alternadamente em M e fora de M.  (O leitor atento não terá deixado de perceber a semelhança desse conceito com o de seqüência alternante.)

Um caminho alternante é de aumento (= augmenting) se termina num vértice não-saturado e tem pelo menos uma aresta.

Para entender como um emparelhamento interage com uma seqüência alternante, precisamos do conceito de diferença simétrica: a diferença simétrica entre conjuntos A e B é o conjunto dos objetos que estão em A ou em B mas não em ambos. A diferença simétrica de A e B será denotada por  A © B . [A pobreza de símbolos do HTML me obriga a fazer essa improvisação.]

Suponha que C é um caminho de aumento para um emparelhamento M.  Se denotarmos por AC o conjunto das arestas de C,  então 

AC © M  é um emparelhamento maior que M.  Conseqüência: se existe um caminho de aumento para M então M não é um emparelhamento máximo.  O interessante é que a recíproca é verdadeira, ainda que isso não seja óbvio.  Esses fatos sugerem o seguinte esqueleto de algoritmo para resolver o problema do emparelhamento máximo:

1 2 3 4

M = { } enquanto existe um caminho de aumento para M faça seja  C  um caminho de aumento para M M = AC © M

(É claro que na linha 1 poderíamos adotar qualquer emparelhamento não-vazio para começar o processo.)  A dificuldade está em determinar um caminho de aumento.

Exercícios

4. Suponha que C é um caminho de aumento para um emparelhamento M.  Mostre que AC © M  é um emparelhamento maior que M.

5. Suponha que C é um caminho alternante para um emparelhamento M.  Em que condições AC © M  é um emparelhamento?

6. Escreva uma função C que receba um emparelhamento M e um caminho de aumento C e calcule o emparelhamento AC © M. 

7. [Importante! Teorema de Berge]  Suponha que um emparelhamento M não é máximo. Prove que existe é um caminho de aumento para M.

8. [Slink]  Dois jogadores, digamos A e B, se alternam escolhendo vértices num grafo g. Primeiro, A escolhe um vértice v0. Em seguida, B escolhe um vértice v1 adjacente a v0. Depois, A escolhe um vértice adjacente a v1 mas diferente de v0 e de v1. E assim por diante.  Eis uma maneira mais limpa de descrever o jogo: os vértices escolhidos formam um caminho v0, v1. . . . , vk;  se k é ímpar, A escolhe um vértice v[k+1] distinto dos demais mas adjacente a vk;  se k é par, B faz um jogada análoga;  o último jogador que puder fazer um movimento vence o jogo.  Prove que A tem uma estratégia vencedora se g não tem um emparelhamento perfeito. Prove que B tem uma estratégia vencedora em caso contrário.

9. [Desafio]  Invente um algoritmo que receba um emparelhamento não-máximo M e encontre um caminho de aumento para M.

Emparelhamentos e coberturas

Há uma relação interessante entre emparelhamentos e coberturas: para todo emparelhamento M e toda cobertura K,

|M|  <  |K| .

Segue daí imediatamente que se |M| = |K| então o emparelhamento M é máximo e a cobertura K é minima.  Infelizmente a recíproca não é verdadeira:  mesmo que M seja um emparelhamento máximo e K seja uma cobertura mínima, temos |M| < |K|  em geral.  Mas nem tudo está perdido: a próxima seção mostra que se o grafo é bipartido então emparelhamentos máximos e coberturas mínimas têm o mesmo tamanho.

Exercícios

10. Prove que |M| < |K| para todo emparelhamento M e toda cobertura K.

11. Suponha que M é um emparelhamento, que K é uma cobertura e que |M| = |K|.  Prove que o emparelhamento M é máximo e a cobertura K é minima.

12. [Bom!]  Seja M^* um emparelhamento máximo e M um emparelhamento maximal. Prove que |M| > ½ |M^*|.

Emparelhamentos em grafos bipartidos

Encontrar caminhos de aumento em grafos arbitrários é supreendentemente difícil. (Mas existe um algoritmo eficiente e muito interessante — o algoritmo de Edmonds — para fazer o serviço.)

Mas se nosso grafo é bipartido (= bicromático), é muito fácil encontrar um caminho de aumento em relação a qualquer emparelhamento M:  basta adaptar um algoritmo de busca de modo que ele percorra caminho alternantes!  Se não existe caminho de aumento para M, nosso algoritmo de busca modificado pode facilmente determinar uma cobertura com |M| vértices, o que prova que o emparelhamento M é máximo.

Com isso resolvemos, de uma só tacada, dois problemas sobre grafos bipartidos: o do emparelhamento máximo e o da cobertura mínima.

Vamos aos detalhes. O conjunto de vértices de nosso grafo é a união de dois conjuntos, V e W, e cada aresta tem uma ponta em V e outra em W. Suponha que M é um emparelhamento. Seja N o conjunto dos vértices não-saturados em V. Faça uma busca por caminhos alternantes a partir de N:  seja X o conjunto de todos os términos de caminhos alternantes que começam em N. Se houver um vértice não-saturado em X∩W então encontramos um caminho de aumento.    Suponha porém que X não contém vértices não-saturados. Então

• não existe aresta fora de M ligando V∩X a W–X;
• não existe aresta de M ligando V∩X a W–X;
• não existe aresta de M ligando W∩X a V–X.

Conclusão: o conjunto W∩X + V–X é uma cobertura e  |W∩X + V–X|  =  |M|.

Exercícios

13. Escreva uma função que receba um grafo bipartido, uma bicoloração de seus vértices e um emparelhamento M e devolva um caminho de aumento para M (ou devolva a informação de que não existe caminho de aumento).

14. Escreva uma função que receba um grafo bipartido e uma bicoloração de seus vértices e devolva um emparelhamento máximo.

A título de curiosidade, eis um applet que calcula um emparelhamento perfeito de peso mínimo em um grafo euclidiano (os vértices são pontos do plano e as arestas são os segmentos de reta no plano que ligam dois vértices e o peso de cada aresta é o comprimento do segmento correspondente).   O applet foi escrito por Luis Goddyn e Michael Maguire na Universidade Simon Fraser, Canadá.