Emparelhamentos em Grafos: Definições e Exemplos

Emparelhamentos Erika Morais Instituto de Informática Universidade Federal de Goiás Emparelhamento Definições Um emparelhamento ou matching em um grafo G V E é um conjunto de arestas M EG tal que quaisquer duas arestas não compartilham um vértice Os vértices uv incidentes a arestas de M são ditos saturados por M Os vértices que não são incidentes em nenhuma aresta de M são ditos insaturados Emparelhamento Exemplo a b c d e f g h i j k MG ad be fi cg jk Emparelhamento Máximo e Maximal Definições Um emparelhamento M é maximal se não é possível adicionar arestas a EM e é máximo se for um emparelhamento maximal que contém o maior número de arestas Todo emparelhamento máximo é maximal porém nem todo maximal é máximo Emparelhamento Exemplo a a b c b c d e f d e f g h g h a b MGa ab de gh MGb ce gh Figura a Emparelhamento Máximo b Emparelhamento Maximal Emparelhamento Perfeito Definição Um emparelhamento M é perfeito se satura todos os vértices de G a b c d e f g h MG ae bf cg dh Figura Emparelhamento Perfeito Caminhos alternantes Dado um emparelhamento qualquer M um caminho Malternante é um caminho que alterna arestas em M e arestas que não estão em M a b c d e f g h CaminhoAlternante e a f b g c h dM 4 Figura Caminho Alternante Caminhos aumentantes Um caminho Maumentante é um caminho Malternante onde os vértices inicial e final não são saturados por M a b c d e f g h CaminhoAumentante e a f b g c h dM 3 Figura Caminho Aumentante Caminhos aumentantes Se existir um caminho P em G que seja Maumentante é possível criar um novo emparelhamento M onde M M 1 e M uvuv P uv M a b c d e f g h Caminho Aumentante A e a f b g c h dM 3 Figura Caminho Aumentante Caminhos aumentantes Se existir um caminho P em G que seja Maumentante é possivel criar um novo emparelhamento M onde M M1 e M uvuv PA uv M a b c d e e e e I ot ole ot e f h Caminho Aumentante e a f b g hdM 4 Figura Emparelhamento M obtido do caminho aumentante A Resultados Teorema 1 Um emparelhamento M em G é um emparelhamento máximo se e somente se G não contém um caminho Maumentante Demonstração Seja M um emparelhamento em G e suponha que G contenha um caminho Maumentante v0v1 v2m1 Defina M EG como M Mv1v2 v3v4 v2m1v2mv0v1 v2v3 v2mv2m1 Então M é um emparelhamento em G e M M 1 Logo M não é um emparelhamento máximo Notacdo Notacdo A vizinhanga de um vértice v escrita Nv 0 conjunto de todos os vértices adjacentes a v NS Uyes Nv Alguns Resultados Teorema 2 Hall Seja G um grafo bipartido com bipartição X Y Então G admite um emparelhamento que satura todos os vértices de X se e somente se NS S para todo S X Demonstração Suponha que G possua um emparelhamento M que satura todo vértice de X e seja S um subconjunto de X Como os vértices em S estão saturados por M com vértices distintos em NS Y temos que NS S Resultados S X u a b c d e f Y g h i j k l m n NS Resultados Corolário 1 Se G é um grafo bipartido kregular com k 0 então G tem um emparelhamento perfeito Demonstração Exercício Resultados Observação Para algum emparelhamento M e alguma cobertura K temos que M K Teorema 3 Seja M um emparelhamento e K uma cobertura tal que M K Então M é um emparelhamento máximo e K é uma cobertura mínima Demonstração Seja M um emparelhamento máximo e K uma cobertura mínima Pela observação anterior temos que M M K K Como M K concluímos que M M e k K Resultados Teorema 4 Em um grafo bipartido o número de arestas em um emparelhamento máximo é igual o número de vértices em uma cobertura mínima Definição 1 Uma componente de um grafo é ímparpar se possui um número ímparpar de vértices Denotaremos por iG o número de componentes ímpares de um grafo G Teorema 5 Tutte G tem um emparelhamento perfeito se e somente se iG S S para todo S V G O problema de atribuição de pessoal O problema Em uma escola n professores x1 x2 xn são avaliados para n classes y1 y2 yn onde cada professor é qualificado para ministrar uma ou mais disciplinas Os professores podem ser todos atribuídos um por classe para classes em que são qualificados O modelo Definiremos um grafo bipartido G com V G X Y onde X x1 x2 xn é o conjunto de professores Y y1 y2 yn é o conjunto de classes e existirá a aresta xiyj se e somente se o professor xi é qualificado para ministrar a disciplina yj O problema consiste em determinar se G possui um emparelhamento que satura todos os vértices de X