676

Cap´ıtulo 10. El mundo de los grafos

10.3.

Coloreado de grafos

Vamos a poner algo de color en el mundo de los grafos. El pintoresco, dir´ıamos que pict´ orico, lenguaje de los grafos y de los colores que presentaremos se mostrar´a bien u ´til y pr´ actico, pues permite, por ejemplo, dise˜ nar horarios eficientes o contar listas con restricciones. Advertimos cari˜ nosamente al lector de que debe tener la precauci´ on de escoger adecuadamente d´ onde y ante qui´en exhibe los conocimientos t´ecnicos avanzados que va a aprender en esta secci´on: al fin y a la postre, la plasmaci´ on de la abstracci´on matem´atica de este lenguaje lo llevar´ a a pintar en un papel rayas y puntos con l´ apices de colores, a mirarlos fijamente, a levantarse de la mesa, pensar peripat´eticamente, volverse a sentar y quiz´as, s´olo quiz´ as, escoger un color. . . Adem´as de un grafo G, dispondremos de una paleta de colores, esto es, un conjunto S = {a, b, . . . } a cuyos elementos nos referiremos como los colores. El uso de esta terminolog´ıa tiene su explicaci´ on, que veremos en un momento; pero lo que realmente utilicemos (sean realmente colores, letras u otros s´ımbolos) no ser´ a relevante, y, por supuesto, qu´e colores tampoco ser´a significativo. Una coloraci´ on de G con los colores de S consistir´ a en asignar a cada v´ertice de G un elemento de S, es decir, un color, de manera que los extremos de cada arista reciban colores distintos. No se trata de una coloraci´ on libre. Formalmente, una coloraci´ on de G con colores de S es una aplicaci´on γ : V (G) −→ S de forma que γ(v) = γ(w) si {v, w} ∈ A(G). El valor de γ(v) es el color que recibe el v´ertice v en la coloraci´ on. Coloraci´ on es la acci´on de colorear28 . Por ejemplo, si tenemos el grafo G que representamos m´as abajo, y disponemos de la paleta de colores S = {a, b, c, d, e, f }, la asignaci´ on de colores de la izquierda es una coloraci´ on, pero no lo es la de la derecha, pues hay una arista con el mismo color e en sus dos v´ertices. a

a

S´I

a

e

e

b

NO e

b

El concepto de coloraci´ on es invariante por isomorfismo. Es decir, si tenemos dos grafos isomorfos y una coloraci´ on del primero, tendremos una coloraci´ on del segundo con el siguiente (obvio) procedimiento: a cada v´ertice del segundo grafo le asignamos el color que lleva el v´ertice del primer grafo que le corresponde por el isomorfismo. El perspicaz lector habr´ a observado que, en realidad, deber´ıamos hablar de coloreado de v´ertices. Puesto que un grafo viene dado por v´ertices y aristas, nos preguntamos, en sinton´ıa con el perspicaz lector, por qu´e no colorear aristas. Se puede, claro, y la restricci´ on es que aristas que concurran en un v´ertice han de llevar colores distintos. No desarrollaremos esta cuesti´on en el texto en s´ı, aunque varios ejercicios (ejercicios 10.3.26–10.3.30) est´ an dedicados a este asunto. 28

Perd´ on por la insistencia y la pedanter´ıa.

(versi´ on preliminar 29 de octubre de 2009)

10.3. Coloreado de grafos La crom´atica terminolog´ıa que vamos a emplear en esta discusi´on tiene su origen en un problema cl´ asico, conocido como el problema de los cuatro colores. Acepte el lector que el dibujo de la derecha es un mapa de las distintos pa´ıses que conforman un cierto continente. Queremos colorear el mapa, es decir, asignar a cada pa´ıs (y tambi´en a la zona mar´ıtima) un color de manera que regiones que compartan frontera no lleven el mismo color (para que no se confundan).

677

mar oceana A B

C D

Traducimos la informaci´ on del mapa a un grafo: los v´ertices ser´an las distintas regiones y entre dos v´ertices habr´a una arista si los pa´ıses correspondientes tienen frontera en com´ un. V´ease, a la izquierda, el mar grafo correspondiente al mapa anterior. Podemos colorear el mapa C D (o, equivalentemente, el grafo) con cinco colores, desde luego, pero, como el lector comprobar´ a, tambi´en con cuatro (asigne por ejemplo, y como parece obligado, el color azul —marino, por supuesto— a la zona mar´ıtima, el rojo a las regiones A y D, el verde al territorio B y, finalmente, el marr´ on a C). A

B

Sorprendentemente, sea cual sea el mapa considerado, el grafo que se obtiene a partir de ´el con el procedimiento indicado anteriormente posee unas caracter´ısticas muy especiales: es lo que se llama un grafo plano. Y lo que afirma el teorema de los cuatro colores es, qu´e otra cosa pod´ıa decir, que todo grafo plano puede colorearse utilizando u ´nicamente cuatro colores. La afirmaci´ on en s´ı nos deja pasmados: ¿sea cual sea el grafo plano?; ¿y por qu´e todo mapa tiene asociado un grafo de los que hemos dado en llamar planos? Hay mucho que hablar sobre el asunto, sobre la propia historia del teorema, y sobre sus fascinantes conexiones. Todo esto lo haremos en el secci´on 10.5. Pero el lenguaje de las coloraciones de grafos no s´ olo sirve para colorear mapas (tarea, en todo caso, que pudiera no resultar del todo apasionante), sino que permite describir y abordar algunas cuestiones combinatorias a las que hicimos referencia en cap´ıtulos anteriores. A. El problema de la asignaci´ on de horarios Empezamos considerando una cuesti´ on, la confecci´ on de horarios, que llamar´ a la atenon en tareas organizativas. ci´on29 de todo aquel que se haya visto involucrado en alguna ocasi´ Lo ilustramos con un ejemplo. Ejemplo 10.3.1 El primer curso de licenciatura consta de nueve asignaturas, A1 , . . . , A9 . Hay alumnos que est´ an matriculados, simult´ aneamente, en las asignaturas A1 y A2 , A3 y as, todo alumno que se matricule en alguna de las asignaturas A4 , A5 y A6 y A7 y A8 . Adem´ nar un horario, A1 , . . . , A8 debe cursar, obligatoriamente, la asignatura A9 . Se trata de dise˜ utilizando el menor n´ umero de horas posible, que permita a todos los alumnos asistir a las clases de las asignaturas en las que est´e matriculado. Observemos que un horario v´ alido es una lista de nueve posiciones, en las que los s´ımbolos son las horas que tengamos a nuestra disposici´on, pero con restricciones sobre los s´ımbolos que podemos utilizar en ciertas posiciones. 29

O quiz´ as le haga revivir pesadillas.

(versi´ on preliminar 29 de octubre de 2009)

678

Cap´ıtulo 10. El mundo de los grafos

Por ejemplo, si la primera y segunda posiciones contienen las hoA1 A2 an llevar el mismo ras para las asignaturas A1 y A2 , entonces no podr´ A8 A3 s´ımbolo. La traducci´ on a nuestro lenguaje de grafos de la informaci´ on sobre asignaturas e incompatibilidades queda resumida en el grafo en A9 alido “aspas de molino” que dibujamos a la derecha. Ahora, un horario v´ A7 A4 no es sino una coloraci´ on del grafo (los colores ser´an las horas disponiA6 A5 bles). Desde luego, con nueve colores se puede colorear. Pero lo que nos interesa, justamente, es colorear con pocos colores para que el horario sea eficiente. El lector podr´ a construir, sin mucha dificultad, una coloraci´ on del grafo que utiliza exactamente tres colores, y cerciorarse de que no puede hacerlo con s´olo dos colores. ♣ B. Listas con restricciones La confecci´on de horarios del ejemplo anterior no es sino un caso particular de una cuesti´on m´ as general: la construcci´ on de listas con restricciones (sobre posiciones). El lenguaje de coloreado permite abordar de manera eficaz esta cuesti´on, que a´ un ten´ıamos pendiente (v´ease, por ejemplo, la discusi´ on de la subsecci´ on 2.2.1). Porque, al fin y al cabo, colorear con k colores un grafo G con v´ertices {v1 , . . . , vn } es lo mismo que formar listas con repetici´on permitida de longitud n con los s´ımbolos (colores) {a1 , . . . , ak }, de manera que si {vi , vj } ∈ A(G), los s´ımbolos que aparezcan en las posiciones i y j de la lista sean distintos. Por ejemplo, las 5-listas con las restricciones que simb´olicamente hemos representado en el dibujo m´ as a la izquierda se corresponden con las coloraciones del grafo de la derecha: 2 4

5

1 1

2

3

4

5

3

Colorear el grafo lineal Ln con, digamos, los colores {a, b, c} es lo mismo que formar listas con repetici´ on permitida de longitud n con los s´ımbolos {a, b, c} de manera que en posiciones consecutivas haya s´ımbolos distintos. Las listas sin repetici´on de longitud n formadas con k s´ımbolos (k ≥ n) se corresponden con las coloraciones del grafo completo Kn con k colores. C. Particiones en bloques Las coloraciones del grafo vac´ıo Nn con k colores son asignaciones de color sin restricci´on alguna. Un coloreado de Nn que use exactamente k colores equivale a repartir los elementos del conjunto {1, . . . , n} en k bloques no vac´ıos, para luego etiquetar cada bloque con un n´ umero de 1 a k. La siguiente generalizaci´ on ser´a u ´til en ciertos argumentos sobre coloreado: colorear un grafo G con v´ertices {1, . . . , n} con exactamente k colores dados (es decir, us´ andolos todos) es lo mismo que partir el conjunto {1, . . . , n} en k bloques no vac´ıos (cada bloque lleva los v´ertices que van con el mismo color), de manera que cada dos elementos (v´ertices) de un bloque no sean vecinos en G. A cada bloque le asignamos un color distinto, de entre los k disponibles. (versi´ on preliminar 29 de octubre de 2009)

10.3. Coloreado de grafos

10.3.1.

679

Coloreado eficiente: el n´ umero crom´ atico

Como el ejemplo 10.3.1 sobre la asignaci´on de horarios suger´ıa, nos interesan coloraciones con poco colores. . . y cuantos menos, mejor. El n´ umero o´ptimo de colores que se pueden utilizar es una caracter´ıstica muy importante asociada a un grafo. Definici´ on 10.3 El n´ umero crom´ atico de un grafo G, que denotaremos por χ(G), es el m´ınimo n´ umero de colores necesario para colorear G. El an´ alisis del ejemplo 10.3.1 nos dice que el n´ umero crom´atico del grafo all´ı dibujado (el de las aspas de molino) es 3, porque lo podemos colorear con 3 colores, pero no con 2. De manera que hacen falta y bastan tres horas para impartir esas asignaturas sin conflictos. Una primera observaci´ on es que el n´ umero crom´atico es invariante por isomorfismos. Es on es que, como ya hemos decir, si G y G son grafos isomorfos, entonces χ(G) = χ(G ). La raz´ comentado, el propio isomorfismo traslada coloraciones en G en coloraciones en G . El grafo que aparece a la derecha es protagonista en algunas de las discusiones matem´aticas de la pel´ıcula30 El indomable Will Hunting. Su n´ umero crom´atico es 3. Obs´ervese que con u ´nicamente dos colores no podr´ıamos pintar los v´ertices de cualquiera de los “tri´angulos”. Y el lector no encontrar´a dificultades para decorar los v´ertices con exactamente tres colores. ¿Qu´e podemos decir de χ(G) en un grafo G general? Lo primero, que si G tiene aristas, χ(G) est´a siempre comprendido entre 2 y el n´ umero de v´ertices del grafo: Por un lado, χ(G) ≤ |V (G)| para todo grafo G, porque una coloraci´ on que siempre es v´ alida (aunque, desde luego, poco efectiva) es asignar a cada v´ertice un color distinto. Por otro, si el grafo contiene al menos una arista, entonces necesitaremos dos colores como m´ınimo. Es decir, si |A(G)| ≥ 1, entonces χ(G) ≥ 2. (De hecho, χ(G) = 1 si y s´olo si G no tiene aristas —es decir, si G es un grafo vac´ıo—.) No gran cosa, desde luego, si por ejemplo estamos tratando un grafo con 1000 v´ertices. M´as adelante, v´eanse las proposiciones 10.18 y 10.19, obtendremos nuevas cotas para el n´ umero crom´atico en funci´ on de los grados de los v´ertices. on de los v´ertices de G sirve Obs´ervese que si G es un subgrafo de G, cualquier coloraci´   tambi´en como coloraci´on de los de G , porque en G hay, en principio, menos restricciones. As´ı que si podemos colorear los v´ertices de G con, digamos, 10 colores, este n´ umero de colores bastar´ a para colorear los v´ertices de G . Lo que supone que si un grafo G contiene a G como subgrafo, entonces χ(G) ≥ χ(G ), Esta observaci´ on sugiere un procedimiento para acotar (inferiormente) el valor de χ(G): buscar subgrafos en G cuyos n´ umeros crom´aticos se conozcan (o se sepan a su vez estimar). Lo que resultar´ a u ´til porque pronto obtendremos n´ umeros crom´aticos de grafos como los completos, los ciclos de orden impar, etc. 30

