Digressão por
‘caminhos, árvores e flores’
João Soares
Departamento de Matemática
Universidade de Coimbra
Hotel Quinta das Lágrimas (Coimbra), 15 de Outubro de 2003
Homenagem ao Professor Doutor Mário Silva Rosa
Índice
Emparelhamento
1.
1.
2.
Definições e motivação
Estrutura poliedral (Cunningham & Marsh, 1978)
Emparelhamento de Cardinalidade Máxima
2.
1.
2.
Em grafos bipartidos
Em grafos não bipartidos (Edmonds, 1965a)
Emparelhamento de Peso Máximo
3.
1.
Em grafos bipartidos (Kuhn,1955)
Emparelhamento
(definição)

Seja G=(V,E) um grafo não orientado
V=vértices, E=arestas, com ‘pesos’ ce, e  E.

Um emparelhamento de G é um subconjunto das arestas sem
extremidades em comum.

Peso de um emparelhamento é a soma dos pesos das arestas do
emparelhamento.

Um emparelhamento diz-se perfeito se “cobre” todos os
vértices.
Emparelhamento
(exemplos)
h
e
a
f
b
1
6
2
7
3
8
4
9
5
10
g
c
In Korte&Vygen (2000)
d
In Nemhauser&Wolsey (1988)
Emparelhamento
(exemplos)
...de máxima cardinalidade?
h
e
a
f
b
1
6
2
7
3
8
4
9
5
10
g
c
In Korte&Vygen (2000)
d
In Nemhauser&Wolsey (1988)
Emparelhamento
(motivação)

Afectar individuos a tarefas
(... perfeito de peso máximo em G bipartido ≡ Afectação)

Emparelhar colegas de quarto em dormitório
(... perfeito de peso máximo)

Heurística para TSP Simétrico e Euclidiano
(... perfeito de peso máximo)

Problema do Carteiro Chinês
(... perfeito de peso máximo)

Afectar alunos a Universidades
(... perfeito tal que não haja nenhum par que fique melhor trocado)
Emparelhamento
(algebra)
Problema de Programação Inteira:
max
c x
 x  1
e E
s.a
e
e  (i )
ou
e
e
(i  V )
(rest. de grau)
xe  0
(e  E ) (nao negatividade)
xe 
(e  E )
(integralidade)
max cx s.a Ax  1, x  0, x 
m
com A matriz de incidência vértice-aresta de G
Emparelhamento
(estrutura poliedral)

Cunningham e Marsh, 1978:
O seguinte sistema de desigualdades é TDI:

xe  1
(i V )

S 1
xe 
2
(i  A  S  V : S impar)
e  (i )
e  E( S )
xe  0
(e  E )
Corolário: Emparelhamento de peso máximo é um Problema Linear, embora com
um número exponencial de restrições (Edmonds, 1965b).
Dificuldade: Como lidar com um tão elevado número de restrições em tempo
polinomial?
Vantagem: Possível explicitar uma caracterização algébrica do invólucro convexo
para qualquer problema de emparelhamento de peso máximo.
Emparelhamento
(Berge, 1957)

Caminho aumentado relativamente a um emparelhamento M:
M



M
M
M
M
M
M
Berge, 1957: Um emparelhamento M é de máxima
cardinalidade se e só se não existe caminho aumentado
relativamente a M.
DEM: “” Por absurdo. Trivial. “” Por absurdo, existe
|M’|>|M|. Então, F=MM’ é um conjunto de circuitos e
caminhos simples. Circuitos têm número par de arestas. Como
|M’|>|M|, existe um dos caminho simples que é aumentado(!).
Ideia para obter emparelhamento de máxima cardinalidade:
Identificar sucessivos caminhos aumentados.
Emparelhamento

Encontrar emparelhamento de máxima cardinalidade num
grafo bipartido
1
6
2
7
3
8
4
9
5
10
Emparelhamento

Encontrar emparelhamento de máxima cardinalidade num
grafo bipartido:
Vértice exposto
* 1
6
2
7
3
8
4
9
5
10
Emparelhamento

Encontrar emparelhamento de máxima cardinalidade num
grafo bipartido:
* 1
6
7 2
7 1
3
8
4
9
5
10
Emparelhamento

Encontrar emparelhamento de máxima cardinalidade num
grafo bipartido:
* 1
6
7 2
7 1
8 3
8 2
4
9
5
10
Emparelhamento

Encontrar emparelhamento de máxima cardinalidade num
grafo bipartido:
* 1
6 3
7 2
7 1
8 3
8 2
4
9 3
5
10 3
Caminho aumentado:
1, 7, 2, 8, 3, 6
Emparelhamento

