Seminario emparelhamento de grafos

Emparelhamento em
Grafos

Sumario
●

●

●

●

Motivação
○ Conceitos
○ Exemplos
○ Tipos de problema
■ Emparelhamento de Cardinalidade Maxima em um Grafo Bipartido
■ Emparelhamento de Peso Maximo em um Grafo Bipartido
○ Exemplos de Aplicações
■ Atribuição Pessoal
■ Casamentos
■ Construção de amostras
Definições
○ Vertice Saturado
○ Emparelhamento Perfeito
○ Emparelhamento Máximo
○ Caminho Alternante
○ Caminho Aumentante
Emparelhamento de Peso Máximo em um Grafo Bipartido
○ Algoritmo Hungaro
■ Cenario
■ Explicação
■ Exemplos de aplicações
Referências

Motivação

Conceitos
● Emparelhamento em grafos
○ Também conhecido como acoplamento ou casamento em Grafos.
○ Formalmente: um emparelhamento M em G (grafo não-dirigido) é um conjunto de arestas que não contém mais do que uma aresta incidente no mesmo vertice.
○ Em Outras Palavras: É um conjunto de arestas independentes em um grafo G sem vertices em comum. Conceitos
● Cardinalidade
○ Numero de arestas presente em M, subconjunto de
G.

● Grafo Bipartido
○ Conjunto de vertices é dividido em 2 subconjuntos
○ Nenhum vertice é adjacente a outro vertice do mesmo subconjunto

Conceitos
● Cobertura
○ Uma cobertura C é um conjunto de arestas tal que todo vértice do grafo é extremo de pelo menos uma aresta de C
○ Em outras palavras: é um conjunto de arestas que possui, no conjunto de seus extremos, todos os vértices do grafo.

Exemplo
● Emparelhamento em grafo

Exemplo
● Grafo bipartido

Tipos de problema

Tipos de problema

Emparelhamento de Cardinalidade Maxima em um Grafo
Bipartido

● Divide-se o problema em dois conjuntos de vertices. ● Procura-se por um emparelhamento com um numero máximo de arestas.
● Exemplo
○ Vertices divididos em dois subconjuntos: Homens e mulheres. ○ Arestas representam a afinidade.
○ Qual o maior numero de casais pode-se formar?

Emparelhamento de Peso Maximo em um Grafo Bipartido

● Caso genérico do