06 Grafos Bipartidos

Prévia do material em texto

Teoria dos Grafos
Rodrigo Machado com adaptações de Tadeu Zubaran
rma@inf.ufrgs.br tkzubaran@gmail.com
Instituto de Informática
Universidade Federal do Rio Grande do Sul
Porto Alegre, Brasil
http://www.inf.ufrgs.br
Grafos bipartidos
Um grafo simples G = (V, E) é bipartido sss V = V1 ∪ V2 onde
• V1 ∩ V2 = ∅ (conjuntos disjuntos)
• V1 e V2 são ambos conjuntos independentes de vértices de G (não há
arestas ligando diretamente dois vértices em V1 ou dois vértices em V2)
Intuição: um grafo bipartido é aquele onde toda aresta conecta um vértice em
V1 a um vértice em V2.
Exemplo:
A B C
D E F
V = {A,B, C,D, E, F}
V1 = {A,B, C}
V2 = {D, E, F}
2/8
Grafos bipartidos completos
Definição: um grafo bipartido é bipartido completo quando possui
todas as arestas possíveis entre os nodos.
Notação: Km,n (onde m e n são as cardinalidades dos conjuntos de
vértices)
Exemplo: K2,3
• •
• • •
3/8
Grafos k-partidos
Um grafo simples G = (V, E) é k-partido sss V = V1 ∪ V2 ∪ . . . ∪ Vk
onde
• V1 a Vk são todos disjuntos entre si (par a par)
• V1 a Vk são todos conjuntos independentes de vértices de G
Intuição: extensão da noção de grafo bipartido para n classes de
vértices.
Exemplo: (grafo tripartido)
A B C
D E F
V = {A,B, C,D, E, F}
V1 = {A,B}
V2 = {D, E}
V3 = {C, F}
4/8
Grafos bipartidos: exercício
Exercício: verifique se os grafos com as seguintes topologias são
bipartidos ou não.
• nulo
• completo
• caminho
• círculo
• grade
• estrela
• roda
• k-cubo
5/8
Caracterização de grafos bipartidos
Lema: todo passeio fechado p de tamanho ímpar contém um ciclo c de tamanho
ímpar.
Demonstração: por indução no tamanho de p
• caso base: (tamanho 3 em grafos simples). Tome p como c.
• passo indutivo: Pela hipótese indutiva, a propriedade vale para todo p′ onde
|p′| < |p|. Duas possibilidades para p:
◦ p não contém vértices repetidos (desconsiderando os pontos iniciais e
finais). Nesse caso, tome p como o ciclo ímpar c.
◦ p contém uma repetição de vértice em v. Portanto, v divide o caminho
fechado em dois subcaminhos fechados q e q′. Como p possui tamanho
ímpar, temos que um dos subcaminhos fechados (digamos q) possui
tamanho ímpar, sendo que |q| < |p|. Pela hipótese indutiva, q possui
ciclo ímpar.
6/8
Caracterização de grafos bipartidos (2)
Teorema: (König, 1936) um grafo é bipartido sss não contém nenhum ciclo de
tamanho ímpar.
Demonstração: (⇒): se G é bipartido, o conjunto de vértices é divisível em dois
conjuntos independentes V1 e V2. Logo, todo passeio alterna entre nodos de V1 e
V2. Portanto todo passeio fechado precisa percorrer um número par de passos. Logo,
G não contém ciclos de tamanho ímpar.
(⇐): G não contém ciclos de tamanho ímpar. Vamos mostrar que todo componente
conexo de G pode ter seus vértices divididos em dois conjuntos independentes. Tendo
isso, podemos compor uma bipartição de G.
Seja H um componente conexo de G, e u um nodo u ∈ V(H). Considere a distância
d(u, v) para cada v ∈ V(H), e classifique os nodos de H em dois subconjuntos:
X = {v | d(u, v) par } e Y = {v | d(u, v) ímpar }. Se houvesse alguma aresta
e = {a, b} interna a X ou Y, haveria um passeio de tamanho ímpar u, . . . , a, b, . . . , u.
Pelo lema do slide anterior, esse passeio teria um ciclo ímpar (contradição). Logo,
não há aresta interna a X e a Y, e portanto ambos são conjuntos independentes,
onde X ∪ Y = V(H).
7/8
	Grafos bipartidos e k-partidos