Seminario emparelhamento de grafos

Disponível somente no TrabalhosFeitos
  • Páginas : 16 (3871 palavras )
  • Download(s) : 0
  • Publicado : 9 de março de 2013
Ler documento completo
Amostra do texto
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
○ EmparelhamentoMá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 quenã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 deCardinalidade 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 doanterior.
● Cada aresta possui um peso positivo
● Procura-se pelo emparelhamento de maior
peso
● Exemplo
○ Vertices divididos em dois subconjuntos: Vagas e
Candidatos
○ Arestas representam o grau de aptidão (peso) para
determinada vaga.
○ Como encontrar conjuntos de candidatos cuja soma
do grau de suas aptidões seja maxima?

Exemplos de Aplicações
● Atribuição Pessoal ou Alocaçãopessoal





N funcionario
N posições em uma empresa
Cada funcionario é qualificado para uma posição
É possível de se atribuir uma posição para cada
funcionario, de tal maneira que cada um ocupe
exatamente um posição?
○ Este é um problema de emparelhamento perfeito em
grafos bipartidos.

Exemplos de Aplicações
● Atribuição Pessoal ou Alocação pessoal
○ Adicionalmente pode-seapresentar uma função que
atribui a cada funcionario um valor numérico
correspondente a sua eficiência para ocupar
determinada posição dentro da empresa.
○ O objetivo agora é achar uma alocação que
maximize a eficiencia total dos funcionarios.
○ É um problema de emparelhamento máximo em
grafos bipartidos.

Exemplos de Aplicações
● Problema dos casamentos
○ É dado um matriz de 0' e 1's,com entradas
independentes. ( sem 1's na mesma coluna ou linha)
○ Linhas são Homens.
○ Colunas são Mulheres.
○ Cada entrada na matriz representa a
compatibilidade de um Homem com um Mulher.
○ Objetivo é casar um numero máximo de casais
compativeis.
○ É um problema de cardinalidade máxima em grafos
bipartidos

Exemplos de Aplicações
● Construção de amostras
○ Um vendedor possui
■Objetos com fomas variadas (cubo, piramide,
etc)
■ Cada Objeto tem suas caracteristicas (cores)
○ Vendedor que carregar o menor número possivel de
objetos de tal maneira que cada forma e cor estejam
representados pelo menos uma vez

Exemplos de Aplicações
● Construção de amostras
○ Grafo Bipartido
■ Conjunto de Cores
■ Conjunto de formas
■ Vertice representa o objeto construido por uma...
tracking img