Aula número 7 – 23/10/2000

Idalécia Guerreiro Rodrigues

Maximum Bipartite Matching

Considerando que um grafo G é composto por vértices V e arcos E G = ( V , E )

Matching M é um subconjunto dos arcos de MÍE, tal que todos os vértices v Î V, e os arcos de M apenas podem incidir sobre um v

" a1 Î M (x, y) Î M

x, y, z, w são diferentes

" a2 Î M (z, w) Î M

O Maximum Bipartite Matching é aplicado apenas a grafos bipartes.

O Matching de cardinalidade máxima é o Matching Maximal.

Cardinalidade Máxima = 3 Matching Máximal

Quando todos os vértices do grafo são utilizados para as ligações, isto é, quando não existe vértices livres no grafo existe um Matching Perfeito

Matching Perfeito

O Matching não é Perfeito

Para encontrar o Maximum Bipartite Matching

Algoritmo de Ford-Fulkerson

G (V, E) G = (V, E)

1. v’ = V È ís, tý

2. E’ = í(s, u) : u Î Lý È í(u, v) : u Î L, v Î R, e (u, v) Î Rý È í(v, t) : v Î Rý

3. Atribuir a capacidade 1 a todos os arcos

Execução do algoritmo

Grafo

Passo 1 : Adiciona-se os vértices S e T ao grafo inicial

Passo 2 : Adiciona-se arcos entre o vértice S e o lado esquerdo, e entre o vértice T e lado direito

Passo 3 : Coloca-se a capacidade 1 em todos os arcos

Encontra-se o Máximo Flow

Matching Máximal

Complexidade

G = (V, E)

Card (V) = m

Card (E) = n

Complexidade Ford-Fulkerson =f(m, n)

G’ = (V’, E’)

Card (V’) = x + 2

Card (E) = y + x

Complexidade Ford-Fulkerson para encontrar o matching =f(x+2, y+x)

Problema dos Casais Estáveis

· O Matching óptimo é entre os pares de maior preferência

· Nem sempre o matching é entre os pares de maior preferência, porque pode existir vários y’s para um x. Primeiro é feito um matching e de seguida é feito um matching para os restantes y’s de acordo com as restantes ordens de preferências.

Algoritmo dos Casais Estáveis

1. Cada y faz uma proposta ao primeiro x da sua lista de preferência;

2. Cada x recebe a proposta dos y’s, vai verificar a sua lista de preferências e escolhe o y preferido;

3. Todos os y’s sem pares fazem propostas ao segundo x da sua lista de preferências;

4. Se o x com mathcing recebe um proposta, vai analisar a sua lista de preferências e caso a proposta seja feita por um y de maior preferência altera o seu matching para o novo y;

5. Volta ao ponto 3 até que todos os casais estejam estáveis.

Exercício

Executando o algoritmo de Ford-Fulkerson no grafo, mostral o garfo residual depois do fluxo de movimentos

Resolução