Encontrar emparelhamento de máxima cardinalidade num
grafo bipartido:
* 1
6 3
7 2
7 1
8 3
8 2
4
9 3
5
10 3
Rótulas permitem identificar
Novo emparelhamento
Emparelhamento

Encontrar emparelhamento de máxima cardinalidade num
grafo bipartido:
Vértice exposto
1
6
2
7
3
8
4
9
*5
10
Emparelhamento

Encontrar emparelhamento de máxima cardinalidade num
grafo bipartido:
1
6
2
7 5
3
8 5
4
9
*5
10 5
Emparelhamento

Encontrar emparelhamento de máxima cardinalidade num
grafo bipartido:
71
6
82
7 5
3
8 5
10 4
*5
9
10 5
Não existe caminho aumentado a partir de 5!
Existe a partir de 9?
Emparelhamento
Encontrar emparelhamento de máxima cardinalidade num
grafo bipartido:

V1
+
V1-
71
6
82
7 5
3
8 5
10 4
*5
9
V2+
V2-
10 5
Não existe caminho aumentado a partir de 5!
Existe a partir de 9?
Emparelhamento
(em grafos bipartidos)




Quando um vértice adquire uma posição relativa num caminho
alternado ( ou ) essa posição relativa é igual em qualquer
caminho aumentado.
Por isso, qualquer rotulação de um vértice é definitiva o que
facilmente implica que averiguação de um caminho alternado
pode ser implementado em O(n2) operações.
Em conclusão, a determinação de um emparelhamento de
máxima cardinalidade num grafo bipartido pode ser efectuada
em O(n3) operações.
No final, R=V1- V2+ é uma
V1+
V2+
cobertura por vértices de G
tal que |R|=|M|.
V1-
V2-
Emparelhamento
(em grafos não bipartidos)

Vejamos se a mesma ideia funciona com grafos não bipartidos
h
e
Vértice exposto
f
g
*
a
b
c
d
Emparelhamento
(em grafos não bipartidos)

Vejamos se a mesma ideia funciona com grafos não bipartidos
h
b
e
f
g
*
a
b
a
c
d
Emparelhamento
(em grafos não bipartidos)

Vejamos se a mesma ideia funciona com grafos não bipartidos
h
b
e
ef
g
*
a
b
a
e
c
d
Emparelhamento
(em grafos não bipartidos)

Vejamos se a mesma ideia funciona com grafos não bipartidos
h
b
e
ef
gf
*
a
b
a
e
c
c
d
Emparelhamento
(em grafos não bipartidos)

Vejamos se a mesma ideia funciona com grafos não bipartidos
Vértice d pode receber rótulo ou .
Foi encontrado circuito ímpar!
Como enumerar caminhos alternados
de modo eficiente?
h
b
e
ef
gf
*
a
b
a
e
c
c
d
Emparelhamento
(em grafos não bipartidos)




Para Berge (1957) isso não seria problema - enfim, há um número finito de
caminhos alternados.
Pois, só com Edmonds (1965a) veio a primeira proposta de enumeração
eficiente de caminhos alternados no célebre Paths, trees and flowers.
Edmonds (1965a) usou a palavra good para se referir a funcionar em tempo
polinomial – só mais tarde com Karp e Cook (anos 70) veio o rigor e o
formalismo da classificação de problemas.
A ideia:
Sempre que for encontrado um vértice que pode ser do tipo ou
então
substituir todos esses vértices do circuito ímpar encontrado por um novo
vértice e retomar a procura de um caminho aumentado.

Ilustramos esta ideia com o exemplo anterior, ...
Emparelhamento

Encontrar emparelhamento de máxima cardinalidade num
grafo não bipartido:
h
b
e
h
ef
gf
Ub
*
a
b
a
e
c
c
d
a
b
a
Emparelhamento

Encontrar emparelhamento de máxima cardinalidade num
grafo não bipartido:
U, f
h
h
b
e
ef
gf
Ub
*
a
b
a
e
c
c
d
a
b
a
Caminho aumentado encontrado: a,
b, U, h
Mais precisamente: a, b, e, c, d, g, f, h
Emparelhamento
(em grafos não bipartidos)

Encontrar emparelhamento de máxima cardinalidade num
grafo não bipartido:
h
b
e
ef
gf
*
a
b
a
e
c
c
d
Emparelhamento
(em grafos não bipartidos)

Encontrar emparelhamento de máxima cardinalidade num
grafo não bipartido:
h
b
e
ef
gf
*
a
b
a
e
c
c
d
Emparelhamento
(em grafos não bipartidos)

