Conjuntos independientes y coloraciones de vértices#
Introducción#
Pensemos en el siguiente problema. Un zoológico se está mudando y quiere transportar a todos sus animales. No son tantos, solamente son \(10\). Sin embargo, la siguiente gráfica muestra que hay algunos animales incompatibles, es decir, hay una arista entre dos de ellos si no pueden ir en el mismo transporte. Por ejemplo, el animal \(A\) no puede transportarse simultáneamente con el animal \(F\).
De aquí hay varias cosas que podríamos preguntarnos. ¿Cuál será la máxima cantidad de animales que podemos transportar en un sólo transporte? ¿Cuál será la mínima cantidad de transportes que necesitamos para transportar a todos los animales? En ningún momento deben de transportarse dos animales incompatibles.
La primer pregunta nos llevará a continuación a la noción de conjuntos independientes e independientes maximales. La segunda nos llevará un poco más abajo a la noción de coloraciones propias de vértices y a la de número cromático de una gráfica.
Conjuntos independientes#
Comencemos definiendo algunos conceptos que nos permitirán plantear y responder preguntas como la del máximo número de animales que se pueden transportar en nuetro ejemplo ficticio. Lo que estamos buscando es un conjunto de animales sin incompatibilidades. En la gráfica esto queda plasmado en la siguiente definición.
Definición. Un conjunto de vértices de una gráfica \(G\) es independiente si no hay aristas entre ellos.
Uno de los problemas importantes a resolver para una gráfica es determinar cuál es el conjunto independiente con la mayor cantidad de vértices.
Definición. El número de independencia de una gráfica \(G\) es el tamaño de un conjunto independiente máximo. Se denota por \(\alpha(G)\).
Ejemplo. Considera la siguiente gráfica \(G\)
Los vértices en azul a continuación indicamos en azul son un conjunto independiente con dos elementos.
Sin embargo, no es un conjunto independiente máximo. Ni siquiera es maximal, pues podemos agregar el vértice rojo todavía tendríamos un conjunto independiente.
Por lo tanto, \(\alpha(G)\geq 3\). Aunque ya no podamos agregar más vértices a este conjunto, esto no quiere decir que sea un conjunto independiente máximo, sino simplemente que es maximal. A continuación mostramos un conjunto independiente máximo, con \(5\) vértices, de donde \(\alpha(G)\geq 5\).
Se puede verificar que no hay conjuntos independientes más grandes (justifícalo). Por lo tanto, \(\alpha(G)=5\). \(\square\)
Para algunos tipos de gráficas, el número de independencia es fácil de calcular. El siguiente problema resuelve totalmente el caso en el que la gráfica sea un ciclo.
Problema. ¿Cuál es el número de independencia de la gráfica \(C_n\) que es un ciclos con \(n\) vértices?
Solución. Conviene separar en casos de acuerdo a si \(n\) es par o impar. Haremos el caso par a continuación, mientras que el caso impar quedará en la sección de ejercicios.
Si \(n\) es par, podemos escribir \(n=2N\), con \(N\) un entero positivo. Veremos que \(\alpha(C_{2N})=N\). Podemos etiquetar a los vértices del ciclo \(1,2,3,\ldots,2N\), de manera que \(i\) es adyacente a \(i+1\) para \(i=1,\ldots,2N-1\), y \(2N\) es adyacente a \(1\). Un conjunto que claramente es independiente son los vértices impares, es decir, \(1,3,5,\ldots,2N-1\). Este conjunto tiene tamaño \(N\). No puede haber un conjunto independiente más grande pues podemos agrupar a los números en \(N\) parejas \(\{1,2\}\), \(\{3,4\}\), \(\ldots\), \(\{2N-1,2N\}\). Si tuviéramos \(N+1\) o más vértices, entonces por principio de las casillas, habría una pareja \(\{i,i+1\}\) con \(i\) e \(i+1\) en el conjunto independiente. Pero esto es imposible, pues estos dos vértices son adyacentes.
\(\square\)
Coloraciones#
Pasemos ahora al segundo problema en nuestro ejemplo de los animales que debemos transportar. Lo primero que podemos asignar a cada uno de los animales un transporte. La manera general en la que pensamos esto en gráficas es con la noción de «coloraciones». Puedes pensar que pintaremos a los vértices de nuestra gráfica de animales con ciertos colores, y que los animales cuyos vértices sean del mismo color irán en el mismo transporte.
Definición. Sea \(G\) una gráfica y \(V\) su conjunto de vértices. Una coloración con \(k\) colores (o bien una \(k\)-coloración) es una función \(f:V\to \{1,2,3,\ldots,k\}\).
La definición anterior no menciona ningún color en específico. Aquí estamos pensando que los colores son \(1,2,\ldots,k\). Sin embargo, cuando tenemos ejemplos sencillos con pocos vértices y colores, podemos hacer un dibujo en donde a cada vértice lo pintamos con su color correspondiente.
Ejemplo. A continuación se muestra una gráfica con una coloración con \(3\) colores.
\(\square\)
Si bien la noción de coloración nos ayuda a clasificar a los vértices en tipos, esto todavía no impone restricciones sobre cómo están relacionadas las aristas con los colores. En el caso de nuestro problema de transportes de animales, ¡todavía no hemos modelado las incompatibilidades! Para incoporar esta información, introducimos la siguiente definición.
Definición. Una coloración de una gráfica es propia si no hay aristas entre vértices del mismo color.
En otras palabras, debe sucedernos que para cada color, los vértices de ese color formen un conjunto independiente.
Ejemplo. La coloración del ejemplo anterior no es propia pues hay aristas entre vértices del mismo color (de hecho, hay varias, ¿cuáles?) Sin embargo, a continuación se muestra una \(3\)-coloración propia de esa misma gráfica:
\(\square\)
Por supuesto, una manera muy sencilla de conseguirse una coloración propia es pintando a cada vértice de un color distinto. Pero en las aplicaciones esto usualmente no es lo que queremos. En el ejemplo del zoológico esto nos llevaría a usar un transporte por cada uno de los animales, lo cual suena muy ineficiente. Así, en algunas aplicaciones nos interesa saber cuál es la minima cantidad de colores con la que es posible colorear una gráfica.
Definición. El número cromático de una gráfica \(G\) es el menor \(k\) tal que \(G\) tiene una \(k\)-coloración propia. Se denota \(\chi(G)\).
Ejemplo. Considera la gráfica \(G\) del ejemplo anterior. El dibujo muestra que tiene número cromático a lo más \(3\) por la coloración que exhibimos. No se puede \(\chi(G)\leq 2\) pues sería bipartita, pero esto es imposible pues tiene un ciclo de longitud impar (¿lo ves?). Por lo tanto, \(\chi(G)=3\). \(\square\)
Probemos un resultado interesante que acota el número cromático de una gráfica en términos del grado máximo.
Proposición. Sea \(G=(V,E)\) una gráfica y \(\Delta(G)\) su grado máximo, es decir, \(\Delta(G):=\max_{v\in V} \deg(v)\). Entonces \(\chi(G)\leq D+1\).
Demostración. Procedemos por inducción en el número de vértices de la gráfica. Si \(G\) tiene un vértice, entonces el grado máximo de \(G\) es \(0\) y el número cromático es \(1\) y entonces el resultado se cumple.
Supongamos que el resultado se vale para cualquier gráfica con \(n\) vértices y tomemos una gráfica con \(n+1\) vértices y grado máximo \(\Delta(G)\). Tomemos un vértice \(v\) cualquiera con el grado máximo, y lo quitamos para obtener una gráfica \(G^\ast\). Al quitar a \(v\) el grado de cualquier otro vértice permanece menor o igual, por lo que \(\Delta(G^\ast)\leq \Delta(G)\). Por hipótesis inductiva, \(G^\ast\) tiene una coloración propia con \(\Delta(G^\ast)+1\leq \Delta(G)+1\) colores.
Al regresar el vértice \(v\), debemos decidir su color. Pero \(\deg(v)\leq D\). De este modo, de entre sus vecinos se utilizan como mucho \(\Delta(G)\) colores. Así, como tenemos \(\Delta(G)+1\) colores disponibles, hay uno que podemos usar para colorear a \(v\) sin crear aristas monocromáticas. \(\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.
Regresando al problema de la introducción, ¿cuál es el mayor número de animales que pueden ir en un mismo transporte? ¿cuál es la menor cantidad de transportes que se necesitan para transportar a todos los animales?
Termina el caso impar del problema de determinar el número de independiencia de los ciclos.
Sea \(G\) cualquier gráfica, \(\alpha(G)\) su número de independencia y \(\chi(G)\) su número cromático.
Demuestra que \(\alpha(G)\chi(G)\geq |V(G)|\).
Encuenta alguna gráfica en donde \(\alpha(G)\chi(G)=|V(G)|\).
Encuentra alguna gráfica en donde \(\alpha(G)\chi(G)>|V(G)|\).
Se hace una gráfica tomando un vértice por cada cuadrado de un tablero de ajedrez, y colocando una arista cada vez que dos cuadrados están o bien en la misma fila, o bien en la misma columna. Encuentra el número cromático y el número de independencia de esta gráfica.
Arturo propone el siguiente procedimiento para encontrar el número de independencia de una gráfica \(G\): comienza con un vértice \(v_1\). Luego, elige un vértice \(v_2\) que no sea vecino de \(v_1\). Luego, elige un vértice \(v_3\) que no sea vecino de \(v_1\) ni de \(v_2\). Y así sucesivamente, hasta que elige un último vértice \(v_k\) y luego no puede elegir más vértices.
Demuestra que este procedimiento sí da un conjunto \(v_1,v_2,\ldots,v_k\) independiente.
Encuentra una gráfica en donde este procedimiento faller, es decir, en donde el conjunto \(v_1,v_2,\ldots,v_k\) no sea independiente maximal.