En Good Will Hunting, el t´ıtulo original de la pel´ıcula dirigida por Gus van Sant en 1997, un hu´erfano (interpretado por Matt Damon) con problemas psicol´ ogicos demuestra tener un talento natural para las Matem´ aticas, talento que es descubierto por un profesor del Massachusetts Institute of Technology, especialista en Combinatoria y Teor´ıa de grafos. Protagonizada tambi´en por Robin Williams, Ben Affleck y Minnie Driver (Damon y Affleck son los autores del gui´ on, ganador de un Oscar), es, ciertamente, una pel´ıcula recomendable.

(versi´ on preliminar 29 de octubre de 2009)

680

Cap´ıtulo 10. El mundo de los grafos

Otra observaci´ on u ´til a la hora de calcular n´ umeros crom´aticos es que podemos restringirnos al caso de los grafos conexos. La raz´on es que, como no hay aristas que conecten v´ertices de componentes conexas distintas, las coloraciones de las distintas componentes conexas de un grafo son independientes. M´ as concretamente, si G tiene k componentes conexas, G1 , G2 , . . . , Gk , cuyos n´ umeros crom´aticos son los n´ umeros χ(G1 ), χ(G2 ), . . . , χ(Gk ) respectivamente, entonces χ(G) = m´ax {χ(Gi )} 1≤i≤k

Comprobemos primero que χ(G) ≥ m´ax 1≤i≤k {χ(Gi )}: ¿cu´antos colores necesitaremos para colorear todo el grafo G? Al menos, tantos como necesitemos para colorear la componente conexa de mayor n´ umero crom´atico. En el otro sentido: supongamos que tenemos evaluado umero de colores podremos colorear la componente conexa m´ax 1≤i≤k {χ(Gi )}. Con este n´ m´as “dif´ıcil”. Pero tambi´en las otras, que necesitan menos colores. Algunas familias de grafos y sus n´ umeros crom´ aticos Vamos ahora a calcular los n´ umeros crom´aticos de las clases m´as habituales de grafos. La verificaci´ on de que un n´ umero de colores es n´ umero crom´atico siempre supone dos pasos. Primero, se comprueba que es posible colorear con ese n´ umero de colores, para despu´es argumentar que no se puede hacer con menos colores. El grafo vac´ıo con n v´ertices Nn es, como ya hemos comentado, bastante especial, pues se puede colorear con un u ´nico color: χ(Nn ) = 1. Y rec´ıprocamente: si un grafo se puede colorear con un s´olo color, entonces es un grafo vac´ıo. Pasemos a un caso m´as interesante, el grafo completo con n ≥ 1 v´ertices, Kn . Aqu´ı necesitamos tantos colores como v´ertices (porque, como est´an presentes todas las aristas posibles, cuando asignamos un color a un v´ertice ya no podemos utilizar este color de nuevo). As´ı que umero crom´atico de un grafo no puede ser mayor que el n´ umero de χ(Kn ) ≥ n. Pero el n´ v´ertices, as´ı que χ(Kn ) ≤ n. De donde deducimos, finalmente, que χ(Kn ) = n. Esto nos dice, de paso, que si un grafo G contiene a un Kn como subgrafo, entonces χ(G) ≥ n. En el grafo de Will Hunting, recordemos, la presencia de tri´ angulos (grafos completos K3 ) nos permit´ıa decidir que al menos tres colores eran necesarios. El caso del grafo lineal con n v´ertices Ln (n ≥ 2) es a a a b b b tambi´en muy sencillo: por un lado, se puede colorear con dos colores, como se muestra en la figura. Pero adem´as, como hay al menos una arista, χ(Ln ) ≥ 2. Por tanto, χ(Ln ) = 2 si n ≥ 2. Consideremos ahora el grafo circular Cn , con n ≥ 3. Resulta convea niente distinguir entre que n sea par o impar. Ilustremos el caso impar c con n = 5 (obs´ervese que el caso n = 3 ya lo hemos visto en los grafos b completos). Por un lado, podemos colorearlo con tres colores (v´ease el b a dibujo de la derecha). Y con dos colores no se puede, ¡simplemente porque la secuencia a − b − a − b − a no cuadra bien! (obs´ervese que empezamos y acabamos con a). Extienda el lector el argumento para deducir que χ(Cn ) = 3 si n es impar. (versi´ on preliminar 29 de octubre de 2009)

10.3. Coloreado de grafos

681

a b El caso par, m´ as sencillo, lo ilustraremos con el “cuadrado”, C4 . V´ease, en el dibujo de la derecha, una coloraci´ on con dos colores. Pea b ro como ´este es el valor m´ınimo que puede tener el n´ umero crom´atico alogo prueba que χ(Cn ) = 2 si n es par. (pues hay aristas), χ(C4 ) = 2. Un argumento an´ En el grafo bipartito completo Kr,s , con r, s ≥ 1, por haber aristas, χ(Kr,s ) ≥ 2. Pero asignar un color a los v´ertices “de la izquierda” y otro distinto a los “de la derecha” es una buena coloraci´ on, as´ı que χ(Kr,s ) ≤ 2. Por tanto, χ(Kr,s ) = 2. En realidad, cualquier grafo bipartito, aunque no sea completo, se puede colorear con s´olo dos colores (de hecho, esta propiedad caracteriza a los grafos bipartitos; v´eanse los ejercicios 10.3.2 y 10.3.3). Por ejemplo, el grafo del cubo Qn , para n ≥ 2, (que es bipartito, ´rboles recordemos la discusi´ on del final de la subsecci´ on 9.1.3), tiene χ(Qn ) = 2. Tambi´en los a y los bosques tienen n´ umero crom´atico 2, salvo el caso trivial del a´rbol con un u ´nico v´ertice. Pero, a diferencia de lo que parecen sugerir estos ejemplos sencillos, calcular el n´ umero crom´atico de un grafo arbitrario es una tarea extraordinariamente complicada (en t´erminos t´ecnicos, un problema NP-completo).

10.3.2.

Algoritmo austero de coloreado

Buscamos ya un procedimiento general que permita colorear un grafo G = (V, A) con |V | = n, dada una paleta de colores S. En principio, no limitaremos el n´ umero de colores que est´ an a nuestra disposici´ on, y adem´ as, para fijar el procedimiento, supondremos que la paleta est´a ordenada: S = (a, b, . . . ). El objetivo es que, en la medida de lo posible, el n´ umero de colores utilizado sea peque˜ no. El procedimiento, que llamaremos31 algoritmo austero, consta de los siguientes pasos: → Paso inicial de ordenaci´ on. Ordenamos los v´ertices del grafo (¡importante!, el resultado del algoritmo depender´ a de la ordenaci´ on elegida; veremos criterios para conseguir ordenaciones eficientes). Esto es, disponemos los v´ertices del grafo en una lista (v1 , v2 , . . . , vn ). Ahora asignaremos sucesivamente colores a los v´ertices siguiendo la ordenaci´ on elegida. → Pasos de asignaci´ on de colores Primer paso: a v1 le asignamos el primer color disponible, a. Segundo paso: ¿c´omo coloreamos v2 ? Si es vecino de v1 le asignamos el color b; si no lo es, le asignamos a. Tercer paso: para colorear v3 , comprobamos si es vecino de v1 ´o v2 ; y no podremos utilizar el color o colores que hayamos utilizado en los que sean vecinos suyos. k-´esimo paso: ya hemos coloreado los v´ertices (v1 , . . . , vk−1 ). De la paleta de colores obviamos los colores usados en los vecinos de vk que ya hayan sido coloreados; de los colores que quedan, elegimos para vk el primero disponible. 31

En la bibliograf´ıa anglosajona se denomina greedy algorithm, que se podr´ıa traducir por algoritmo voraz, acaparador, avaricioso. . . (en franc´es se usa glouton, que suponemos no necesita traducci´ on. Medite el lector sobre las diferencias culturales). El t´ermino elegido aqu´ı (austero) trata de captar la filosof´ıa del algoritmo, que supone elegir, en cada paso, la opci´ on m´ as econ´ omica, hasta conseguir la coloraci´ on completa.

(versi´ on preliminar 29 de octubre de 2009)

682

Cap´ıtulo 10. El mundo de los grafos

Para ver el algoritmo en acci´on, consideremos el grafo dibujado a la derecha, en el que ya hemos asignado un cierto orden a los v´ertices. En el primer paso, a v1 le asignamos el color a. Para colorear v2 no podemos utilizar el color a, pues es vecino de v1 (que ya ha sido previamente coloreado con a). As´ı que de la paleta tachamos a, ( a, b, c, d, . . . ) y nos quedamos con el color b. El v´ertice v3 s´olo tiene un vecino que ya haya sido coloreado, el v2 con b: (a, b, c, d, . . . ), y escogemos a.

v1

v2

v4

v3

v5

v6

v7

El procedimiento se repite con los dem´ as v´ertices. Para v4 hay disponibles ( a, b, c, d, . . . ), as´ı que escogemos c. Para v5 hay disponibles (a, b, c, d, . . . ), de manera que escogemos a. Para v6 hay a a disponibles ( a, b, c, d, . . . ), por lo que escogemos b. Llegados al v´ertice v7 , nos encontramos con ( a, b, c, d, . . . ), de forma que escogemos b. Exhibimos, a la izquierda de estas l´ıneas, la coloraci´ on obtenida. Observemos que el algoritmo austero ha producido una b b coloraci´on con tres colores, que es el m´ınimo posible, esto es, el n´ umero crom´atico, pues el grafo contiene ciclos de longitud impar. a

b

c

Nuestro “algoritmo austero” toma como datos de entrada un grafo G y una paleta de colores y produce una coloraci´ on de (los v´ertices de) G. Pero, ¿es realmente eficaz? ¿Permite, por ejemplo, colorear G con el m´ınimo n´ umero de colores posible, χ(G)? Resulta que s´ı. ¡Magn´ıfico!, exclamar´a el lector. Pero quiz´as perder´ a parte de este entusiasmo cuando analice el argumento que exhibimos a continuaci´ on. Supongamos que un grafo G tiene n´ umero crom´atico χ(G) = k. Esto es, que puede ser coloreado con exactamente k colores. En otras palabras, que sus v´ertices pueden dividirse en k bloques (los que van “de rojo”, los que van “de azul”, etc.) de manera que no haya aristas entre v´ertices que est´en en el mismo bloque. Ordene ahora el lector los v´ertices del grafo de la siguiente manera: primero, los del primer bloque (los “de rojo”), etiquetados del 1 hasta el n´ umero de v´ertices que haya en el bloque (dentro de ´el, da igual c´omo los ponga). Luego los del segundo, luego los del tercero, etc. Al aplicar el algoritmo austero a esta ordenaci´ on, comprobar´ a que se utilizan exactamente k colores. As´ı que una o´ptima ordenaci´on. . . haberla hayla, pero no hay manera de saber cu´ al es. Obs´ervese que, en el argumento anterior, la ordenaci´ on o´ptima viene dictada por una coloraci´on o´ptima, que es justo lo que pretendemos obtener con el algoritmo. Pura prestidigitaci´ on, el argumento. En realidad s´ı que hay un procedimiento para obtener la ordenaci´ on o´ptima (o una de ellas), que consiste en considerar cada una de las posibles y aplicar una y otra vez el algoritmo austero, hasta encontrar la fet´en. Pero si el grafo tiene n v´ertices, hay n! posibles ordenaciones y, a estas alturas, ya sabemos que. . . Pero no todo est´ a perdido. En muchas ocasiones, el algoritmo funciona “bastante” bien, sobre todo si ordenamos los v´ertices atendiendo a unos criterios razonables. Empecemos analizando un par de ejemplos que nos permitir´ an entender algo m´ as el funcionamiento de este algoritmo. (versi´ on preliminar 29 de octubre de 2009)

