Comprender las biparticiones en la teoría de grafos

En teoría de grafos, una bipartición de un gráfico es una división de su conjunto de vértices en dos conjuntos disjuntos (llamados conjuntos partitos) de modo que todos los bordes conectan vértices de diferentes conjuntos partitos. En otras palabras, no hay aristas entre los vértices en el mismo conjunto de particiones. Por ejemplo, considere un gráfico con 4 vértices {a,b,c,d} y dividimos el conjunto de vértices en dos partes: {a,b} y {cd}. El gráfico es bipartito porque todos los bordes conectan vértices de diferentes partes. La bipartición se puede utilizar para reducir la complejidad de los algoritmos para problemas de gráficos como el recorrido del gráfico, la búsqueda de la ruta más corta y la coincidencia de gráficos.