Teoría de grafos · Definición
Grafo bipartito
Antes de empezar necesitas conocer
La bipartición modela emparejamientos, como estudiantes con cursos o trabajadores con tareas, y es la forma más simple de dividir un grafo en dos bandos opuestos.
Definición
Un grafo bipartito es un grafo \(G=(V,E)\) cuyos vértices se reparten en dos conjuntos disjuntos \(A\) y \(B\) de modo que cada arista \(e\in E\) une un vértice de \(A\) con uno de \(B\).
Las dos partes \(A\) y \(B\) no tienen aristas internas: todo lo que ocurre en el grafo ocurre entre un bando y el otro. Por eso un grafo bipartito no puede tener triángulos, ni en general ciclos de longitud impar. Recíprocamente, el criterio clásico asegura que un grafo es bipartito exactamente cuando todos sus ciclos tienen longitud par.
Para decidir si un grafo conexo es bipartito se pone un vértice en el bando \(A\), sus vecinos en \(B\), los vecinos de estos en \(A\), y así sucesivamente. Si en algún momento una arista une dos vértices del mismo bando, hay un ciclo impar y el grafo no es bipartito. En un grafo conexo la partición, si existe, es única salvo intercambiar \(A\) y \(B\); cada componente conexa aporta ese mismo grado de libertad.
El ejemplo guía es el grafo bipartito completo \(K_{m,n}\), con partes de \(m\) y \(n\) vértices y las \(mn\) aristas posibles entre ellas. Con \(N\) vértices, un grafo bipartito tiene a lo sumo \(\lfloor N^2/4\rfloor\) aristas. Además, como cada arista tiene un extremo en cada parte, la suma de grados en \(A\) es igual a la suma de grados en \(B\) y ambas valen \(|E|\). Un error frecuente es creer que basta con no tener triángulos: un ciclo de longitud 5 no tiene triángulos y tampoco es bipartito.
Para pensar
¿Es bipartito el grafo del cubo, con 8 vértices (las ternas de 0 y 1) y aristas entre ternas que difieren en una sola coordenada?
Sí. Tomando como \(A\) las ternas con número par de unos y como \(B\) las de número impar, cada arista cambia la paridad y por tanto une las dos partes.
Si un grafo bipartito conexo tiene \(|A|\ne|B|\), ¿se pueden intercambiar los papeles de \(A\) y \(B\)?
Solo como nombres: la partición es única, así que \(A\) y \(B\) son los dos únicos bandos posibles y lo único que cambia al intercambiarlos es cómo los llamamos.
Ejercicios 10
- ¿Cuál de los siguientes grafos es bipartito?
- ¿Cuántas aristas tiene el grafo bipartito completo \(K_{2,5}\), donde cada vértice de una parte se une con todos los de la otra?
- ¿Cuál es el máximo número de aristas de un grafo bipartito con 6 vértices?
- ¿Cuál de estas condiciones garantiza que un grafo NO es bipartito?
- Un grafo tiene vértices \(1,\dots,6\) y aristas \(\{1,4\},\{1,5\},\{2,4\},\{2,6\},\{3,5\},\{3,6\}\). ¿Cuál es una partición válida \(A\), \(B\)?
- Al ciclo \(C_6\), con vértices \(1,\dots,6\) y aristas \(\{i,i+1\}\) y \(\{6,1\}\), se le agrega una arista. ¿Cuál hace que deje de ser bipartito?
- En un grafo bipartito, los 4 vértices de la parte \(A\) tienen grado 3 y los 6 vértices de \(B\) tienen todos el mismo grado \(d\). ¿Cuánto vale \(d\)?
- Un grafo bipartito conexo tiene partes de 3 y 5 vértices. ¿Cuál es el mínimo número de aristas que puede tener?
- Un grafo con 7 vértices tiene tres componentes conexas: dos aristas aisladas y un camino de 3 vértices. ¿De cuántas formas se puede escoger la partición no ordenada \(\{A,B\}\)?
- ¿Puede un grafo con 9 vértices y 21 aristas ser bipartito?
Referencias
- Kenneth H. Rosen, Discrete Mathematics and Its Applications, 8th edition, McGraw-Hill, 2019. §10.2
- Susanna S. Epp, Discrete Mathematics with Applications, 5th edition, Cengage, 2019. §10.1
- Ralph P. Grimaldi, Discrete and Combinatorial Mathematics: An Applied Introduction, 5th edition, Pearson, 2003. §11.2