Emparelhamentos bipartidos

Questões-guia:

1. Quantos emparelhamentos perfeitos existem em K_n,n?
2. Para cada inteiro n ≥ 3, mostre um grafo com n vértices onde existe um emparelhanto maximal que não é máximo.  Mostre um caminho aumentante para estes emparelhamentos.
3. Qual a importância algorítmica do teorema de Hall?
4. Como coberturas por vértices podem nos ajudar a garantir que um emparelhamento é máximo?
5. Nos números α(G), α'(G), β(G), β'(G), o que significa a linha (')?  E quais destes números somam n(G)?  Em que condições?
6. O efeito do Algoritmo 3.2.1 pode ser conseguido com uma BFS ou DFS modificada?  Qual seria a complexidade deste algoritmo modificado?
7. Por que o problema de emparelhamento de peso máximo em grafos bipartidos ponderados pode ser reduzido a bipartidos completos?  E, ainda por cima, com partes do mesmo tamanho?
8. Como se generaliza a noção de cobertura por vértices em grafos bipartidos ponderados?
9. O Algoritmo Húngaro p/ resolver o problema de emparelhamento de peso máximo num grafo bipartido utiliza qual outro algoritmo como subrotina fundamental?

Exercícios:

Para entender o Algoritmo Húngaro, um bom exercício é ver as coisas acontecendo numa planilha de cálculo.  Pegue um exemplo do livro e coloque numa planilha da seguinte forma.

1. Separe uma região n × n da planilha para colocar a entrada.
2. A seguir, ao lado ou embaixo da entrada, escolha outra região n × n da planilha para codificar um emparelhamento.  Esta região terá apenas zeros e uns.
3. Numa outra região do mesmo tamanho, faça a multiplicação da região entrada pela do emparelhamento, elemento a elemento, obtendo os pesos das arestas do emparelhamento.  Faça uma célula conter o peso total deste emparelhamento.
4. Finalmente, numa outra região do mesmo tamanho, compute a matrix de excessos.  Nesta região é interessante ladear as bordas superior e esquerda com uma cobertura.  Faça uma célula conter o peso total desta cobertura.
5. Após este arranjo, o algoritmo pode ser "executado" mexendo apenas no emparelhamento e na cobertura, até que seus pesos fiquem iguais.