10.3. Coloreado de grafos

683

Ejemplo 10.3.2 Consideremos el grafo del cubo Q3 . Encontramos ordenaciones que utilizan: 1

a

4

−→

7 3

3 d

8

a

2 5

c

c

3 colores

c a

2

d

b b

−→

4

4 colores

b

a

5

c

6

8

1

b

7

6

b

c

Pero, con cierto cuidado, encontramos ordenaciones que utilizan 2 colores, el m´ınimo posible: 1

a

7 5

b

−→

4 3

a

a

6 8

b

b 2

b

♣

a

Ejemplo 10.3.3 Consideremos un grafo bipartito con 2n v´ertices en el que cada v´ertice de la izquierda est´ a unido a todos los de la derecha excepto al que se sit´ ua justo enfrente. A la derecha exhibimos dos posibles ordenaciones de los 1 2 1 v´ertices. Para la primera ordenaci´ on (impares para los 3 4 2 v´ertices de la izquierda, pares para los de la derecha), el 5 6 3 algoritmo austero utiliza n colores, como el lector puede comprobar sin esfuerzo. Para la segunda ordenaci´ on, sin embargo, el algoritmo s´olo emplea dos colores, que es el mejor resultado posible, pues el n´ umero crom´atico del 2n−1 2n n grafo es 2. Si tomamos n muy grande, nos hacemos una idea de lo “sensible” que es el resultado del algoritmo austero a la ordenaci´ on inicial.

n+1 n+2 n+3

2n

♣

En ambos ejemplos hemos encontrado ordenaciones “´optimas” (para las que el algoritmo austero emplea el m´ınimo n´ umero de colores posible, el n´ umero crom´atico). Pero adem´as, y esto es curioso, en el caso del cubo, la “peor” ordenaci´on posible emplea 4 colores (y 3 es el grado de los v´ertices), mientras que para el bipartito el peor caso utiliza n colores (y todos los v´ertices son de grado n − 1). Vale la pena analizar si ´este es un comportamiento general, pero antes convenz´amonos de que lo dicho sobre el grafo del cubo es realmente cierto. Ejemplo 10.3.4 Mostremos que, para cualquier ordenaci´ on de los v´ertices del cubo, el algoritmo austero utiliza, a lo sumo, 4 colores. En el paso k-´esimo del algoritmo, para colorear vk estar´an prohibidos los colores usados en as, sean anteriores a vk (que sean del tipo los v´ertices que sean vecinos de vk y que, adem´ a (como mucho) tantos colores prohibidos como vj , con j < k). Por tanto, en cada paso habr´ el grado del v´ertice correspondiente. En el cubo, todos los v´ertices tienen grado 3, as´ı que a lo sumo tendremos 3 colores prohibidos en cada paso. Por tanto, con 4 bastar´ a para colorear mediante el algoritmo. ♣ (versi´ on preliminar 29 de octubre de 2009)

684

Cap´ıtulo 10. El mundo de los grafos

El argumento descrito en el ejemplo anterior se puede generalizar como se recoge en el siguiente resultado, cuya demostraci´ on dejamos como ejercicio al lector, y que nos proporciona, de paso, una cota superior para el n´ umero crom´atico de un grafo. Proposici´ on 10.18 Sea G un grafo y sea Δ(G) su m´ aximo grado (todos los v´ertices de G son de grado ≤ Δ(G)). Entonces el algoritmo austero utiliza a lo sumo Δ(G) + 1 colores. As´ı que χ(G) ≤ Δ(G) + 1 . Esta cota puede no ser muy buena: por ejemplo, en el grafo bipartito que analiz´ abamos antes, χ(G) = 2, mientras que Δ(G) = n. En ciertos casos, podemos mejorar un poco la estimaci´on: Proposici´ on 10.19 Si G es un grafo conexo con m´ aximo grado Δ(G), pero en el que existe al menos un v´ertice w con gr(w) < Δ(G), entonces χ(G) ≤ Δ(G) . vn−s−1

´ n. Supongamos que tenemos n v´ertices y Demostracio vn−1 digamos que w tiene grado s < Δ(G). Vamos a orde´ltimo nar los v´ertices de la siguiente manera: w ser´a el u v´ertice de la lista (w = vn ). Los s vecinos de w prevn−2 ceder´an a ´este en el orden establecido (vn−1 , . . . , vn−s ). vn−3 Despu´es, consideramos los vecinos de vn−1 que no hayan . . . . . . vn = w sido ya ordenados, luego los de vn−2 y as´ı sucesivamente. Como G es conexo, al final tendremos una ordenaci´on de todos los v´ertices. Apliquemos ahora el algoritmo austero: en cada paso estar´an prohibidos los colores vn−s usados en los vecinos anteriores. Pero todos los v´ertices (excepto w) tienen alg´ un vecino posterior, as´ı que #{vecinos anteriores} ≤ Δ(G) − 1, para todo v = w. Para w, es el grado el que es estrictamente menor que Δ(G). En total, en cada paso hay, a lo sumo, Δ(G) − 1 colores prohibidos.  Por tanto, con Δ(G) colores bastar´a para colorear32 . Reflexionemos un momento sobre el funcionamiento del algoritmo: en el paso k, el n´ umero de colores prohibidos es el n´ umero de colores utilizados en los v´ertices vecinos y anteriores: ' ( ' ( # {colores prohibidos para vk } ≤ m´ın # vecinos de vk , #anteriores = m´ın gr(vk ), k − 1 . Si pretendemos que el algoritmo austero utilice “pocos” colores, convendr´ a que esta cantidad, el n´ umero de colores prohibidos, se mantenga “peque˜ na” en cada paso. As´ı que interesar´ a colocar los v´ertices de mayor grado al principio (cuando el n´ umero de v´ertices anteriores es peque˜ no, de manera que se “neutralicen” los valores grandes de los grados) y al final los de menor grado, para compensar que el n´ umero de v´ertices anteriores es aqu´ı elevado (v´ease el ejercicio 10.3.8). Este criterio no es una panacea, e incluso en ocasiones no tiene aplicaci´on alguna (pensemos, por ejemplo, en un grafo regular como el del cubo, donde todos los v´ertices tienen el mismo grado). 32

En realidad, este resultado es m´ as general: el teorema de Brooks, del que no daremos demostraci´ on, afirma que si G es un grafo conexo, entonces χ(G) ≤ Δ(G). Excepto si el grafo es un grafo completo o un grafo circular con un n´ umero impar de v´ertices, para los que χ(G) = Δ(G) + 1.

(versi´ on preliminar 29 de octubre de 2009)

10.3. Coloreado de grafos

10.3.3.

685

Polinomio crom´ atico

No s´olo interesa saber si se puede colorear un grafo con k colores, sino tambi´en de cu´ antas formas se puede colorear. La primera cuesti´on queda resuelta en cuanto se conoce el n´ umero crom´atico, χ(G): si k ≥ χ(G) podremos colorear el grafo con k colores, y si k < χ(G), ser´a imposible colorear el grafo con k colores. Dedicamos esta subsecci´on a la segunda cuesti´ on. Aqu´ı, como queremos contar y calcular, conviene que los colores sean n´ umeros, y qu´e mejor que los n´ umeros de 1 a k. Dado un grafo G y para cada entero k ≥ 1, llamamos on {1, . . . , k}} , PG (k) = # {coloraciones distintas de G usando los colores de la colecci´ teniendo en cuenta que no es necesario usarlos todos. Desde luego, PG es una funci´ on de k, y veremos enseguida (en la subsecci´on 10.3.5) que resulta ser un polinomio en k, que llamaremos el polinomio crom´ atico de G:  αj kj . PG (k) = j

Los coeficientes (αj ), como asimismo veremos en la subsecci´on 10.3.5, contienen informaci´on importante sobre la estructura del grafo. Observemos, para empezar, que como un isomorfismo entre grafos traslada coloraciones de uno en coloraciones del otro, los polinomios crom´aticos deben coincidir: es decir, si G y G son dos grafos isomorfos, entonces PG (k) = PG (k), para cada entero k ≥ 1. Puesto que, como hemos indicado, podemos tratar listas con restricciones usando el lenguaje de grafos coloreados, el polinomio crom´ atico nos permitir´ a contar listas con restricciones. As´ı, si hemos formado un grafo G con n v´ertices y con aristas que codifican las umero de listas restricciones, PG (k) nos informa del n´ de longitud n con repetici´ on permitida con los s´ımbolos {1, . . . , k}; y tales que si {i, j} ∈ A(G), en las posiciones i y j de la lista usamos s´ımbolos distintos. El lenguaje de los polinomios crom´ aticos resulta ser una manera adecuada de organizar c´ alculos con el principio de inclusi´ on/exclusi´ on que hasta ahora emple´abamos para abordar esta cuesti´on. Supongamos, por ejemplo, que queremos ··· · · · n−1 n umero de n-listas con k s´ımbolos que cumplen las contar el n´ 1 2 3 4 1 restricciones que representamos simb´olicamente a la derecha n 2 (distintos s´ımbolos en las posiciones primera y segunda, en la n−1 3 segunda y tercera, etc., y as´ı hasta las dos u ´ltimas posiciones; 4 adem´as, la primera y u ´ltima posiciones deben llevar s´ımbolos distintos). Dibujamos tambi´en el grafo correspondiente, que ´ltima resulta ser un grafo circular Cn . Es la presencia de la restricci´on entre la primera y la u posici´on la que no nos permite contar las listas directamente, utilizando la regla del producto. Podr´ıamos entonces aplicar el principio de inclusi´on/exclusi´ on, calculando los tama˜ nos de los conjuntos de n-listas en las que va el mismo s´ımbolo en las dos primeras, el mismo en la segunda y tercera, etc., adem´as de las intersecciones dos a dos, tres a tres, etc., para luego contabilizar estos n´ umeros de la manera habitual. (versi´ on preliminar 29 de octubre de 2009)

686

Cap´ıtulo 10. El mundo de los grafos

Pero, con ayuda del lenguaje y los algoritmos que vamos a presentar, descubriremos que atico de Cn la respuesta que buscamos, que no es otra que PCn (k), el valor del polinomio crom´ en k, viene dada por la siguiente sencilla f´ ormula (v´ease el ejemplo 10.3.13): PCn (k) = (k − 1)n + (−1)n (k − 1) . A. Polinomio crom´ atico y n´ umero crom´ atico El polinomio crom´ atico se pregunta cu´antas coloraciones, y el n´ umero crom´atico si hay alguna, as´ı que cu´ al es el n´ umero crom´atico debe de quedar recogido dentro del propio polinomio crom´ atico. En efecto, 1. con menos de χ(G) colores no podemos colorear el grafo, as´ı que PG (k) = 0 si k < χ(G); 2. pero con exactamente χ(G) colores se puede colorear el grafo de, al menos, una forma; por tanto, PG (χ(G)) ≥ 1. umero de coloraciones distintas con k 3. De un cierto grafo G ya conocemos PG (k), el n´ colores. Supongamos que ahora en nuestra paleta de colores disponemos de algunos antas coloraciones podremos formar con esos k colores? Lo m´as, digamos k > k. ¿Cu´ que es seguro es que las que ya ten´ıamos con k colores seguimos teni´endolas ahora; y seguramente algunas m´as. Por tanto, si k < k , entonces PG (k) ≤ PG (k ). Reuniendo las tres propiedades anteriores, deducimos que ) si k ≥ χ(G) =⇒ PG (k) ≥ 1 , si k < χ(G) =⇒ PG (k) = 0 . As´ı que si tuvi´eramos la expresi´on del polinomio crom´ atico, podr´ıamos obtener el valor del n´ umero crom´atico como el menor valor entero de k en el que PG (k) no se anula. B. Subgrafos y polinomios crom´ aticos Supongamos que H es un subgrafo abarcador de un grafo G; esto es, H tiene los mismos v´ertices que G y algunas de sus aristas (o quiz´ as todas). Disponemos, adem´as, de k colores. Toda coloraci´ on de G con esos k colores induce una coloraci´on de H, pues si dos v´ertices de H son vecinos en H, tambi´en lo son en G. De manera que, para cada k ≥ 1, PG (k) ≤ PH (k)