Encontrar emparelhamento de máxima cardinalidade num
grafo não bipartido:
h
e
a
f
b
g
c
d
Emparelhamento
(em grafos não bipartidos)

Notação introduzida por Edmonds, 1965a:
y
x
u
v
d
a
b
c
Emparelhamento
(em grafos não bipartidos)

Notação introduzida por Edmonds, 1965a:
y
x
u
v
d
a
b
c
Encontrado vértice
que pode ser rotulado de
dois modos diferentes
Emparelhamento
(em grafos não bipartidos)

Notação introduzida por Edmonds, 1965a:
y
x
u
v
d
a
b
c
Flower: a união dos dois
caminhos alternados
encontrados
Emparelhamento
(em grafos não bipartidos)

Notação introduzida por Edmonds, 1965a:
y
x
u
v
a
b
Stem: o caminho comum
àqueles dois caminhos alternados
d
c
Flower: a união dos dois
caminhos alternados
encontrados
Emparelhamento
(em grafos não bipartidos)

Notação introduzida por Edmonds, 1965a:
y
x
u
v
d
a
b
Stem: o caminho coumum
àqueles dois caminhos
Flower: a união dos dois
caminhos alternados
encontrados
c
Blossom: o circuito ímpar encontrado
(que vai ser substituído por um novo
vértice – shrinked).
Emparelhamento
(em grafos não bipartidos)






Cada um dos vértices do Blossom pode ser rotulado com ou para uma
escolha adequado da ordem pela qual o circuito ímpar é percorrido
alternadamente.
Apenas uma aresta do emparelhamento é incidente no Blossom. Essa aresta
é a última do stem.
Por isso, podemos interpretar o Blossom como um grande vértice rotulado
com . As suas arestas incidentes são as arestas incidentes de todos os
vértices do Blossom. Contraccão! Sucede-se a procura de um caminho
aumentado como normalmente.
Quando um caminho aumentado for encontrado, recuperam-se as arestas
desse caminho usando os rótulos e escolhendo as orientações adequadas
sempre um vértice associado a um Blossom é encontrado.
Se um caminho aumentado não for encontrado deve tentar-se um outro
vértice exposto. Podem manter-se todas as contracções entretanto
efectuadas.
Como a rotulação de vértices é sempre definitiva, o algoritmo pode ser
implementado em O(n3) operações – implementação mais delicada do que
no caso bipartido.
Emparelhamento
(de peso máximo num grafo bipartido)



Encontrar emparelhamento perfeito de peso máximo num grafo
bipartido G (Kuhn, 1955)
Sem perda de generalidade, suponhamos que G é completo
(arestas inexistentes têm peso -). Afectação!
Uma formulação é
n
n
max
c
i 1
j 1
n
s.a
x
j 1
ij
n
x
i 1
ij
ij
xij
1
(i  1, 2,
, n)
1
( j  1, 2,
, n)
xij  0
xij 
(i, j  1, 2,
(i, j  1, 2,
Nota: Matriz das restrições é TU.
Por isso, restrições de integralidade podem ser ignoradas.
, n)
, n)
Emparelhamento
(de peso máximo num grafo bipartido)



Teorema (Kuhn, 1955): Um ponto X é óptimo para o problema da
Afectação se e só se existirem vectores u,v satisfazendo cij – ui – vj  0 tal
que X é vector característico de um emparelhamento perfeito no grafo
G[u,v]=(V,E[u,v]), com E[u,v] = {(i,j): cij – ui – vj =0 }.
DEM: Dualidade Forte da P.L.
Ideia: Construir G[u,v] para u,v satisfazendo cij – ui – vj  0.
Obter M emparelhamento de máxima cardinalidade em G[u,v]. Se |M|=n
então parar, senão modificar u,v de modo a obter mais uma aresta em M
sem violar cij – ui – vj  0.
Emparelhamento
(de peso máximo num grafo bipartido)

Consideremos o seguinte problema de Afectação:
1
1’
2
2’
3
3’
4
4’
 27 17 7 8
 14 2 10 2 

(cij )  
 12 19 4 4 


 8 6 12 6 
Emparelhamento
(de peso máximo num grafo bipartido)

Como valores iniciais, considerem-se
u=(0,-2,0,0), v=(27,19,12,8)
G[u,v]
1
1’
c  c
ij
2
2’
3
3’
4
4’
ij

 ui  v j 
 0  2 5 0 
 11 15 0 4 


 15
0 8 4 


 19 13 0 2 
Emparelhamento
(de peso máximo num grafo bipartido)

