Aula 17 - EMPARELHAMENTO
Suponhamos cinco candidatos c1, c2, c3, c4 e c5 para as cinco vagas de uma empresa: v1, v2,
v3, v4 e v5. Suponhamos também que nem tudo mundo tem as competências para todas as
vagas. O candidato c1 pode concorrer para as vagas v2 e v3, c2 para as vagas v2 e v5, c3 para
as vagas v1, v3 e v4, c4 para as vagas v3 e v5 e, finalmente, c5 para as vagas v2 e v3. Isso pode
ser representado por um grafo bipartido como ilustrado na figura 1, onde cada aresta liga
um candidato a uma vaga que ele poderia eventualmente ocupar.
Figura 1
A questão agora é a seguinte: é possível empregar cada candidato de tal maneira que cada
um ocupa uma das vagas disponíveis? Em teoria dos grafos, isso é o problema de
emparelhamento de um subconjunto de vértices em um outro subconjunto de vértices. Em
outras palavras, um emparelhamento é um subconjunto de arestas onde não existem duas
arestas incidentes a um mesmo vértice. Chamaremos emparelhamento saturado um
emparelhamento onde nenhuma aresta pode ser acrescentada. Note que o conceito de
emparelhamento vale para todo tipo de grafo, não somente para os grafos bipartidos (veja,
por exemplo, o exercício 7-3).
Um grafo pode ter mais de um emparelhamento saturado. Por exemplo, o grafo ilustrado na
figura 2a pode ter os dois emparelhamentos saturados ilustrados em 2b e 2c. Nos dois
casos, não é possível acrescentar mais uma aresta ao emparelhamento, e o segundo contém
mais arestas do que o primeiro. Particularmente interessante é o emparelhamento saturado
de um grafo que contém o maior número de arestas. Tal emparelhamento será dito
máximo.
Figura 2
Mesmo se o conceito de emparelhamento é definido de maneira geral para qualquer grafo,
nós estudaremos somente a sua aplicação a grafos bipartidos. Voltando ao nosso problema
inicial, podemos ver agora que ele se resume a procurar um emparelhamento máximo.
Primeiro, gostaríamos de saber se existe, no grafo bipartido, um emparelhamento
completo. Isto é, supondo o grafo divido em dois conjuntos de vértices V1 e V2, um
emparelhamento que contém todo vértice de V1. Evidentemente, uma condição para ter esse
emparelhamento completo é que o número de vértices em V2 seja igual ou maior ao número
de vértices no conjunto V1. Mas isso não é suficiente. No exemplo da figura 1, não é
possível obter tal emparelhamento completo, apesar do número de candidatos ser igual ao
número de vagas. Isso nos leva a um teorema importante.
Teorema 1: Um emparelhamento completo em um grafo bipartido decomposto em dois
subconjuntos V1 e V2 existe se e somente se todo subconjunto de r vértices de V1 é
coletivamente adjacente a no mínimo r vértices de V1.
Graças a esse teorema, podemos concluir que não existe emparelhamento completo para o
grafo da figura 1. Considere o conjunto de vértice {c1, c2, c4, c5}. Eles são ligados somente
aos três vértices {v2, v3, v5}. Segundo o teorema 1, como o número de vértices no segundo
conjunto é inferior ao número de vértices contidos no primeiro, não existe emparelhamento
completo nesse grafo.
Figura 3
Considere agora o grafo da figura 3. Qualquer que seja o subconjunto de {c1, c2, c3, c4, c5},
sempre existe um número de elementos superior ao número de elementos no conjunto de
vértices adjacentes. Por exemplo, o conjunto de vértices adjacentes ao conjunto {c1, c2, c3}
é o conjunto {v1, v2, v3, v4, v5}, que contém mais elementos.
O problema com o teorema 1 é que ele exige muitos testes para determinar se existe um
emparelhamento completo. O número de testes requerido é igual ao número de
subconjuntos possíveis. Sabendo que o número de subconjuntos de um conjunto de n
elementos é igual a 2n, deveríamos realizar 32 testes no nosso exemplo. É fácil ver que com
um grafo maior a situação rapidamente fica inviável.
Existe um outro teorema mais fraco que dá uma condição suficiente, mas não necessária,
para que um grafo tenha um emparelhamento completo.
Teorema 2: Seja um grafo bipartido decomposto em dois conjuntos V1 e V2. É possível
identificar um emparelhamento completo nesse grafo se existe (mas não necessariamente)
um valor inteiro m tal que o grau de todo vértice em V1 é superior ou igual a m e o grau de
todo vértice em V2 é inferior ou igual a m .
Infelizmente o grafo da figura 3 não respeita a condição do teorema 2 apesar de permitir um
emparelhamento completo, como ilustrado na figura 4:
Figura 4
O grafo da figura 5a respeita a condição do teorema 2. O grau mínimo no conjunto de
vértices {c1, c2, c4, c5} é 2, enquanto o grau máximo no conjunto {v1, v2, v3, v4, v5} é 2.
Então deve existir um emparelhamento completo nesse grafo. Tal emparelhamento é
ilustrado na figura 5b.
Figura 5
Agora que está resolvido o problema da existência, vamos considerar outro problema mais
interessante: como achar um emparelhamento completo, se ele existe, ou, se ele não existe,
achar um emparelhamento máximo? Uma primeira abordagem consiste em uma busca,
começando com um emparelhamento que é o conjunto vazio. A cada etapa da busca
acrescentamos no conjunto uma aresta. Se o resultado não é um emparelhamento (isto é, ele
contém duas arestas incidentes ao mesmo vértice) retiramos essa última aresta, recuamos
nas etapas anteriores até encontrar uma que contém possibilidades não consideradas ainda e
continuamos o processo a partir desse ponto. O algoritmo pára quando achamos um
emparelhamento completo.
Esse algoritmo que é na verdade uma busca em profundidade e tem a vantagem da
simplicidade. Infelizmente, ele tem um tempo de execução exponencial. Na figura 6 é
ilustrado um momento na busca para o grafo da figura 3. A configuração atualmente
considerada é indicada por um quadro. Podemos ver que essa configuração não é válida e o
algoritmo vai recuar de novo. Basicamente, nesse exemplo, podemos ver que no primeiro
nível da busca tem 12 configurações que podem ser consideradas no pior caso. No segundo
nível, existem 12x11 configurações; no terceiro, 12x11x10 configurações, e assim por
diante.
Figura 6
No pior caso, se não existe emparelhamento completo para o grafo, ou se a configuração
solução é no último nodo da árvore, todas as configurações possíveis serão visitadas.
Portanto, esse algoritmo tem um tempo de execução em O(a!), onde a é o número total de
arestas.
Vamos agora ver um algoritmo mais eficiente. Primeiro, é preciso definir o conceito de
caminho de expansão. Seja M um emparelhamento para um grafo G. Um vértice é dito
mapeado se ele é uma das extremidades de uma aresta de M. Sejam u e v dois vértices não
mapeados. Um caminho que vai de u até v alternando aresta de M com arestas que não
pertencem a M é chamado caminho de expansão em relação a M. Consideremos tal
caminho estendido. Se agora retiramos de M toda aresta desse caminho que pertence a M e
acrescentamos a M as outras arestas do caminho, o resultado é um novo emparelhamento
M' que contém uma aresta a mais.
Figura 7
Veja por exemplo o grafo da figura 7. O emparelhamento M ilustrado contém duas arestas.
Considere agora o caminho de expansão (c4, v5, c2, v2, c1, v3). Aplicando a técnica do
caminho de expansão, obtemos um novo emparelhamento M' ilustrado na figura 8.
Figura 8
Com essa técnica, existem várias maneiras de aumentar o emparelhamento. Considere por
exemplo o mesmo grafo da figura 7 com o mesmo emparelhamento, mas com o caminho
estendido (c5, v2, c1, v3). Nesse caso, o emparelhamento M' resultante é como ilustrado na
figura 9.
Figura 9
Eis o algoritmo para identificar um emparelhamento máximo de um grafo bipartido:
1. Começar com um emparelhamento M vazio.
2. Identificar um caminho de expansão para ampliar o emparelhamento M.
3. Repetir a etapa 2 até obtenção de um emparelhamento máximo ou até um momento
em que não se encontra nenhum caminho de expansão.
Para ampliar o emparelhamento na etapa 2, efetuamos um busca em largura da seguinte
maneira: Começamos com uma floresta de árvore que contém todos os vértices não
mapeados do conjunto V1. Depois acrescentamos, para cada nodo folha, um vértice de V2
ligado com essa folha por uma aresta que não pertence a M. Depois, acrescentamos às
folhas todo vértice de V1 ligado por uma aresta que pertence a M. Alternamos assim por
diante até que apareça na busca um vértice não mapeado de V2, ou que não seja mais
possível acrescentar mais vértices. Quando a busca termina, pegamos um vértice v não
mapeado que pertence a V2 e que se encontra em uma folha da árvore. Seja r a raiz da sua
árvore. O caminho de r até v é um caminho de expansão. Utilizamo-lo para ampliar o
emparelhamento. Se não existir tal vértice, o algoritmo termina e temos um
emparelhamento máximo.
Vamos ilustrar o algoritmo com o grafo da figura 3. Na primeira tentativa de ampliação do
emparelhamento M (inicialmente vazio) a busca começa com todos os vértices c1, c2, c3,
c4c, 4. A partir de c1, podemos atingir v1, v2 e v3. Isso é ilustrado na figura 10. Como
nenhum desses vértices é mapeado, escolhemos qualquer um deles para formar o caminho
de expansão.
Figura 10
Supondo que v1 é selecionado, temos o caminho de expansão (c1,v1), que resulta no
emparelhamento ilustrado na figura 11. Na próxima expansão do emparelhamento, a busca
é inicializada com os vértices c2, c3, c4 e c5.
Figura 11
Como podemos ver na figura 11, temos uma situação semelhante à precedente, que resulta
no emparelhamento ilustrado na figura 12. Idem para as duas próximas etapas, que resultam
nos emparelhamentos das figuras 13 e 14.
Figura 12
Figura 13
O mais interessante é a situação que temos na última etapa do algoritmo. Com o
emparelhamento da figura 14, o único vértice não mapeado que sobra no conjunto V1 é o
vértice c5. A partir desse vértice, podemos somente atingir v1, que já foi mapeado. Então,
devemos continuar a busca. A partir de v1, o único lugar onde podemos chegar usando
somente arestas de M é o vértice c1. De novo continuamos a busca, que acrescenta os
vértices v2 e v3, ambos mapeados. De v2 podemos chegar a c3 e de v3 podemos ir até c4. A
próxima espansão acrescenta o vértice v1 abaixo de c3. Como v1 já é um vértice mapeado, a
busca não não continuará nesse ramo. De c4 podemos ir até v4 e v5. Como v5 não é um
vértice mapeado, a busca termina aqui, com a identificação do caminho de expansão (c5, v1,
c1, v3, c4, v5). Usando esse caminho de expansão para ampliar M, obtemos o
emparelhamento da figura 15.
Figura 14
Figura 15
Note que o algoritmo, aplicado aqui aos grafos bipartidos, pode ser usado com qualquer
grafo.