si H es subgrafo abarcador de G.

Pero, ¡atenci´ on!: la condici´ on de ser subgrafo abarcador es impresH cindible. Considere el lector los dos grafos G y H que aparecen a la G derecha (completos con tres y dos v´ertices, respectivamente). Desde luego, H es subgrafo (pero no abarcador) de G. Sus respectivos polinomios crom´ aticos son PG (k) = k(k − 1)(k − 2)

y

PH (k) = k(k − 1) .

As´ı que, si k es suficientemente grande, PG (k) > PH (k). Y es que, aunque sigue siendo cierto que toda coloraci´ on de G induce una en H, ahora puede haber muchas coloraciones de G que dan lugar a la misma en H. (versi´ on preliminar 29 de octubre de 2009)

10.3. Coloreado de grafos

687

N´otese que si un grafo G tiene n v´ertices, entonces G es subgrafo abarcador de un Kn . Adem´as, un Nn es subgrafo abarcador de G. Pronto comprobaremos (v´eanse los ejemplos 10.3.8 y 10.3.9) que los polinomios respectivos de un Kn y de un Nn son: PKn (k) = k(k − 1)(k − 2) · · · (k − n + 1) y

PNn (k) = kn .

De donde deducimos que, si G tiene n v´ertices, su polinomio crom´ atico cumple que k(k − 1)(k − 2) · · · (k − n + 1) ≤ PG (k) ≤ kn

para cualquier k ≥ 1.

C. Conexi´ on, “desconexi´ on” y polinomios crom´ aticos Como no hay aristas entre v´ertices de distintas componentes conexas, las coloraciones de las distintas componentes de un grafo son independientes. Esto permite obtener, como detallaremos a continuaci´ on, el polinomio crom´ atico de un grafo a partir de los polinomios crom´aticos de sus componentes. Asimismo comprobaremos que si un grafo se puede separar en dos subgrafos que tienen “escasa conexi´on” entre s´ı (un concepto que precisaremos), el polinomio crom´ atico del grafo se puede escribir en t´erminos de los de estos subgrafos. Para empezar, si G tiene dos componentes conexas, G1 y G2 . Como no hay aristas entre v´ertices de las componentes G1 y G2 , para construir las coloraciones de G basta construir las de G1 primero y luego las de G2 . Aplicando la regla del producto, tendremos que PG (k) = PG1 (k) · PG2 (k) . La extensi´on a varias componentes conexas es directa: si G tiene r componentes conexas, digamos G1 , . . . , Gr , PG (k) = PG1 (k) · · · PGr (k) ¿Y qu´e ocurre si dos grafos comparten ·H u ´nicamente un v´ertice? Denotemos G♦ al grafo formado por dos grafos G y H que comparten s´olo un v´ertice v. Nos gustar´ıa escribir el valor del polinomio crom´atico del grafo G♦ · H en funci´ on de los polinomios de G y de H.

G♦ ·H v

G

H

¿C´ omo comparar?



-

La observaci´ on clave es la siguiente: consideremos un grafo F , un conjunto de colores {1, . . . , k} y un cierto v´ertice v del grafo. Entonces, # {coloraciones de F con {1, . . . , k} en las que v recibe el color 1} =

PF (k) . k

Obtendr´ıamos el mismo resultado, por supuesto, si cont´aramos las coloraciones en las que v recibe el color 2, o el 3, etc. Volvamos a la cuesti´on que describimos simb´olicamente en el dibujo de m´ as arriba. Suon pongamos que tenemos fijos los k colores, digamos {a1 , . . . , ak }. Podemos hacer una partici´ (versi´ on preliminar 29 de octubre de 2009)

688

Cap´ıtulo 10. El mundo de los grafos

de las coloraciones de uno de los grafos, por ejemplo H, en funci´ on del color que la coloraci´ on asigne al v´ertice v y escribir que +  +  Coloraciones de H Coloraciones de H con k colores =# + ··· # con k colores que asignan a1 a v  +  + Coloraciones de H con k colores Coloraciones de H con k colores + ··· + # +# que asignan ak−1 a v

que asignan ak a v

El n´ umero de la izquierda es PH (k); y todos los sumandos de la derecha tienen el mismo valor, PH (k)/k, como hemos indicado m´as arriba. Sea ahora una coloraci´ on de G, que asignar´ a un alidas para cierto color aj al v´ertice v. Queremos contar las coloraciones de H que son v´ colorear el grafo total; es decir, aqu´ellas que tambi´en asignan aj a v. Pero de ´esas hay PH (k)/k. Y esto ocurre sea cual sea aj , es decir, sea cual sea la coloraci´on de G de la que hayamos partido. As´ı que: PG (k) PH (k) PG♦ · H (k) = k A˜ nadamos algo m´ as de estructura com´ un, y supongamos que los dos grafos comparten u ´nicamente una arista v v v ¿C´ omo comparar? (y, por supuesto, los v´ertices que son  extremos de esa arista)? Es decir, conw w w - H formado por sideremos un grafo G♦ los grafos G y H que comparten exactamente una arista, por ejemplo, la arista (v, w), como el dibujo de la izquierda. -H G♦

G

H

La observaci´ on pertinente es ahora que si tenemos un grafo F , unos colores {1, . . . , k} y consideramos una arista (v, w) del grafo, entonces  + PF (k) coloraciones de F con {1, . . . , k} en las que v . # = recibe el color 1 y w recibe el color 2 k (k − 1) De nuevo, en lugar de 1 y 2, podr´ıamos haber elegido cualquier otro par de colores. Consideremos entonces una coloraci´ on cualquiera de H, que asignar´ a ciertos colores (¡distintos!) ai a v y aj a w. Queremos utilizar esta coloraci´on para construir la del grafo grande. un la pareja de Podemos hacer una partici´ on de las PG (k) posibles coloraciones de G seg´ colores que asignen a v y w; y de ellas, fijada la coloraci´ on de H descrita anteriormente, s´olo valdr´ an para colorear el grafo total aqu´ellas que asignen los colores ai y aj a los v´ertices v y w; es decir, una proporci´ on 1/k(k − 1). As´ı que PG♦ - H (k) =

PG (k) PH (k) k (k − 1)

Este argumento se puede generalizar, v´ease el ejercicio 10.3.20. Como ilustraci´on de estas t´ecnicas, veamos un par de ejemplos: (versi´ on preliminar 29 de octubre de 2009)

10.3. Coloreado de grafos

689

Ejemplo 10.3.5 Volvemos a la cuesti´ on del ejemplo 10.3.1. Ahora se trata de calcular cu´ antos horarios distintos se pueden confeccionar. Toda la informaci´ on sobre las asignaturas y las incompatibilidades se recog´ıa en el grafo “aspas de molino” que dibujamos a la derecha. Como el grafo consta de cuatro tri´ angulos que comparten entre s´ı un u ´nico v´ertice, aplicamos reiteradamente lo visto antes para llegar a que [k(k − 1)(k − 2)]4 = k(k − 1)4 (k − 2)4 . PG (k) = k3

A1

A2

A8

A3 A9

A7

A4 A6

A5

Aunque el c´ alculo se puede hacer tambi´en directamente: primero, hay k posibilidades para colorear el v´ertice central. Una vez coloreado ´este, hay (k − 1)(k − 2) posibilidades para colorear cada par de v´ertices que son extremos de un aspa. En total, k(k − 1)4 (k − 2)4 . ♣ Ejemplo 10.3.6 El polinomio crom´ atico del grafo de la pel´ıcula “El indomable Will Hunting”. En una escena de la pel´ıcula (v´ease la nota al pie de la p´ agina 679) se calculaba, en animada e ingenua recreaci´ on del proceso de descubrimiento matem´atico, el polinomio crom´atico del grafo que aparece a la derecha. Nosotros podemos resolverlo tambi´en, observando que son cuatro tri´ angulos que comparten tres aristas. Simulando la acci´ on de la pel´ıcula, llamemos G3 al grafo que contiene tres tri´ angulos (por ejemplo, el que se obtiene quitando el de la esangulos (quitamos los dos de las esquinas quina inferior izquierda), G2 el que tiene dos tri´ angulo, cuyo polinomio crom´ atico, ya lo sabemos, es inferiores) y, finalmente, G1 al del tri´ PG1 (k) = k(k − 1)(k − 2). Aplicando la regla anterior, obtenemos, sucesivamente, que PG (k) =

PG2 (k) [k(k − 1)(k − 2)]2 PG3 (k) [k(k − 1)(k − 2)] PG1 (k) [k(k − 1)(k − 2)]3 = = . k(k − 1) [k(k − 1)]2 [k(k − 1)]3

S´ olo queda tachar, con cierta teatralidad (y tal como suced´ıa en la pel´ıcula), los factores comunes arriba y abajo para deducir que PG (k) = k(k − 1)(k − 2)4 . Alternativamente, podemos organizar el c´alculo del polinomio crom´ atico coloreando primero el tri´ angulo interior, de k(k − 1)(k − 2) maneras, para luego observar que cada v´ertice exterior se puede colorear de k − 2 maneras, sea cual sea la coloraci´on usada en el tri´ angulo interior, dando as´ı un total de k(k − 1)(k − 2)4 posibles coloraciones del grafo en cuesti´on. ♣ D. Algunas clases de grafos y sus polinomios crom´ aticos Presentamos aqu´ı el c´alculo de los polinomios crom´ aticos de las familias habituales de grafos. En la subsecci´on 10.3.4 discutiremos algoritmos generales para el c´alculo de PG (k). Ejemplo 10.3.7 El polinomio crom´ atico del grafo lineal Ln . Consideremos, para empezar, el grafo lineal con tres v´ertices, L3 . Con 0 o con 1 color no umero de colores k genepodemos colorearlo, as´ı que PL3 (0) = 0 y PL3 (1) = 0. ¿Y para un n´ ral? Intentemos contar las coloraciones directamente. Tendremos k posibles colores para el (versi´ on preliminar 29 de octubre de 2009)

690

Cap´ıtulo 10. El mundo de los grafos

a prohiv´ertices v1 ; una vez coloreado, tendremos s´olo k − 1 disponibles para v2 , porque est´ bido utilizar el color que hayamos asignado al v´ertice v1 . Finalmente, para v3 tambi´en hay un color prohibido, el utilizado para v2 , as´ı que, utilizando la regla del producto, PL3 (k) = k(k − 1)(k − 1) = k(k − 1)2 . Un argumento an´ alogo nos permite concluir que, para el grafo lineal con n v´ertices, Ln , PLn (k) = k(k − 1)n−1 y que, por tanto, χ(Ln ) = 2, como ya sab´ıamos.

♣

