Grafos bipartitos

Un grafo $G = (V, X)$ se dice bipartito si existen dos subconjuntos $V_{1}$ , $V_{2}$ del conjunto de vértices $V$ tal que:

\begin{array}{r} V_{1} \cup V_{2} = V \\ V_{1} \cap V_{2} = \emptyset \end{array}

Y tal que todas las aristas de $G$ tienen un extremo en $V_{1}$ y otro en $V_{2}$ .

Es decir, queremos dividir al grafo en dos grupos de nodos. A su vez, en cada grupo no debe haber aristas internas, es decir, dos nodos forman parte del mismo grupo si no son vecinos en el grafo.

Un grafo bipartito con subconjuntos $V_{1}$ , $V_{2}$ , es bipartito completo si todo vértice en $V_{1}$ es adyacente a todo vértice en $V_{2}$ .

flowchart LR

name(No es bipartito)

id1((1))
id2((2))
id3((3))

id1 --- id2
id2 --- id3
id3 --- id1

flowchart LR

name(Es bipartito)

id1((1))
id2((2))
id3((3))
id4((4))
id5((5))
id6((6))
id7((7))
id8((8))

id1 --- id2
id1 --- id4
id1 --- id5
id3 --- id7
id3 --- id4
id2 --- id6
id2 --- id3
id4 --- id8
id5 --- id6
id5 --- id8
id6 --- id7
id7 --- id8

El segundo dibujo representa un grafo bipartito, ya que podríamos tomar $V_{1} = {v_{1}, v_{3}, v_{6}, v_{8}}$ y $V_{2} = {v_{2}, v_{4}, v_{5}, v_{7}}$ , separando el grafo en partes completamente inconexas.

Un teorema muy útil dice que un grafo $G$ es bipartito si y solo si no tiene ciclos de longitud impar.