Como valores iniciais, considerem-se
u=(0,-2,0,0), v=(27,19,12,8)
G[u,v]
1
1’
c  c
ij
2
2’
3
3’
4
4’
ij

 ui  v j 
 0  2 5 0 
 11 15 0 4 


 15
0 8 4 


 19 13 0 2 
Emparelhamento
(de peso máximo num grafo bipartido)

Como valores iniciais, considerem-se
u=(0,-2,0,0), v=(27,19,12,8)
G[u,v]
1
1’
c  c
ij
* 2
2’
3
3’
4
4’
ij

 ui  v j 
 0  2 5 0 
 11 15 0 4 


 15
0 8 4 


 19 13 0 2 
Emparelhamento
(de peso máximo num grafo bipartido)

Como valores iniciais, considerem-se
u=(0,-2,0,0), v=(27,19,12,8)
G[u,v]
1
1’
c  c
ij
* 2
3
3’ 4
2’
3’ 2
4’
ij

 ui  v j 
 0  2 5 0 
 11 15 0 4 


 15
0 8 4 


 19 13 0 2 
Emparelhamento
(de peso máximo num grafo bipartido)

Como valores iniciais, considerem-se
u=(0,-2,0,0), v=(27,19,12,8)
G[u,v]
1
1’
c  c
ij
* 2
3
3’ 4
2’
3’ 2
4’
V1+={2,4}, V2-={1’,2’,4’},
ij

 ui  v j 
 0  2 5 0 
 11 15 0 4 


 15
0 8 4 


 19 13 0 2 
Emparelhamento
(de peso máximo num grafo bipartido)

Como valores iniciais, considerem-se
u=(0,-2,0,0), v=(27,19,12,8)
G[u,v]
1
1’
c  c
ij
* 2
3
3’ 4
2’
3’ 2
4’
V1+={2,4}, V2-={1’,2’,4’},
ij

 ui  v j 
 0  2 5 0 
 11 15 0 4 


 15
0 8 4 


 19 13 0 2 
Emparelhamento
(de peso máximo num grafo bipartido)

Após adequada modificação: u=(0,-4,0,-2), v=(27,19,14,8)
G[u,v]
1
c  c
1’
ij
* 2
3
3’ 4
2’
3’ 2
4’
ij

 ui  v j 
0
 0  2 7
 9 13

0

2


 15
0 10 4 


0 0
 17 11
Nota importante: os rótulos anteriores permanecem válidos
Emparelhamento
(de peso máximo num grafo bipartido)

Após adequada modificação: u =(0,-4,0,-2), v=(27,19,14,8)
G[u,v]
1
1’
c  c
ij
* 2
2’
3
3’ 2
3’ 4
4’ 4
ij

 ui  v j 
0
 0  2 7
 9 13

0

2


 15
0 10 4 


0 0
 17 11
Caminho aumentado encontrado!
Emparelhamento
(de peso máximo num grafo bipartido)

Após adequada modificação: u =(0,-4,0,-2), v=(27,19,14,8)
G[u,v]
1
1’
c  c
ij
* 2
2’
3
3’ 2
3’ 4
4’ 4
ij

 ui  v j 
0
 0  2 7
 9 13

0

2


 15
0 10 4 


0 0
 17 11
Caminho aumentado encontrado!
Emparelhamento
(de peso máximo num grafo bipartido)

Após adequada modificação: u =(0,-4,0,-2), v=(27,19,14,8)
G[u,v]
1
1’
2
2’
3
3’
4
4’
Portanto, pelo Teorema de Kuhn,
encontrámos solução ‘optima
x11 = x21 = x32 = x44 = 1,
de valor
(0-4+0-2)+(27+19+14+8)=62.
Emparelhamento
(de peso máximo num grafo bipartido)

No final de cada iteração (após modificacao de u e de v):





Por isso, no final de cada iteração, um dos seguintes acontece:




Os custos reduzidos permanecem não positivos.
Os rótulos permanecem válidos.
O emparelhamento de máxima cardinalidade permanece
emparelhamento no novo G[u,v].
É criada pelo menos uma aresta (i,j) com i V1+ e j V2É encontrado um emparelhamento com mais uma aresta, ou
O conjunto V2+ fica com mais um vértice.
Por isso, o esforço computacional envolvido em aumentar uma
unidade ao emparelhamento é O(n2).
O método Húngaro termina após O(n3) operações.
Conclusão
1.
Recordámos os métodos clássicos para a determinação de
um emparelhamento de cardinalidade máxima.
2.
Procurámos justificar o desempenho desses métodos
(detalhes no documento em papel) recorrendo a imagens e
exemplos.
3.
Recordámos o método Húngaro usando uma notação que o
torna uma extensão do método anterior para o caso
bipartido.