Ejemplo 10.3.8 El polinomio crom´ atico del grafo completo Kn . Empecemos con el de tres v´ertices, K3 . No podemos colorearlo con 1 o´ 2 colores, as´ı que un color PK3 (1) = PK3 (2) = 0. Pero de nuevo podemos contar directamente: no hay ning´ prohibido para v1 , uno para v2 y dos para v3 , as´ı que PK3 (k) = k(k − 1)(k − 2) = k3 − 3k2 + 2k . Y en general, si tenemos un Kn , el resultado es que PKn (k) = k(k − 1)(k − 2) · · · (k − n + 1) que coincide, como debe ser, con el n´ umero de n-listas sin repetici´on que se pueden formar con k s´ımbolos. Como n es el primer entero en el que este polinomio no se anula, χ(Kn ) = n. Observe el lector que, en el polinomio crom´ atico de K3 , PK3 (k) = k3 − 3 k2 + 2 k, el grado del polinomio es el n´ umero de v´ertices y el coeficiente del segundo t´ermino es (cambiado de signo) el n´ umero de aristas. Interesante. M´as sobre esto, en la subsecci´on 10.3.5. ♣ Ejemplo 10.3.9 El polinomio crom´ atico del grafo vac´ıo Nn . No hay aristas, as´ı que no tenemos colores prohibidos para colorear los v´ertices, por lo que PNn (k) = kn Resultado ´este que ya hemos visto varias veces: son las n-listas con repetici´on permitida formadas con k s´ımbolos, o el n´ umero total de aplicaciones de un conjunto con n elementos en otro con k elementos (v´ease tambi´en el ejercicio 10.3.13). Por cierto, de la expresi´on del ♣ polinomio crom´ atico deducimos de nuevo que χ(Nn ) = 1. Ejemplo 10.3.10 Polinomios crom´ aticos de ´ arboles. Consideremos un a´rbol G con n v´ertices. Fijemos uno cualquiera de esos v´ertices como ra´ız, v´ease la subsecci´on 9.2. Desde la ra´ız, partimos los v´ertices en generaciones. Como podemos usar el mismo color en toda una generaci´ on, y como cada dos generaciones podemos repetir colores, podemos usar k colores para la ra´ız y k − 1 para cada uno de los v´ertices de la generaciones siguientes. Tenemos as´ı que PG (k) = k(k − 1)n−1

si G es un ´arbol con n v´ertices.

(versi´ on preliminar 29 de octubre de 2009)

10.3. Coloreado de grafos

691

Este ejemplo nos permite obtener una cota general para grafos conexos. Supongamos que G es un grafo conexo con n v´ertices. Sabemos ya (recu´erdese la discusi´on de la subsecci´on 9.2.2) que hay un subgrafo H que tiene los mismos v´ertices que G y que, adem´ as, es un ´arbol: un arbol abarcador de G. De la existencia de este subgrafo deducimos la siguiente cota ´ PG (k) ≤ PH (k) = k(k − 1)n−1 (comp´arese con la cota general PG (k) ≤ kn , que es v´alida para todo grafo con n v´ertices, conexo o no). ♣ Ejemplo 10.3.11 El polinomio crom´ atico del grafo circular Cn : comienzan las dificultades. No tanto para C3 , que coincide con K3 . Pero s´ı para C4 . Intentemos contar directamente el n´ umero de coloraciones, como hicimos en los otros ? ? v1 v2 ejemplos. El dibujo de la izquierda muestra el proceso, en el que vamos calculando las posibilidades a nuestra disposici´ on en los sucesivos v´ertiv4 v3 ces. Al llegar al u ´ltimo v´ertice nos encontramos 7 6 con una respuesta “depende”, que no permite k − 1 posibilidades ¡depende de c´ omo completar el argumento. Ya nos enfrentamos a hayamos coloreado v1 y v3 ! (un color prohibido) esta cuesti´on en el ejemplo 2.2.7, aunque all´ı nos ocupaba el lenguaje de las listas con prohibiciones. Resolvimos entonces la dificultad pasando al complementario y utilizando el principio de inclusi´ on/exclusi´ on en su forma general; o utilizando la regla de la suma (v´ease el comienzo de la secci´on 2.3). Esta idea, convenientemente desarrollada, nos da la clave para dise˜ nar el algoritmo que presentamos a continuaci´ on. ♣ k posibilidades

10.3.4.

k − 1 posibilidades (un color prohibido)

El algoritmo “come-aristas”

En la secci´ on 2.3 calcul´ abamos el n´ umero de 4−listas que no ten´ıan s´ımbolos consecutivos iguales y tales que el primer y u ´ltimo s´ımbolo tambi´en eran distintos. All´ı consider´ abamos33 dos casos: en uno, las posiciones primera y tercera llevaban el mismo s´ımbolo, y en el otro, s´ımbolos distintos. Y los interpret´ abamos, en un caso, como si una u ´nica posici´ on englobara a la primera y a la tercera, y en el otro, como si tuvi´eramos una restricci´on adicional. 1 2 1=3 2 1 2 En el lenguaje de los grafos, construir las citadas listas es lo mismo que colorear un gra= + fo C4 . Las listas en las que las posiciones 1 y 3 llevan el mismo s´ımbolo se obtendr´ıan 4 3 4 4 3 coloreando un grafo lineal con tres v´ertices, y las listas con s´ımbolos distintos en esas dos ponadimos una de las diagonales. El dibujo de la derecha debe siciones, coloreando un C4 al que a˜ entenderse como una manera simb´olica de expresar igualdades entre polinomios crom´ aticos. Significa que las coloraciones de C4 son aqu´ellas en las que 1 y 3 tienen el mismo color (y, por tanto, son coloraciones del primer grafo a la derecha del signo de igualdad), y aqu´ellas en las que 1 y 3 llevan distinto color (y, por tanto, son coloraciones del segundo grafo a la derecha del signo de igualdad). 33

Sutil invitaci´ on al lector a releer aquel material.

(versi´ on preliminar 29 de octubre de 2009)

692

Cap´ıtulo 10. El mundo de los grafos

Utilicemos la misma idea para la situaci´ on general. Sea un grafo G; nos fijamos en una arista suya, a ∈ A, que se˜ nalamos en el dibujo: v2

G

v4

v6 v5

v1

v3 v7

a v11

v8

v10 v9

Formamos ahora el grafo G \ {a} quitando esa arista: v2

G \ {a}

v4

v6 v5

v1

v3 v7

v11

v8

v10 v9

Por u ´ltimo, formamos el grafo Ga identificando los v´ertices unidos por la arista a. Si, como ocurre en el ejemplo entre v9 y el nuevo v´ertice v8 = v10 (recu´erdese que v8 y v10 estaban unidos a v9 en G), apareciera una arista doble, nos quedamos con una simple: v2

Ga

v4

v6 v5

v1

v3 v7

v11

v10 = v8 v9

Fijemos k colores y supongamos que tenemos calculados PG (k), PG\{a} (k) y PGa (k). Consideremos las posibles coloraciones de G \ {a} con esos k colores. Podemos hacer la partici´ on: : ) : ) : ) #

Coloraciones de G \ {a} con k colores

=#

Coloraciones de G \ {a} con k colores que llevan colores distintos en los extremos de a

+#

Coloraciones de G \ {a} con k colores que llevan el mismo color en los extremos de a

.

Observemos ahora que las coloraciones de G \ {a} que llevan colores distintos en los extremos de a son coloraciones v´alidas para G (en G tenemos una prohibici´ on m´ as, la que impone la arista a; pero una coloraci´ on de ´estas respeta esta prohibici´on). Y las coloraciones de G \ {a} que llevan el mismo color en los extremos de a son asimismo coloraciones v´alidas para Ga , donde los dos v´ertices son en realidad el mismo. As´ı que +  +  +  Coloraciones de G \ {a} Coloraciones de G Coloraciones de Ga . # =# +# con k colores con k colores con k colores Es decir, PG\{a} (k) = PG (k) + PGa (k) . O, como resulta conveniente escribir, PG (k) = PG\{a} (k) − PGa (k) (versi´ on preliminar 29 de octubre de 2009)

10.3. Coloreado de grafos

693

