Gráficas bipartitas y emparejamientos

Contenido

Gráficas bipartitas y emparejamientos#

Introducción#

En algunas ocasiones queremos emparejar objetos que son de dos naturalezas distintas. Por ejemplo, quizás tenemos una cierta colección alimentos, y una cierta colección de bebidas, y queremos decir cuándo un alimento es compatible con una bebida, sin que nos importe cuáles alimentos son compatibles entre sí, o cuáles bebidas son compatibles entre sí. Otro ejemplo sería tomar una colección de jóvenes que quieren estudiar en la universidad, y una colección de universidades. Aquí nos interesaría saber cuándo una universidad es compatible con los gustos y aptitudes de un joven.

Este tipo de problemas nos llevan a un tipo de gráficas especiales: las gráficas bipartitas. En estas gráficas hay dos «tipos» distintos de vértices. Los vértices de un mismo tipo nunca tienen arista entre ellos.

Gráficas bipartitas#

La definición que refleja lo que planteamos en la introducción es la siguiente.

Definición. Una gráfica $G$ es bipartita si se puede dar una partición de su conjunto de vértices $V$ en dos conjuntos $A$ y $B$ tales que las aristas de $G$ únicamente conectan vértices de $A$ con vértices de $B$. En otras palabras, no existen aristas entre elementos de $A$, ni entre elementos de $B$.

Ejemplo. Consideremos la siguiente gráfica.

Esta es una gráfica bipartita. Demos una partición de sus vértices para mostrar esto. Para ello, pintaremos algunos de rojo y otros de azul. Lo que tenemos que lograr es que no haya aristas entre dos vértices rojos, ni aristas entre dos vértices azules. Una forma de hacer esto es la siguiente:

$\square$

Ejemplo. La siguiente gráfica es parecida a la anterior, sin embargo no es bipartita.

Para convencernos de que no lo es, podemos comenzar pintando algún vértice de rojo (por ejemplo, el de la esquina superior izquierda). Sus vecinos deben de ser azules. Los vecinos de sus vecinos rojos, y así sucesivamente. Sin importar dónde empecemos, siempre los colores están forzados y llegaremos a un problema, como en la siguiente figura, en donde el vértice gris ya no puede ser ni rojo ni azul.

$\square$

Caracterización de gráficas bipartitas#

En el segundo ejemplo de la sección anterior hay una forma sencilla de convencernos de que no será posible dar una partición de los vértices que muestre que la gráfica es bipartita. Consideremos los vértices marcados en negro en la siguiente figura:

Estos vértices forman un ciclo de tamaño $7$. Si la gráfica fuera bipartita, podríamos colorear estos vértices de rojo y azul sin tener aristas entre vértices del mismo color. Pero esto es imposible: sobre el ciclo se tienen que alternar los colores y el ciclo tiene una cantidad impar de vértices, así que al final hay un conflicto.

Este es el único tipo de problemas que pueden aparecer cuando estamos intentando ver si una gráfica es bipartita o no. Formalizamos esto mediante el siguiente resultado.

Proposición. Sea $G$ una gráfica con $n\geq 2$ vértices. La gráfica $G$ es bipartita si y sólo si no hay dentro de ella ciclos de longitud impar.

Demostración. Si $G$ tiene un ciclo de longitud impar, digamos $v_1,v_2,\ldots,v_{2k+1}$, entonces es imposible que sea bipartita pues de serlo los vértices de dicho ciclo deberían estar en conjuntos diferentes de la partición de manera alternada. Pero entonces $v_1$ y $v_{2k+1}$ quedarían en el mismo conjunto y la arista $v_1v_{2k+1}$ nos daría una contradicción.

Supongamos ahora que $G$ no tiene ciclos de longitud impar. Veremos que la gráfica es bipartita. Primero nos enfocaremos en cada una de las compontentes conexas de $G$.

Tomemos una componente conexa $H$ de $G$. Esta componente tampoco tiene ciclos de longitud impar. Tomemos un vértice $v$ de $H$ y consideremos los siguientes conjuntos:

\[\begin{align*} A_H&=\text{vértices a distancia par de $v$}\\ B_H&=\text{vértices a distancia impar de $v$}. \end{align*}\]

