MO405 - Atas das Aulas

Ata de Aula:     16/09/2002
Redator:           Janaína Ruas 910645

Capítulo: 3.2 Algorithms and Applications

Tópicos Discutidos mais importantes:

1- Algoritmo do Caminho Aumentante

* O algoritmo do caminho aumentante encontra um caminho aumentante dado um grafo G bipartido X,Y e um emparelhamento M de G. Ele procura um caminho aumentante a partir de cada vértice não saturado por M em X.

* O importante é que o algoritmo do caminho aumentante, se aplicado várias vezes, produz um emparelhamento máximo no grafo bipartido. Ele também encontra uma cobertura por vértices, que é do mesmo tamanho que o emparelhamento, e é uma cobertura por vértices mínima.

* Assim, repetindo-se o algoritmo, enquanto houver caminho aumentante, para cada passo da iteração, o tamanho do emparelhamento aumenta em 1 (uma) unidade.

* Usando este método, o custo de execução para encontrar o emparelhamento máximo é O(m.n), onde m é o número de arestas e n o número de vértices.

2- Algoritmo Húngaro
O algoritmo Húngaro serve para encontrar um emparelhamento bipartido de peso máximo e também para encontrar uma cobertura por vértices de peso mínimo.

* Utiliza-se o grafo bipartido completo Km,n criado a partir do grafo bipartido original G. As arestas não existentes em G tem peso 0 (zero) em Km,n. Km,n e denominado grafo extendido (X).

2.1- O peso de um emparelhamento máximo no grafo extendido (X) é igual ao peso de um emparelhamento máximo no grafo original (G).

Isto é verdade porque cada emparelhamento de G pode ser completado com arestas de peso zero em X para formar um emparelhamento de mesmo peso em X.

Por outro lado, cada emparelhamento em X pode ser transformado em um emparelhamento de mesmo peso em G retirando-se as arestas de peso zero.

2.2- Transversal
Dada uma matriz nxn, uma transversal consiste de n posições, escolhidas de tal forma que caia exatamente uma em cada linha e uma em cada coluna.

Se olharmos a matriz nxn como representando um grafo bipartido completo ponderado, uma transversal corresponde a um emparelhamento perfeito, e vice-versa.

3- Emparelhamentos Estáveis
Dados:

• um grafo bipartido completo (Km,n) com bipartição X,Y
• uma ordem de preferências dos vértices da partição X para cada vértice da partição Y
• uma ordem de preferências dos vértices da partição Y para cada vértice da partição X

Um emparelhamento estável é um emparelhamento M onde não existe um par (x1,y1) FORA do emparelhamento tal que, ao mesmo tempo, x1 prefira y1 mais do que seu atual parceiro no emparelhamento, e também y1 prefira x1 a seu atual parceiro.
É possível encontrar um emparelhamento estável em tempo polinomial. Pode haver mais de um emparelhamento estável para a mesma lista de preferências.