Lo que hace que esta identidad sea realmente u ´til (y que de hecho sea una regla de recurrencia as) para el c´ alculo de polinomios crom´ aticos) es que tanto Ga como G \ {a} tienen una (o m´ aristas menos que G. El proceso se puede repetir (para Ga y G \ {a}), a lo sumo tantas veces como aristas tiene G, hasta llegar a escribir PG (k) como suma (o resta) de polinomios crom´aticos de grafos vac´ıos con diversos n´ umeros de v´ertices (pues en cada paso eliminamos aristas y tambi´en v´ertices), que son conocidos. En la pr´actica no siempre tendremos que eliminar todas las aristas, porque por el camino obtendremos grafos cuyos polinomios crom´aticos conozcamos. Por ejemplo, en breve obtendremos el polinomio crom´ atico de los grafos circulares. Si ahora consideramos el grafo que aparece a la izquierda, y con la notaci´ on simb´ olica explicada antes para expresar igualdades entre polinomios crom´aticos, podemos optar por la siguiente aplicaci´on del algoritmo: ◦ ◦ ◦ ◦ ◦ K ◦ J ◦ −◦ ◦− ◦ ◦ ◦ ◦= ◦ = ◦ − ◦

◦

◦

◦

◦

◦

◦

◦

◦

◦

◦

as por esta otra: con lo que PG (k) = PC5 (k) − PL4 (k) + PL3 (k). O quiz´ ◦

◦ ◦= ◦

◦ ◦

◦

◦

◦

◦

J ◦= ◦

◦ −◦ ◦

◦

K ◦ −◦

◦−◦ ◦

◦

◦

◦

◦ ◦

◦

Como el polinomio crom´atico de un grafo con dos componentes conexas es el producto de los polinomios de cada una de ellas, concluimos que PG (k) = kPC4 (k) − 2PC4 (k). Aunque, en angulo y un cuadrado este caso, el camino m´as directo34 ser´ıa aprovechar que el grafo es un tri´ que comparten una arista: PC3 (k)PC4 (k) . PG (k) = k(k − 1) Ejemplo 10.3.12 Ahora podremos calcular el polinomio crom´ atico del grafo C4 . Los grafos que debemos considerar son v1

v2

e

C4 v4

v1

v2

C4 \ {e}

v3

v4

v1 v2 = v3

(C4 )e v3

v4

as´ı que, siguiendo los pasos del algoritmo, PC4 (k) = PL4 (k) − PC3 (k) = k(k − 1)3 − k(k − 1)(k − 2) = k(k − 1)(k2 − 3k + 3) . ♣ 34

Obs´ervese que el grafo de la figura est´ a “m´ as cerca” del grafo completo con cinco v´ertices que del grafo nulo con cinco v´ertices. As´ı que cabr´ıa preguntarse si no ser´ıa m´ as conveniente transformar nuestro algoritmo de manera que, en lugar de eliminar aristas, fu´eramos a˜ nadiendo. Medite el lector sobre la cuesti´ on y revise el ejercicio 10.3.21.

(versi´ on preliminar 29 de octubre de 2009)

694

Cap´ıtulo 10. El mundo de los grafos

Ejemplo 10.3.13 ¿Y para un Cn general? En el primer paso, como se muestra a la derecha, escribimos el polinomio crom´atico de Cn como el = − de Ln (que conocemos) menos el de Cn−1 . Pero a este u ´ltimo se le puede aplicar de nuevo el algoritn − 1 v´ertices n v´ertices mo, de manera que se podr´a escribir como el de un Ln−1 menos el de un Cn−2 . Repitiendo este proceso, obtenemos   PCn (k) = PLn (k) − PCn−1 (k) = PLn (k) − PLn−1 (k) − PCn−2 (k)   = PLn (k) − PLn−1 (k) + PLn−2 (k) − PCn−3 (k) = ··· =

n−3 

(−1)j+1 PLn−j (k) + (−1)n−3 PC3 (k) .

j=1

Conocemos los polinomios crom´aticos de los grafos lineales y del grafo C3 , as´ı que el problema queda resuelto. Aunque el resultado no tiene, desde luego, un aspecto muy agradable. Hay un truco, espec´ıfico para este ejemplo, que nos va a llevar a una expresi´on m´ as manejable. Se trata, ni m´ as ni menos. . . ¡que del famoso recurso de sumar y restar un 1!: PCn (k) = PLn (k) − PCn−1 (k) = k(k − 1)n−1 − PCn−1 (k) = (k − 1 + 1)(k − 1)n−1 − PCn−1 (k) = (k − 1)n + (k − 1)n−1 − PCn−1 (k) As´ı que PCn (k) − (k − 1)n = −[PCn−1 (k) − (k − 1)n−1 ] . La resoluci´ on de esta regla de recurrencia para el polinomio crom´ atico del grafo circular es bien sencilla, porque basta iterarla:     PCn (k) − (k − 1)n = − PCn−1 (k) − (k − 1)n−1 = (−1)2 PCn−2 (k) − (k − 1)n−2   = · · · = (−1)n−3 PC3 (k) − (k − 1)3 . El polinomio crom´ atico de C3 es conocido, PC3 (k) = k(k − 1)(k − 2), as´ı que   PCn (k) = (k − 1)n + (−1)n−3 k(k − 1)(k − 2) − (k − 1)3 = (k − 1)n + (−1)n (k − 1) Si n es par, el polinomio crom´atico no se anula en k = 2, y si n es impar, s´ı se anula en k = 2, ♣ pero no en k = 3. As´ı que, para n ≥ 1, χ(C2n ) = 2, mientras que χ(C2n+1 ) = 3. Finalicemos esta discusi´on sobre el algoritmo de c´alculo del polinomio crom´ atico se˜ nalando que, en general, y m´ as all´ a de estos ejemplos sencillos, ´esta es una cuesti´on muy complicada desde el punto de vista computacional. Obs´ervese que, en cada paso, el n´ umero de grafos que aparecen es el doble que en el paso anterior. Y, aunque son grafos cada vez m´ as “peque˜ nos”, se plantean grandes problemas de almacenamiento y manipulaci´ on de la informaci´ on que se va generando en cada etapa. A´ un as´ı, y sobre todo desde el punto de vista te´ orico, el polinomio crom´ atico es un importante objeto asociado a un grafo. Al estudio de algunas de sus propiedades dedicamos la siguiente subsecci´ on. (versi´ on preliminar 29 de octubre de 2009)

10.3. Coloreado de grafos

10.3.5.

695

Coeficientes del polinomio crom´ atico

Como grafos isomorfos tienen polinomios crom´aticos id´enticos, los coeficientes del polinomio crom´atico deben codificar informaci´ on intr´ınseca sobre la estructura del grafo. Conviene advertir que no tanta como para caracterizarlo, pues hay grafos no isomorfos con el mismo polinomio crom´ atico. Por ejemplo, como ya hemos visto anteriormente, todo ´arbol con n v´ertices tiene como polinomio crom´atico a k(k − 1)n−1 . El estudio sistem´atico que iniciamos ahora desvelar´ a parte de la informaci´ on que encierran los coeficientes. Pero, antes de proseguir, ya es hora de que justifiquemos que A. ¡El polinomio crom´ atico es un polinomio! umero de formas de colorear los Para comprobar que la funci´ on PG (k), que codifica el n´ v´ertices de G con k colores es realmente un polinomio en k, basta35 recordar el algoritmo come-aristas: al final del procedimiento, escribimos PG (k) como suma (o resta) de polinomios crom´aticos de grafos vac´ıos Nt , para varios valores de t. Es decir, como suma (o resta) de umero que da cuenta de las veces que aparece (con t´erminos del tipo At kt , donde At es el n´ signos + ´o −) cada grafo vac´ıo Nt en el resultado del algoritmo. Sin argumentos adicionales, hemos comprobado tambi´en que los coeficientes del polinomio crom´atico son siempre n´ umeros enteros. Una demostraci´ on m´ as formal procede por inducci´ on: supongamos que PG (k) es siempre un polinomio en k con coeficientes enteros para grafos G con |A(G)| ≤ m. Sea H un grafo cualquiera con m + 1 aristas. Si a es una arista de H, PH (k) = PH\{a} (k) − PHa (k) , donde H \{a} tiene m aristas y Ha tiene, a lo sumo, m aristas. Por inducci´on, los dos t´erminos de la derecha son polinomios en k con coeficientes enteros, as´ı que su resta tambi´en lo ser´a. Supongamos que G tiene n v´ertices. Obs´ervese que los grafos vac´ıos que se obtienen al aplicar el algoritmo come-aristas a G no pueden tener m´ as de n v´ertices (los que tiene el as a´ un, en el algoritmo propio G), as´ı que el grado de PG (k) no puede ser mayor que n. M´ aparece con seguridad un grafo vac´ıo con n v´ertices (y, en realidad, s´ olo uno). Medite el lector sobre la cuesti´on hasta convencerse de que el grado de PG (k) es exactamente n: PG (k) =

n 

αj kj ,

j=0

donde los n´ umeros αj son enteros. Nos interesa obtener los valores precisos de los coeficientes umero de v´ertices y aristas, n´ umero de (α0 , α1 , . . . , αn ) en t´erminos de las propiedades (n´ componentes conexas, etc.) de que goce el grafo en cuesti´on. B. Coeficientes de los t´ erminos de grado bajo Obs´ervese, para empezar, que no podemos colorear grafo alguno con 0 colores, as´ı que el a ser siempre nulo: coeficiente α0 (esto es, el t´ermino independiente) deber´ α0 = PG (0) = 0 35

para todo grafo G.

Quiz´ as el lector quiera reflexionar sobre el argumento alternativo que presentamos en el ejercicio 10.3.24.

(versi´ on preliminar 29 de octubre de 2009)

696

Cap´ıtulo 10. El mundo de los grafos

aticos de sus Si G tiene dos componentes conexas, PG ser´a el producto de los polinomios crom´ componentes, ninguno de los cuales tiene t´ermino independiente. As´ı que la menor potencia de k que puede aparecer en la expresi´ on de PG es k2 . Esto es, el coeficiente α1 del polinomio crom´atico PG (k) ser´a nulo. En general, si G1 , . . . , Gr (r ≥ 2) son las componentes conexas de un grafo G, entonces PG (k) = PG1 (k) · PG2 (k) · · · PGr (k) = αr    todos con t´ ermino independiente nulo

kr 

+αr+1 kr+1 + · · · ,

menor grado

y por tanto, no s´ olo α0 , sino tambi´en los siguientes coeficientes (α1 , . . . αr−1 ) son nulos. C. Suma de coeficientes Adem´as, si G no es un grafo vac´ıo, es decir, si tiene alguna arista, entonces no podemos colorearlo con un u ´nico color. Esto es, PG (1) = 0, lo que nos dice que la suma de los coeficientes de su polinomio crom´atico vale siempre 0: n 

αj = PG (1) = 0

si G no es un grafo vac´ıo.

j=1

D. Coeficientes de los t´ erminos de grado alto y alternancia de signos Como el lector concienzudo podr´ a comprobar, en todos los ejemplos que hemos analizado en p´ aginas anteriores se verifican la serie de propiedades que listamos a continuaci´ on: si el  grafo tiene n v´ertices y m aristas y escribimos su polinomio crom´atico de la forma j αj kj , entonces: (1) el coeficiente αn (el del t´ermino de mayor grado) es siempre 1; (2) el coeficiente αn−1 (el del t´ermino en kn−1 ) coincide con −m; (3) si G tiene r ≥ 1 componentes conexas, todos los coeficientes, desde αn hasta αr , son no nulos; (4) y estos coeficientes van alternando el signo: αn = 1, αn−1 = −m, luego αn−2 es positivo, αn−3 es negativo, etc. Para probar que estas propiedades se cumplen en un grafo general, vamos a combinar dos herramientas: por un lado, el algoritmo come-aristas, que nos dice que PG (k) = PG\{a} (k) − PGa (k) Si G tiene n v´ertices y m aristas, la tabla de la derecha recoge la informaci´ on que tenemos sobre los tres grafos en cuesti´on. Y la identidad anterior se puede reescribir, llamando βj y γj a los coeficientes de PG\{a} y PGa , como ()

n  j=1

j

αj k =

n  j=1

βj k − j

n−1 

grafo G G \ {a} Ga

γj kj .

j=1

(versi´ on preliminar 29 de octubre de 2009)

v´ertices n n n−1

aristas m m−1 ≤m−1

10.3. Coloreado de grafos

697

El otro ingrediente va a ser el m´etodo de n 1 ··· t 2 3 4 5 inducci´ on. Una inducci´ on peculiar, sobre la m suma n + m (n´ umero de v´ertices m´as n´ ume··· t 5 4 0 1 2 3 ro de aristas del grafo). Quiz´ as la tabla de ··· t 5 1 4 2 3 la derecha ayude a entender el procedimiento. La tabla va etiquetada por n, los posibles ··· t t+1 5 2 4 3 n´ umeros de v´ertices, y por m, los de aris··· t 5 3 4 ] tas. Los registros de la tabla son los valores otesis de inde n + m: Enunciaremos la hip´ aqu´ı, el grafo de inter´es ··· t 4 5 ducci´ on de la siguiente manera: la propiedad o t “tal” se cumple para todos los grafos para los que la suma del n´ umero de v´ertices y el t n´ umero de aristas sea ≤ t. Entonces, si partila hip´ otesis de inducci´ on, mos de un grafo G con n v´ertices y m aristas, t−1 t hasta la diagonal donde m+n = t+1, autom´ aticamente (v´ease la tabla) los grafos G \ {a} y Ga cumplir´ an la hip´ otesis en cuesti´on. Adem´ as, y para empezar, habr´ıa que comprobar el caso inicial36 n + m = 1, algo que el lector diligente habr´ a cumplimentado ya al terminar esta frase. Sin m´ as pre´ambulo (que ya ha sido bastante), nos ponemos a la faena: Propiedad 1 El coeficiente del t´ermino de mayor grado es siempre 1. S´ olo hay que reescribir () y utilizar la hip´ otesis de inducci´on (para G \ {a}, en este caso): PG (k) =

n  j=1

βj k − j

n−1  j=1

j

n

γj k = k +

n−1 

(βj − γj ) kj .

j=1

Propiedad 2 El siguiente coeficiente coincide con el n´ umero de aristas (cambiado de signo). Aprovechamos la propiedad 1 y la hip´ otesis de inducci´on (sobre G\{a}) para reescribir () de la siguiente manera: PG (k) =

n  j=1

βj kj −

n−1 

n−2 . /  γj kj = kn + − (m − 1) − 1 kn−1 + (βj − γj ) kj ,

j=1

j=1

de donde obtenemos que el coeficiente del t´ermino en kn−1 de PG (k) es, justamente, −m. Dejamos al lector que se ejercite comprobando la propiedad 3 (los coeficientes intermedios son todos no nulos) y terminamos demostrando la Propiedad 4 Los coeficientes alternan en signo, empezando con el de mayor grado, que es positivo (vale 1, de hecho). Supondremos que n es par (un argumento an´ alogo valdr´ıa para n impar, ¡compru´ebese!). 36

O quiz´ as los casos triviales en los que m = 0. Obs´ervese que, en la tabla de la p´ agina anterior, muchas casillas no se corresponden con situaciones en las que podemos tener grafos. Por ejemplo, con n = 1 v´ertices s´ olo podemos tener m = 0 aristas. En general, para n v´ertices s´ olo podremos tener un n´ umero de aristas entre  on del argumento. 0 y n2 . Acepte el lector la ligera imprecisi´

(versi´ on preliminar 29 de octubre de 2009)

698

Cap´ıtulo 10. El mundo de los grafos Por la hip´ otesis de inducci´on, podemos escribir PG\{a} y PGa de la siguiente manera: PG\{a} (k) =

n  (−1)j β;j kj

y

PGa (k) =

j=1

n−1 

(−1)j−1 γ ;j kj ,

j=1

;j son no negativos. Ahora reescribimos () a la luz de esta informaci´on: donde todos los β;j y γ PG (k) =

n 

βj k − j

j=1

n−1 

n n−1 n−1    j ; j j−1 j n γj k = (−1) βj k − (−1) γj k = k + ; (−1)j (β;j +; γj ) kj , j

j=1

j=1

j=1

j=1

