Compreendendo as bipartições na teoria dos grafos

Na teoria dos grafos, uma bipartição de um grafo é uma divisão de seu conjunto de vértices em dois conjuntos disjuntos (chamados conjuntos de partições), de modo que todas as arestas conectem vértices de diferentes conjuntos de partições. Em outras palavras, não há arestas entre vértices no mesmo conjunto de partições.

Por exemplo, considere um gráfico com 4 vértices {a,b,c,d} e dividimos o conjunto de vértices em duas partes: {a,b} e {cd}. O gráfico é bipartido porque todas as arestas conectam vértices de partes diferentes.

A bipartição pode ser usada para reduzir a complexidade de algoritmos para problemas de gráfico, como travessia de gráfico, localização de caminho mais curto e correspondência de gráfico.