Como $H$ es compontente conexa, la distancia de cada vértice de $H$ a $v$ está bien definida y siempre es o par, o impar (pero no ambas). De esta manera, $A_H$ y $B_H$ tienen en conjunto a todos los vértices de $H$ y además

\[A\cap B = \emptyset.\]

Afirmamos que además no hay aristas entre los vértices de $A_H$, ni entre los vértices de $B_H$.

Si hubiera, por ejemplo, una arista entre vértices $w$ y $z$ de $A_H$, tendríamos un camino $C_1$ de longiud par de $v$ a $w$, luego la arista $wz$ y luego un camino $C_2$ de longitud par de $z$ a $v$. Al concatenar estos caminos, tendríamos un camino cerrado de longitud impar de $v$ a sí mismo.

Se puede mostrar (tarea moral) que la existencia de un camino cerrado de longitud impar implica la existencia de un ciclo de longitud impar y esto daría una contradicción. De manera análoga, se ve que no hay aristas entre vértices de $B_H$.

Consideremos ahora todos los conjuntos $A_H$ y $B_H$ (variando la componente conexa $H$) para construir los siguientes conjuntos:

\[\begin{align*} A&=\bigcup_{\text{$H$ c.c. de $G$}} A_H\\ B&=\bigcup_{\text{$H$ c.c. de $G$}} B_H. \end{align*}\]

Todos los vértices de $G$ están en alguna compontente conexa (y sólo una) y por lo tanto en algún $A_H$ ó $B_H$ (y sólo uno). De este modo, $A\cup B$ tiene todos los vértices de $G$ y $A\cap B=\emptyset$.

Lo único que nos falta para ver que $A$ y $B$ son una partición es verificar que no son vacíos. Claramente $A$ no es vacío pues $G$ tiene al menos una componente conexa.

Si alguna componente conexa tiene al menos dos vértices, entonces algún $B_H$ es no vacío y por lo tanto $B$ también sería no vacío.

Así, la única forma en la que todos los $B_H$ sean vacíos es si todas las componentes conexas de $G$ son vértices aislados. En ese caso, como tenemos por lo menos dos vértices $u$ y $v$, hacemos una excepción y declaramos que uno de ellos esté en $A$, el otro en $B$ y los demás en cualquiera de los queramos.

$\square$

Si una gráfica es bipartita, usualmente la representamos en dos columnas, una por cada conjunto de su partición de vértices. Así, queda algo como en el siguiente dibujo:

Tenemos una versión particular del «lema de los saludos de Euler» para el caso en el que una gráfica sea bipartita.

Proposición. Sea $G$ una gráfica bipartita con $m$ aristas y partición de vértices $A$ y $B$. Se tiene que:

\[\sum_{v\in A} \text{deg}(v)=m=\sum_{v\in B} \text{deg}(v).\]

Por ejemplo, en la gráfica de arriba los grados de $A$ son $3, 3, 3, 2, 2$ y los de $B$ son $2, 4,3,1,2$ y en ambos casos su suma es $13$.

Demostración. La clave es la igualdad con el número de aristas. Cada arista usa exactamente un vértice de $A$. Así, $\sum_{v\in A} \text{deg}(v)$ debe ser $m$. Análogamente $\sum_{v\in B}\text{deg}(v)$ también debe ser $m$.

$\square$

Emparejamientos#

En una gráfica bipartita podemos tomar algunas aristas que no repitan vértices y pensar que «emparejan» vértices del lado izquierdo con vértices del lado derecho. Aunque esta noción nos interesará principalmente en el caso de gráficas bipartitas, de cualquier manera damos a continuación una definición que se extiende a cualquier gráfica.

Definición. Un emparejamiento en una gráfica $G$ es un subconjunto de sus aristas de modo que no haya dos de ellas que compartan vértices.

Ejemplo. En la siguiente figura se muestra una gráfica $G$. Las aristas marcadas en azul en la siguiente figura conforman un emparejamiento de $G$, pues estas aristas no comparten vértices.

$\square$

De entre los emparejamientos de una gráfica, usualmente nos interesa encontrar aquellos que tengan la mayor cantidad de aristas posibles.

Definición. Un emparejamiento de una gráfica es maximal si no hay ninguna forma de extenderlo de modo que siga siendo emparejamiento. Es decir, es un emparejamiento que no es subconjunto propio de otro emparejamiento.

