Um emparelhamento (= matching) num grafo não-dirigido G é 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.
Dizemos que um emparelhamento M satura um vértice v se alguma aresta de M incide em v. 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.
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. (Note a semelhança entre esse conceito e o conceito de sequência alternante no contexto do problema do par disjunto de caminhos.)
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 sequê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.
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. Consequê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 esboço de algoritmo para resolver o problema do emparelhamento máximo:
M = { }
enquanto existe um caminho de aumento para M faça
seja C um caminho de aumento para M
M = AC ⊕ M
(Na linha 1, poderíamos adotar qualquer emparelhamento não-vazio para começar o processo.) A dificuldade desse esboço está em encontrar um caminho de aumento.
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.
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.
Encontrar um caminho de aumento para um dado emparelhamento M é supreendentemente difícil. (Mas existe um algoritmo eficiente e muito interessante — o algoritmo de Edmonds — que faz o serviço.)
Se o grafo é bipartido (= bicromático), entretanto, então encontrar um caminho de aumento para M é muito fácil: basta adaptar um algoritmo de busca de modo que ele percorra caminhos alternantes! (A busca pode ser do tipo em largura ou do tipo em profundidade, tanto faz.) Se não existe caminho de aumento para M, nosso algoritmo encontra uma cobertura com ∣M∣ vértices, o que prova que 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, P e Q, e cada aresta tem uma ponta em P e outra em Q. Suponha que M é um emparelhamento. Seja P0 o conjunto dos vértices não-saturados de P. Faça uma busca por caminhos alternantes a partir de P0. Seja X o conjunto de todos os términos de caminhos alternantes que começam em P0. Se houver um vértice não-saturado em X ∩ Q então encontramos um caminho de aumento!
Suponha agora que X ∩ Q não contém vértices não-saturados. Então
Conclusão: o conjunto (Q ∩ X) ∪ (P − X) é uma cobertura e essa cobertura tem ∣M∣ vértices.