Grafos

1 GRAFOS BIBARTIDOS

Um grafo é chamado bipartido quando seu conjunto de vértices pode ser divido em dois subconjuntos distintos V1 e V2, tais que todas as arestas do grafo, possuam, em suas extremidades, um vértice de cada subconjunto. Isto significa que o grafo bipartido não pode conter uma aresta que ligue dois vértices de um mesmo subconjunto, como mostra a Figura 1.
Teorema: Um grafo é bipartido se e somente se todo ciclo de G possuir comprimento par.

Figura 1 – Grafo bipartido.

Chamamos de grafo bipartido completo, o grafo bipartido que possua uma aresta entre cada par qualquer de vértices V1 e V2. O grafo bipartido completo é denotado por Kn1,n2, onde N1 é a quantidade de vértices do subconjunto V1 e N2 a quantidade de vértices do conjunto V2. A Figura 2 mostra o exemplo de um grafo bipartido completo.
Vemos que um grafo é bipartido, precisamente quando os vértices podem ser coloridos com duas cores de modo que nenhuma aresta une dois vértices de mesma cor, como mostra a Figura 3. Tal coloração é impossível no caso de um grafo que não é bipartido, como um triângulo, depois de um nó ser colorido de preto e outro de branco, o terceiro vértice do triângulo é ligado a vértices de ambas as cores, impedindo que seja atribuída qualquer cor.

Figura 2 – Grafo bipartido completo.

Figura 3 – Exemplo de um grafo bipartido.

2 REFERÊNCIAS

ANDERSON, I. A first course in discrete mathematics. Heidelberg: Springer, 2001.

FIGUEIREDO, R. T. Teoria dos grafos. Petrolina, 2010.

JURKIEWICZ, S. Grafos. Disponível em: <http://200.17.137.109:8081/novobsi/Members/silvana/matematica-discreta-1o-2011/GrafosModfrancisca.pdf>. Acesso em: 18 de agosto de