que nos dice que los coeficientes de PG (k) van alternados de signo. E. Coeficientes del polinomio crom´ atico y principio de inclusi´ on/exclusion Ya disponemos de mucha informaci´ on sobre los coeficientes de un polinomio crom´atico. Pero, insaciables en nuestra sed de conocimiento, nos gustar´ıa saber, por ejemplo, cu´ anto vale el coeficiente αn−2 . Y aunque a estas alturas ya intuimos (a´ un m´ as, estar´ıamos dispuestos a a que ver con alguna caracter´ıstica intr´ınseca del grafo, asegurar) que el valor de αn−2 tendr´ los ejemplos vistos no nos permiten conjeturar cu´al ser´a ese valor, por lo que no podemos utilizar la maquinaria de prueba por inducci´ on que tan fruct´ıfera se ha mostrado hasta ahora. Para proseguir nuestro an´ alisis, recurrimos al principio de inclusi´ on/exclusi´ on, que subyace en todo lo relacionado con los polinomios crom´aticos. Recordemos que colorear con k colores un grafo G de n v´ertices y m aristas es lo mismo que formar n-listas con k s´ımbolos y con las restricciones (entre posiciones) que se˜ nalen las m aristas. Ya en este lenguaje de listas, llamando L al conjunto de las n-listas con k s´ımbolos, empezamos por definir los conjuntos A1 = {listas de L con el mismo s´ımbolo en las posiciones que indique la arista 1} , .. . Am = {listas de L con el mismo s´ımbolo en las posiciones que indique la arista m} . Pasando al complementario, PG (k) = # listas legales = |L| − |A1 ∪ A2 ∪ · · · ∪ Am |. El n´ umero total de listas |L| es, por supuesto, kn . Ahora, siguiendo el paradigma del principio de inclusi´ on/exclusi´ on, vamos a evaluar el tama˜ no de todas las posibles intersecciones. Para calcular |Ai |, para cada i, basta observar que dos posiciones llevan el mismo s´ımbolo; luego tenemos libertad para elegir los s´ımbolos de las restantes n − 2 posiciones. Por tanto, |Ai | = k · kn−2 = kn−1

para cada i = 1, . . . , m.

Vamos con las intersecciones dos a dos. Llamemos ai a la arista asociada al conjunto Ai y aj a la asociada a Aj . S´ olo hay dos configuraciones posibles: ◦

ai

◦

◦

aj

◦

Quedan n − 4 v´ ertices libres y hay que elegir dos colores para los dos pares de v´ertices a los que llegan ai y aj

→ |Ai ∩Aj | = kn−4 k2 = kn−2

(versi´ on preliminar 29 de octubre de 2009)

10.3. Coloreado de grafos

◦

ai aj ◦ ◦

699

Quedan n − 3 v´ ertices libres y hay que elegir un color para los tres v´ertices a los que llegan ai y aj

→ |Ai ∩ Aj | = kn−3 k = kn−2

En ambos casos obtenemos kn−2 ; por tanto, |Ai ∩ Aj | = kn−2 para todo i = j. Para las intersecciones 3 a 3 (que involucran 3 aristas) hay cinco configuraciones posibles: ai

◦

◦

◦

◦

aj

◦

◦

ai

◦

◦

ak

aj ak

◦

◦

aj

◦

ai

◦

◦

ak

aj

→ |Ai ∩ Aj ∩ Ak | = kn−6 k3 = kn−3

◦

Quedan n − 5 v´ ertices libres y hay que elegir dos colores para los dos conjuntos de v´ertices a los que llegan ai , aj y ak

→ |Ai ∩ Aj ∩ Ak | = kn−5 k2 = kn−3

◦

Quedan n − 4 v´ ertices libres y hay que elegir un color para los v´ertices a los que llegan ai , aj y ak

→ |Ai ∩ Aj ∩ Ak | = kn−4 k = kn−3

Quedan n − 4 v´ ertices libres y hay que elegir un color para los dos v´ertices a los que llegan ai , aj y ak

→ |Ai ∩ Aj ∩ Ak | = kn−4 k = kn−3

Quedan n − 3 v´ ertices libres y hay que elegir un color para los v´ertices a los que llegan ai , aj y ak

→ |Ai ∩ Aj ∩ Ak | = kn−3 k = kn−2

◦ ◦ ai ◦

Quedan n − 6 v´ ertices libres y hay que elegir tres colores para los tres pares de v´ertices a los que llegan ai , aj y ak

◦

ak

◦

aj

◦

ai ak

◦ La u ´ltima configuraci´ on es la que menos v´ertices involucra y, como vemos, es especial. El polinomio crom´ atico se escribe, con la informaci´ on de que disponemos hasta ahora como J K    n |Ai | − |Ai ∩ Aj | + |Ai ∩ Aj ∩ Ak | + · · · PG (k) = k − i

i =j

i =j =k

 

 1  + 2 m n−1 m n−2 m k − k + − #tri´angulos kn−3 + (# tri´angulos) kn−2 + · · · = kn − 1 2 3 1  2 m − # tri´angulos kn−2 + · · · = kn − m kn−1 + 2 Que los dos primeros coeficientes son 1 y −m ya lo sab´ıamos. Ahora descubrimos que el siguiente coeficiente es

 m − # tri´angulos. 2 Un resultado sugerente: de nuevo, una cantidad ligada a propiedades estructurales del grafo. Para concluir que esta afirmaci´ on es cierta, debemos comprobar que en el resto del polinomio crom´atico, “eso” que hemos representado con puntos suspensivos (y que se corresponde con configuraciones que involucran 4 o m´ as aristas), no aparecen m´ as t´erminos en kn−2 . La inducci´ on no parece ahora un buen camino, porque no tenemos informaci´ on sobre el n´ umero de tri´ angulos que tienen los grafos G\{a} y Ga , as´ı que debemos argumentar de otra manera. (versi´ on preliminar 29 de octubre de 2009)

700

Cap´ıtulo 10. El mundo de los grafos

Recordemos que intentamos calcular |A1 ∩ A2 ∩ · · · ∩ Al |, donde l ≥ 4. Cada conjunto de listas Aj est´a “asociado” una arista aj . El subgrafo H de G formado por las aristas a1 , . . . , al consta de un cierto n´ umero t de v´ertices y de un cierto n´ umero r de componentes conexas. Las listas que queremos contar se corresponden con “coloraciones” de G en las que los v´ertices de cada arista aj llevan el mismo color. As´ı que “coloreamos” primero H con esta peculiar receta, pintando los v´ertices de cada componente conexa con el mismo color (hay kr formas de hacerlo). Hecho esto, tenemos libertad para colorear los n − t v´ertices restantes de G. Y as´ı |A1 ∩ A2 ∩ · · · ∩ Al | = kn−t kr = kn−t+r . Si ahora comprob´ aramos que n − t + r ≤ n − 3, o, en otras palabras, que r ≤ t − 3, habr´ıamos concluido el argumento: los siguientes t´erminos del polinomio no podr´ıan contener potencias kn−2 . El siguiente resultado da fin a nuestras preocupaciones: Proposici´ on 10.20 Sea G un grafo con r componentes conexas, t v´ertices y l aristas. (a) Si G no tiene v´ertices aislados, entonces r ≤ t/2. (b) Si G no tiene v´ertices aislados y adem´ as l ≥ 4, entonces r ≤ t − 3. ´ n. La parte (a) es sencilla, pues cada componente conexa ha de tener, como Demostracio m´ınimo, dos v´ertices. Para la segunda parte, si t ≥ 6, se cumple que t/2 ≤ t − 3, y la parte (a) nos permite concluir el resultado; si t = 5, queremos comprobar que r ≤ 2. Pero es que si hubiera tres (o m´ as) componentes conexas, tendr´ıamos v´ertices aislados. Y si t = 4, s´olo puede suceder que r = 1, pues recordemos que al menos hay cuatro aristas.  E. Coda recurrente de asombro Paremos un momento. Recuperemos el resuello. Reflexionemos durante unos breves momentos: hemos creado un objeto abstracto, los grafos. Son objetos matem´aticos que aportan un lenguaje de representaci´on. Hemos ampliado el lenguaje introduciendo coloreados de v´ertices y nos hemos puesto a contar formas distintas de colorear. Las hemos codificado en otro objeto, que es un polinomio, y hemos estudiado sus coeficientes, que resulta que tienen propiedades tales como que siempre alternan en signo, o que el segundo coeficiente. . . El grado de sorpresa y asombro aumenta si nos dicen que, por ejemplo, el valor del polinomio crom´ atico en k = −1 tiene una interpretaci´ on combinatoria: (−1)|V (G)| PG (−1) 37 coincide con el n´ umero de orientaciones ac´ıclicas del grafo G. ¡En k = −1! ¿Pero k no era el n´ umero de colores con los que colore´ abamos?, ¿qu´e sentido tiene k = −1? 38 Pues todo eso, y bastante m´as , estaba en el objeto que hemos. . . ¿creado? ¿O estaba dentro, por s´ı s´olo, por su cuenta? ¿Subyac´ıa y lo hemos desvelado? ¿Lo hemos . . . descubierto? ¡Cuesta no ser plat´ onico cuando habitamos el mundo virtual de los objetos matem´ aticos! 37 Dado un grafo, podemos asignar un sentido a cada una de sus aristas (“orientarlo”), para convertirlo en un grafo dirigido. Estas orientaciones ser´ an ac´ıclicas si no contienen ciclos dirigidos. V´ease el ejercicio 10.3.25. 38 Como ciertas curiosas propiedades de los ceros de un polinomio crom´ atico. El matem´ atico americano George David Birkhoff (1884-1944) introdujo la noci´ on de polinomio crom´ atico en conexi´ on con el problema de coloreado los mapas, y precisamente con la esperanza de que el estudio anal´ıtico de los ceros de esta funci´ on arrojara luz sobre el problema de los cuatro colores.

(versi´ on preliminar 29 de octubre de 2009)

10.3. Coloreado de grafos

701

´ 10.3 EJERCICIOS DE LA SECCION 10.3.1 Compru´ebese que el grafo G del dibujo de la izquierda tiene n´ umero crom´ atico 4. Consid´erese tambi´en el grafo Rn , n ≥ 2, que llamaremos grafo rueda (dibujo de la derecha), que tiene n + 1 v´ertices. Compru´ebese que χ(Rn ) = 3 si n es par, mientras que χ(Rn ) = 4 si n es impar. G

Rn

10.3.2 Compru´ebese que χ(G) = 2 si y s´ olo si G es un grafo (no vac´ıo) bipartito. 10.3.3 Util´ıcese el algoritmo austero para comprobar que χ(G) = 2 si y s´ olo si G no contiene ciclos de orden impar. Ded´ uzcase que un grafo G es bipartito si y s´ olo si no tiene ciclos de orden impar. 10.3.4 Pru´ebese que si G es un grafo con n v´ertices y tal que todos sus v´ertices tienen grado k entonces n χ(G) ≥ . n−k 10.3.5 Pru´ebese que si G es un grafo, entonces a)

 χ(G) |A(G)| ≥ . 2

b)

1 χ(G) ≤ + 2

2|A(G)| +

1 . 4

10.3.6 Compru´ebese que el n´ umero m´ aximo de aristas que puede tener un grafo de n v´ertices y n´ umero crom´ atico 2 es n2 /4 si n es par, y (n − 1)(n + 1)/4 si n impar. 10.3.7 El grafo Mr se obtiene del ciclo C2r a˜ nadiendo aristas que unen pares de v´ertices opuestos. Es decir, si los v´ertices son {1, 2, . . . , 2r} entonces las aristas son {1, 2}, {2, 3}, . . . , {2r − 1, 2r}, {2r, 1} y {1, r + 1}, {2, r + 2}, . . . , {r, 2r}. Pru´ebese que (i) Mr es bipartido cuando r es impar. (ii) χ(Mr ) = 3 cuando r es par y r = 2. (iii) χ(M2 ) = 4. 10.3.8 Dado un grafo G, ordenemos los v´ertices {v1 , v2 , . . . , vn } de forma que si gi = grado(vi ) entonces g1 ≥ g2 ≥ · · · ≥ gn . Sea q = m´ax {m´ın{i, 1 + gi }}. 1≤i≤n

