Grafo bipartido §

---

Grafo bipartido é um grafo cujo conjunto de vértices pode ser particionado em dois subconjuntos e .

Note

Vale ressaltar que grafo bipartido é o exemplo mais simples para explicar esse conceito, porém pode ser n-partidos.

Tal que cada aresta incide em um vértice de X e um vértice em . Dessa forma, a partição é chamada bipartição do grafo.

Problema da bipartição §

Seja um grafo não direcionado. Então é bipartido se e somente se não tem ciclos ímpares.

No conjunto onde seus vértices são divididos em 2 subconjuntos e onde todas as arestas de possui uma extremidade em e outra em .

Algoritmo §

A base do algoritmo utiliza a estratégia de colocação dos vértices. No caso do grafo bipartido, chamados de bicolocação, utilizamos 2 cores (uma para o vértice em e outra em ).

Referências §

---