Definición. Un emparejamiento de una gráfica es máximo si tiene la mayor cantidad de aristas de entre todos los emparejamientos posibles en la gráfica.

Definición. Sea $G$ una gráfica. A la cantidad de aristas en un emparejamiento máximo le llamamos el número de emparejamiento de $G$, y lo denotamos por $\nu(G)$.

Si un emparejamiento es máximo, en particular no puede ser subconjunto propio de otro emparejamiento. De este modo, los emparejamientos máximos son maximales. Pero el converso no es cierto.

Ejemplo. El emparejamiento del ejemplo de arriba no es maximal pues comenzando con él todavía podemos añadir aristas. Una forma de hacerlo es la siguiente:

Este emparejamiento es maximal. Puedes verificar que es imposible agregar cualquier otra arista de modo que sigamos teniendo aristas que no compartan vértice. Sin embargo, este emparejamiento no es máximo, pues hay emparejamientos con más aristas, por ejemplo, el siguiente:

Aquí tenemos $5$ aristas. Una vez más, este emparejamiento es maximal, pues es imposible agregar más aristas. ¿Será un emparejamiento máximo? Necesitamos un argumento contundente para asegurar que ninguna otra forma de elegir aristas disjuntas nos da $6$ aristas o más.

Un argumento que funciona en este ejemplo particular es el siguiente: si tuviéramos $6$ aristas disjuntas, necesitaríamos al menos $12$ vértices. Pero la gráfica sólo tiene $11$ vértices. Así, no hay emparejamientos con $6$ o más aristas.

Este argumento muestra que el emparejamiento de arriba, además de ser maximal, también es máximo. Concluimos entonces que $\nu(G)=6$. $\square$

Las nociones de arriba nos ayudan a saber cuáles son los emparejamientos «grandes» en distintos sentidos. Otra forma de caracterizar a los emparejamientos es mediante los vértices a los que llegan.

Definición. Sea $G$ una gráfica y $X$ un subconjunto de sus vértices. Un emparejamiento cubre a $X$ o satura a $X$ si sus aristas pasan por todos los vértices de $X$.

Ejemplo. En la siguiente figura el emparejamiento de aristas azules cubre al subconjunto de vértices azules.

$\square$

Lo «mejor» que nos puede pasar en términos de emparejamientos es que pasen por todos los vértices de la gráfica. Por esta razón, le damos un nombre especial a éstos.

Definición. Sea $G$ una gráfica. Un emparejamiento perfecto de $G$ es un emparejamiento que cubre a todos sus vértices.

Ejemplo. El emparejamiento de arriba no es perfecto, pues hay vértices que no son cubiertos por él. De hecho, es imposible que haya un emparejamiento perfecto en esta gráfica pues tiene una cantidad impar de vértices.

Sin embargo, a continuación mostramos una gráfica que sí tiene un emparejamiento perfecto.

$\square$

Tarea moral#

Los siguientes problemas te ayudarán a practicar lo visto en esta entrada. Para resolverlos, necesitarás usar herramientas matemáticas, computacionales o ambas.

Considera el conjunto $A$ de números del $1$ al $10$ y el conjunto $B$ de las letras del alfabeto. Toma a $A\cup B$ como el conjunto de vértices de una gráfica en donde habrá una arista del número $n$ a cierta letra si la letra forma parte del nombre del número (por ejemplo $9$ se conectaría con $n$, $u$, $e$, $v$). Esto es una gráfica bipartita. ¿Cuántas aristas tiene? ¿Cuál es el vértice de $A$ con mayor grado? ¿Y el vértice de $B$ con mayor grado?
Demuestra que si en una gráfica $G$ hay un camino cerrado de longitud impar, entonces hay un ciclo de longitud impar.
Encuentra un emparejamiento con la mayor cantidad de aristas posibles en la gráfica del primer problema.
Considera la gráfica ejemplo de la sección «Emparejamientos»
- Encuentra todos sus emparejamientos máximos.
- Encuentra todos sus emparejamientos maximales.
- Encuentra todos sus emparejamientos con cuatro aristas.
Sea $n$ un entero positivo. Encuentra para cada $k$ con $1\leq k \leq n$ un árbol $G$ con $2n$ vértices y tal que $\nu(G)=k$.