Grafos

Neste trabalho iremos apresentar o conceito de emparelhamento de grau maximo em grafos  bipartidos. Esta é uma área classica da teoria dos grafos e considera­se os precursores dessa área  Julius Petersen, estudando a fatoração de grafos e Dénes König, estudando grafos bipartidos. O  primeiro algoritmo para encontrar um emparelhamento maximo em grafos bipartidos foi dado por  König e Egerváry em 1930. Em 1955 foi apresentado o metodo hungaro que tinha o objetivo de  encontrar, se possível, um emparelhamento perfeito de peso máximo ou minimo em um grafo.  Um emparelhamento é um sub conjunto de arestas onde não existe duas arestas incidentes no  mesmo vertice. A figura a seguir mostra um grafo bipartido emparelhado.

Podemos observar as arestas emparelhadas do conjunto (V1, C3) e (C4, V3) e os vertices que  incidem nessas arestas emparelhadas, que são chamados saturados. Quando um vertice não incide  em uma aresta emparelhada ele é chamado não saturado. Esse grafo, apesar de estar emparelhado,  não tem a cardinalidade maxima possível, pois os vertices C1 e C2 da bipartição C e o vetice v1 da  bipartiçao V não tem grafos emparelhados incidentes a eles. A figura a seguir mostra o grafo  emparelhado e bipartido de cardinalidade máxima.

Vamos verificar como o processo de emparelhamento maximo é feito a partir de um grafo bipartido  normal. Primeiramente iniciamos a busca com todos os vertices da bipartiação C(c1,c2, c3, c4, c5) e  escolhemos para como vertice inicial o C1. Com o C1 podemos atingir os vertices v1, v2, v3. Assim  marcamos esse vertices como possiveis para o emparelhamento.

Escolhendo o v1 obtemos o primeiro emparelhamento (c1,v1) e recomeçamos a busca a partir do  vertice c2.

Com o vertice c2 podemos atingir o vertice v1, v4 e v5, porém o v1 já é incidente em um  emparelhamento portanto ele não pode ser escolhido. A proxima escolha será o vertice v4 e assim  formaremos o segundo emparelhamento (c2, v4) e recomeçamos a busca a partir o vertice c3.

O vertice c3 pode atingir o v1 e v2, porém caimos no mesmo caso do passo anterior pois o vertice  v1 já é incidente em um emparelhamento. Escolhemos o v2 formando o esparelhamento (c3,v2) e  recomeçaremos a busca a partir do vertice c4