Pru´ebese que χ(G) ≤ q. Ded´ uzcase que si k es tal que k − 1 ≤ gk y k > gk+1 , entonces χ(G) ≤ k . ; su complementario (mismos v´ertices que G y sus aristas 10.3.9 Sea G = (V, A) un grafo y sea G unen los pares de v´ertices que no est´ an unidas en G). > ≥ n. (i) Pru´ebese que χ(G)χ(G) > ≤ n+1. (ii) Compru´ebese que χ(G) + χ(G)

(versi´ on preliminar 29 de octubre de 2009)

702

Cap´ıtulo 10. El mundo de los grafos

10.3.10 Dado un grafo G, una anticoloraci´ on de G es una asignaci´ on de color a los v´ertices de G de manera que v´ertices vecinos en el grafo reciben el mismo color. Compru´ebese que # {m´ aximo de colores distintos en una anticoloraci´ on} = #{componentes conexas de G} .

10.3.11 Calc´ ulense los n´ umeros y los polinomios crom´ aticos de los siguientes grafos: G1

G2

10.3.12 Sea G un grafo. Supongamos que en todo subgrafo H de G se cumple que δ(H) ≡ m´ın grH (v) ≤ K , v∈V (H)

(grH (v) quiere decir el grado de v como v´ertice de H). Compru´ebese que χ(G) ≤ K + 1. 10.3.13 Sea G = Nn el grafo vac´ıo con n v´ertices. Llamemos d(j) el n´ umero de formas de colorear Nn con j colores us´ andolos todos. Verif´ıquese que d(j) = j! S(n, j) y concl´ uyase que n

k =

n 

k(k − 1) . . . (k − j + 1) S(n, j) .

j=1

un resultado que ya hemos visto en varias ocasiones (rev´ısese el ejemplo 3.3.3). 10.3.14 (a) Pru´ebese que un grafo G con n v´ertices es un a ´rbol si y s´ olo si su polinomio crom´ atico n−1 es pG (k) = k (k − 1) . (b) Compru´ebese que si el grafo G de n v´ertices es un bosque formado por t componentes conexas (´ arboles), entonces su polinomio crom´ atico es PG (k) = k t (k − 1)n−t . ¿Es cierto el rec´ıproco? 10.3.15 Sea G un grafo con n v´ertices cuyo polinomio crom´ atico PG cumple que PG (0) = 0 y que (n−1) PG (0) = (1 − n)(n − 1)!. Demu´estrese que G es un a ´rbol. 10.3.16 H´ allese el polinomio crom´ atico del grafo bipartito completo Kr,s , donde r ≥ 1 y s ≥ 1. 10.3.17 Compru´ebese que el polinomio crom´ atico del grafo Q3 correspondiente al cubo tridimensional viene dado por PQ3 (k) = k 8 − 12 k 7 + 66 k 6 − 214 k 5 + 441 k 4 − 572 k 3 + 423 k 2 − 133 k . 10.3.18 Calc´ ulese el polinomio crom´ atico del grafo En =(Escalera)n , que tiene 2n+2 v´ertices y 3n+1 aristas: 1

2

3

n

10.3.19 Para cada par de n´ umeros naturales n, m, (n ≥ 2, m ≥ 2), construimos el grafo Gn,m que tiene n + m v´ertices {a1 , a2 , . . . , an } ∪ {b1 , b2 , . . . , bm } con las n + m − 2 aristas   j=m−1 {ai , ai+1 }i=n−1 ; {b , b } j j+1 j=1 i=1

(versi´ on preliminar 29 de octubre de 2009)

10.3. Coloreado de grafos

703

m´ as las 4 aristas siguientes {{a1 , b1 }, {a1 , b2 }, {a2 , b1 }, {a2 , b2 }}. Es decir, se trata de un grafo Ln y un grafo Lm que unimos mediante todas las aristas posibles entre sus respectivos dos primeros v´ertices. Se pide calcular el n´ umero crom´ atico y el polinomio crom´ atico de Gn,m . 10.3.20 Pru´ebese la siguiente generalizaci´ on de los resultados sobre grafos que son uni´ on de dos que comparten un v´ertice o una arista: si un grafo G est´ a compuesto por dos subgrafos H1 y H2 que comparten un grafo completo con n v´ertices, entonces PG (k) =

PH1 (k) PH2 (k) . PKn (k)

Los casos vistos anteriormente corresponden a n = 1 y n = 2. Compru´ebese que la conclusi´ on no es cierta, en general, si la intersecci´ on de los dos subgrafos no es un grafo completo. 10.3.21 En este ejercicio vamos a “reinterpretar” el algoritmo come-aristas. La construcci´ on b´ asica nos dec´ıa que PG\{a} (k) = PG (k) + PGa (k) , tras una adecuada reordenaci´ on de los t´erminos. Es decir, que si tenemos un cierto grafo que, en la notaci´ on de arriba, ser´ıa G\{a}, su polinomio crom´ atico se puede escribir como la suma del polinomio crom´ atico del grafo que obtenemos a˜ nadi´endole a G \ {a} una cierta arista a (por supuesto, una que no est´e en el grafo) m´ as el polinomio crom´ atico del grafo que resulta de identificar los v´ertices de a. En ocasiones, este nuevo punto de vista, que podemos bautizar como el “algoritmo a˜ nade-aristas”, puede ser m´ as eficaz que el “come-aristas”. Por ejemplo, cuando el grafo que estamos considerando est´e “m´ as cerca” de ser un grafo completo que uno vac´ıo. Apl´ıquese esta idea a la obtenci´ on del polinomio crom´ atico del grafo que aparece dibujado a la derecha. 10.3.22 ¿Cu´ antas listas distintas (con repetici´ on permitida) de longitud 7 se pueden formar con los cuatro s´ımbolos {a, b, c, d} de manera que en posiciones consecutivas aparezcan s´ımbolos distintos, y que adem´ as el s´ımbolo de la posici´ on central sea distinto del s´ımbolo en la posici´ on primera y del s´ımbolo en la posici´ on u ´ltima? 10.3.23 Compru´ebese, usando inducci´ on y el argumento empleando para comprobar la alternancia de signo de los coeficientes, que si un grafo G tiene n v´ertices y r componentes conexas, entonces todos los coeficientes desde el t´ermino independiente hasta el de grado r − 1 son cero, mientras que todos los coeficientes desde el de grado r hasta el de grado n son no nulos. v2 10.3.24 Un conjunto de v´ ertices independientes de un grafo G es un v3 subconjunto de V (G) cuyos elementos no tienen aristas entre s´ı. Por ejemplo, v1 S = {v1 , v3 , v5 } es un conjunto de v´ertices independientes del grafo que dibuv4 v jamos a la derecha, mientras que S  = {v1 , v2 , v3 } no lo es (pues, por ejemplo, v6 5 hay una arista entre v1 y v2 ). Sea G un grafo con n v´ertices, y llamemos fG (r) al n´ umero de formas distintas de partir los v´ertices de G en r conjuntos de v´ertices independientes. Obs´ervese que fG (r) = 0 si r > n y tambi´en que fG (0) = 0.

a) Podemos colorear los v´ertices del grafo G con k colores de la siguiente manera: primero partimos V (G) en r conjuntos independientes, y luego asignamos a cada bloque un color distinto. Compru´ebese que, dada una partici´ on en r bloques, tenemos k(k − 1) · · · (k − r + 1) maneras distintas de asignar colores a los v´ertices de cada bloque. Ded´ uzcase que PG (k) =

n 

fG (r) k(k − 1) · · · (k − r + 1) = fG (1) k + fG (2) k 2 + · · · + fG (n) k(k − 1) · · · (k − n + 1) .

r=1

(versi´ on preliminar 29 de octubre de 2009)

704

Cap´ıtulo 10. El mundo de los grafos

En particular, esto prueba que PG (k) es un polinomio en k, con coeficientes enteros y de grado n. N´ otese que los n´ umeros fG (r) son los coeficientes de PG (k) en la base de los factoriales decrecientes, que presentamos en la discusi´ on sobre el origen de los n´ umeros de Stirling de la subsecci´ on 3.3.2. uzcase que el coeficiente que acompa˜ na a k n en PG (k) es 1. b) Compru´ebese que fG (n) = 1 y ded´ c) Supongamos ahora que el grafo G tiene n v´ertices y m aristas. Compru´   ebese que fG (n − 1) coincide con el n´ umero de pares de v´ertices sin arista en com´ un, esto es, con n2 − m. d) Si el lector revisa la citada discusi´ on sobre n´ umeros de Stirling, descubrir´ a que el coeficiente umero de Stirling de primera de k n−1 en el desarrollo de k(k − 1) · · · (k − n + 1) coincide con el n´ especie s(n, n  1). An´ımese el lector a calcularlo, si no lo hizo en su momento, para obtener la − respuesta: − n2 . e) Det´ectense, en la expresi´ on de PG (k) escrita arriba, los factores en k n−1 y util´ıcense los dos apartados anteriores para comprobar que el coeficiente que acompa˜ na a k n−1 en PG (k) es −m. 10.3.25 Dado un grafo G, “orientarlo” consiste en crear a partir de ´el un grafo dirigido asignando sentido a sus aristas. Si G tiene m aristas, hay 2m orientaciones distintas. Una orientaci´ on es “ac´ıclica” si el grafo dirigido no contiene ciclos. Consid´erense los dos grafos que aparecen a la derecha. El G1 G2 primero, G1 , es un grafo circular con 4 v´ertices y 4 aristas. Tieas ne, pues, 24 = 16 orientaciones distintas. El grafo G2 , algo m´ complicado, tiene 26 = 64 orientaciones distintas, pues consta de 6 aristas. Compruebe el lector (a mano) que 22 de ellas contienen ciclos. Ahora obt´engase, en ambos casos, el n´ umero de orientaciones ac´ıclicas calculando los respectivos polinomios crom´ aticos y evalu´ andolos en k = −1. Los siguientes ejercicios est´an dedicados a las coloraciones de aristas. 10.3.26 Una coloraci´ on de las aristas de un grafo G es una asignaci´ on de colores a las aristas del grafo de forma que las aristas adyacentes (es decir, que comparten un v´ertice) llevan distinto color. umero crom´ atico de aristas, al menor n´ umero de colores necesario para Llamamos χ (G), el n´ colorear las aristas de un grafo. Compru´ebese que χ (G) ≥ Δ(G), donde, recordemos, Δ(G) es el mayor grado presente en los v´ertices del grafo39 . 10.3.27 Compru´ebese que, para los grafos circulares Cn y los completos Kn   Δ(Cn ) = 2 Δ(Kn ) = n − 1 si n par;   χ (Cn ) = χ (Kn ) = Δ(Cn ) + 1 = 3 si n impar; Δ(Kn ) + 1 = n

si n par; si n impar;

10.3.28 Compru´ebese que si G es un grafo k regular con un n´ umero impar de v´ertices, entonces χ (G) ≥ k + 1 (en lugar del obvio χ (G) ≥ k). 10.3.29 Compr´ uebese que si G tiene n v´ertices, m aristas, Δ(G) = k y se cumple que m > kn/2, entonces χ (G) = k + 1. 10.3.30 (a) Compru´ebese que el grafo de Petersen (v´ease el dibujo del ejercicio 10.1.7) no se puede colorear con tres colores (n´ otese que este grafo 3-regular tiene 10 v´ertices y 15 aristas, as´ı que no podemos aplicar directamente el ejercicio anterior). (b) Obs´ervese que si el grafo fuera hamiltoniano, entonces sus aristas se podr´ıan colorear con tres colores. Ded´ uzcase que el grafo de Petersen no es hamiltoniano. 39 Un resultado general, debido a Vizing, afirma que para un grafo G cualquiera, Δ(G) ≤ χ (G) ≤ Δ(G) + 1 . onig). Los grafos bipartitos, por ejemplo, tienen χ (G) = Δ(G) (es un resultado de K¨

(versi´ on preliminar 29 de octubre de 2009)