Grafo bipartido

---

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

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 $Y$. Dessa forma, a partição $(X,Y)$ é chamada bipartição do grafo.

Problema da bipartição

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

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

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 $A$ e outra em $B$).

Referências

---