Grafos Bipartitos

Teoría

Un grafo bipartito es un tipo especial de grafo donde puedes dividir el conjunto de vértices en dos conjuntos disjuntos, que solemos llamar $U$ y $V$ (llamados partes o conjuntos bipartitos), de tal forma que cada arista del grafo conecta un vértice de $U$ con uno de $V$. En otras palabras, no hay aristas que conecten dos vértices dentro del mismo conjunto $U$, ni tampoco dentro de $V$. Esta estructura es equivalente a decir que el grafo es 2-coloreable: puedes colorear cada vértice en $U$ de negro y cada vértice en $V$ de blanco, asegurando que no haya dos vértices adyacentes con el mismo color.

En las olimpiadas de matemáticas, los grafos bipartitos son herramientas fundamentales para modelar problemas de relaciones donde interactúan dos clases distintas de objetos (por ejemplo, alumnos y clases, o trabajadores y empleos). Aparecen seguido en problemas de combinatoria sobre cuadrículas (colorear un tablero de ajedrez es básicamente definir un grafo bipartito) y en teoría de emparejamientos (matchings). Si te das cuenta de que un grafo es bipartito, puedes aprovechar propiedades muy útiles sobre la suma de los grados y la longitud de los ciclos.

La idea más importante sobre los grafos bipartitos es su relación con los ciclos. Un grafo es bipartito si y solo si no tiene ciclos de longitud impar. Esta caracterización es casi siempre el método principal para demostrar que un grafo es bipartito o que cierta estructura no puede existir. Por ejemplo, si un problema implica que existe un triángulo (un ciclo de longitud 3) o un pentágono, la estructura del grafo no puede ser bipartita.

Fórmulas Clave

Definición Un grafo $G = (V_{total}, E)$ es bipartito si $V_{total} = U \cup V$ con $U \cap V = \emptyset$, de tal forma que: $$ \forall (x, y) \in E, \quad (x \in U \land y \in V) \lor (x \in V \land y \in U) $$

Propiedad de la Suma de Grados En un grafo bipartito con partes $U$ y $V$, la suma de los grados en una parte es igual a la suma de los grados en la otra, y esto es igual al número total de aristas $|E|$: $$ \sum_{u \in U} \deg(u) = \sum_{v \in V} \deg(v) = |E| $$

Teorema de Caracterización Un grafo $G$ es bipartito si y solo si $G$ no contiene ciclos impares. $$ G \text{ es bipartito} \iff \text{todos los ciclos en } G \text{ tienen longitud par} $$

Máximo de Aristas (Caso del Teorema de Mantel / Teorema de Turán) Para un grafo bipartito con tamaños de partición $|U| = m$ y $|V| = n$, el número máximo de aristas es $mn$. Por lo tanto, para un grafo bipartito con $N$ vértices, el número máximo de aristas es: $$ |E| \le \left\lfloor \frac{N^2}{4} \right\rfloor $$

Número Cromático El número cromático $\chi(G)$ de un grafo bipartito no vacío es exactamente 2.

Demostración

Teorema: Un grafo $G$ es bipartito si y solo si no contiene ciclos impares.

Demostración:

Parte 1: $(\Rightarrow)$ Si $G$ es bipartito, no tiene ciclos impares. Toma un grafo bipartito $G$ con particiones $U$ y $V$. Considera cualquier ciclo $C$ en $G$ formado por los vértices $v_1, v_2, \dots, v_k, v_1$. Sin perder generalidad, supón que $v_1 \in U$. Como las aristas solo existen entre $U$ y $V$:

• Como $v_1 \in U$, su vecino $v_2$ tiene que estar en $V$.
• Como $v_2 \in V$, su vecino $v_3$ tiene que estar en $U$.
• En general, $v_i \in U$ si $i$ es impar, y $v_i \in V$ si $i$ es par.

Para que el camino regrese a $v_1$ (que está en $U$), el vértice anterior, $v_k$, debe estar en $V$. Para que $v_k$ esté en $V$, el índice $k$ tiene que ser par. Por lo tanto, la longitud del ciclo, $k$, debe ser par. Así, $G$ no contiene ciclos impares.

Parte 2: $(\Leftarrow)$ Si $G$ no tiene ciclos impares, es bipartito. Supón que $G$ es conexo (si no lo es, aplicas esta misma lógica a cada componente conexa). Hay que construir una bipartición $U, V$.

1. Escoge un vértice arbitrario $r$ para que sea la "raíz".
2. Para cada vértice $v \in G$, sea $d(r, v)$ la longitud del camino más corto (distancia) de $r$ a $v$.
3. Define los conjuntos $U$ y $V$ de esta manera: $$ U = { v \in G \mid d(r, v) \text{ es par} } $$ $$ V = { v \in G \mid d(r, v) \text{ es impar} } $$ Nota que $r \in U$ porque $d(r,r)=0$ (par).

Lo que hay que mostrar es que no hay dos vértices en el mismo conjunto conectados por una arista. Supón, por contradicción, que existe una arista $(x, y)$ donde ambos $x, y \in U$. Sean $d(r, x) = 2m$ y $d(r, y) = 2n$. Hay un camino de $r$ a $x$ de longitud $2m$ y un camino de $r$ a $y$ de longitud $2n$. La unión del camino $r \to x$, la arista $(x, y)$ y el camino $y \to r$ forma un paseo cerrado de longitud $2m + 1 + 2n$, que es impar. Aunque un paseo cerrado no es estrictamente un ciclo simple, un paseo cerrado de longitud impar debe contener un ciclo simple impar. Esto contradice la hipótesis de que $G$ no tiene ciclos impares.

La misma lógica aplica si $x, y \in V$ (las distancias son impares, su suma es par, más la arista da una longitud impar). Por lo tanto, no existen aristas dentro de $U$ ni dentro de $V$. Todas las aristas conectan $U$ con $V$. Así, $G$ es bipartito.

$\square$