Capitulo 8b PDF

Preview

Summary

Download Capitulo 8b PDF

Description

Cap´ıtulo 8. Grafos

592

8.4.

Coloreando grafos

pr eli m in ar

Vamos ahora a introducir un ingrediente nuevo en este recorrido por la Teor´ıa de Grafos: vamos a “colorear” los v´ertices de un grafo, con unas ciertas reglas que veremos en un momento. El objetivo es abordar la cuesti´on de contar listas con restricciones (en particular, el problema de los horarios que plante´ abamos al principio del cap´ıtulo). Tenemos un grafo G y un conjunto de colores S = {a, b, . . . }. Una coloraci´ on de G con los colores de S consistir´a en asignar a los v´ertices de G elementos de S (“colores”) de manera que los extremos de cada arista reciban colores distintos. 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. Definici´ on 8.13 El n´ umero crom´ atico de un grafo G, χ(G), ser´ a el n´ umero m´ınimo de colores necesario para colorear G.

Ve rs i´o n

Un problema cl´asico en este contexto es el llamado problema de los cuatro colores. Esta cuesti´ on concreta es la que da lugar a la terminolog´ıa de los colores. Aunque la estudiaremos en detalle en el cap´ıtulo 15, vamos a presentarla aqu´ı de manera informal. Tenemos un mapa con un cierto n´ umero de pa´ıses y sus fronteras correspondientes, y queremos colorearlo de manera que pa´ıses vecinos reciban, para poder distinguirlos, colores distintos. Para analizar esta cuesti´on, usamos grafos para representar la informaci´ on relevante: los pa´ıses que aparecen y una relaci´on binaria, la de vecindad. El conjunto de pa´ıses ser´ a el de v´ertices, y dibujaremos una arista entre dos v´ertices si los pa´ıses que representan son vecinos. De esta manera obtenemos un grafo, y el problema de asignar colores a los pa´ıses se traduce en el de colorear el grafo. Hay que tener cierto cuidado con la construcci´ on del grafo: dos pa´ıses pueden tener m´ as de un trozo de frontera com´ un (Espa˜ na y Francia, por ejemplo, donde Andorra separa en dos la frontera pirenaica), as´ı que a veces tendremos que usar aristas m´ ultiples. O quiz´as a un pa´ıs le pueden corresponder varias regiones separadas (por ejemplo, unas islas); cada una de estas regiones deber´ıa entonces ser considerada como un pa´ıs distinto. En todo caso, y esto es lo importante, el grafo que se obtiene es muy especial: es lo que se llama un grafo plano (en el cap´ıtulo 15 lo definiremos con cuidado). El problema cl´ asico al que alud´ıamos es el de verificar que todo mapa puede ser coloreado con s´ olo cuatro colores; en otras palabras, que el n´ umero crom´atico del grafo (plano) obtenido a partir de un mapa de la forma descrita anteriormente es menor o igual que cuatro. Por ejemplo, en el mapa A B

A

B

C

D

cuyo grafo asociado ser´ıa C

D

es decir, un K4 , hacen falta cuatro colores. (versi´ on preliminar 24 de noviembre de 2003)

593

8.4. Coloreando grafos

Pero volvamos con nuestro problema general de coloraciones de grafos. Algunas observaciones inmediatas sobre el n´ umero crom´atico son las siguientes: Para todo grafo G, χ(G) ≤ |V | , porque siempre podremos colorear con |V | colores, ´ es, obviamente, la forma menos efectiva asignando a cada v´ertice un color distinto. Esta de colorear.

2.

Si el grafo contiene al menos una arista, necesitaremos dos colores como m´ınimo; es decir, si |A| ≥ 1, entonces χ(G) ≥ 2. Si G contiene a G′ como subgrafo, entonces

3.

pr eli m in ar

1.

χ(G) ≥ χ(G′ ) ,

4.

porque al menos necesitaremos χ(G′ ) colores para colorear el subgrafo (y quiz´ as m´as para el resto). Los ejemplos m´ as relevantes de subgrafos que habremos de buscar dentro de un grafo para obtener informaci´ on sobre su n´ umero crom´atico son los completos y los ciclos de orden impar, cuyos n´ umeros crom´aticos obtendremos pronto (en el ejemplo 8.4.1). Si G tiene k componentes conexas, G1 , G 2 , . . . , G k que tienen n´ umeros crom´ aticos χ(G1 ), χ(G2 ), . . . , χ(Gk ) respectivamente, entonces χ(G) = m´ax {χ(Gi )} 1≤i≤k

Ve rs i´o n

Para verlo, comprobamos 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.

Pero tambi´en se cumple que χ(G) ≤ m´ ax 1≤i≤k {χ(Gi )}. Supongamos que tenemos evaluado m´ax 1≤i≤k {χ(Gi )}. Con este n´ umero de colores podremos colorear la componente conexa m´as “dif´ıcil”. Pero tambi´en las otras, que necesitan menos colores.

5.

Si G y G′ son grafos isomorfos, entonces χ(G) = χ(G′ ). El propio isomorfismo aplica coloraciones en G en coloraciones en G′ .

Ejemplo 8.4.1 Calculemos el n´ umero crom´ atico de algunos grafos. Para colorear el grafo completo con n v´ertices, Kn , necesitamos tantos colores como v´ertices (porque cuando asignamos un color a un v´ ertice, ya no podemos utilizar este color de nuevo). As´ı que χ(Kn ) ≥ n. Pero el n´ umero crom´atico de un grafo no puede ser mayor que el n´ umero de v´ertices, as´ı que χ(Kn ) = n . Por tanto, si un grafo G contiene a un Kn como subgrafo, ya tenemos una cota inferior para χ(G). Para el grafo lineal con n v´ertices, Ln (n ≥ 2), observemos primero que lo podemos colorear con s´olo dos colores: a b a b a b a ◦ ◦ ◦ ◦ ◦ ◦ ◦ Pero adem´as, como n ≥ 2, al menos hay una arista, as´ı que χ(Ln ) ≥ 2. Por tanto, χ(Ln ) = 2 si n ≥ 2. (versi´ on preliminar 24 de noviembre de 2003)

Cap´ıtulo 8. Grafos

594

El grafo vac´ıo Nn se puede colorear con un u ´ nico color, as´ı que χ(Nn ) = 1. Y rec´ıprocamente: si un grafo se puede colorear con un s´ olo color, entonces es un grafo vac´ıo.

pr eli m in ar

Consideremos el grafo circular Cn , con n ≥ 3. Veamos los primeros casos. Por ejemplo, para C3 , una posible coloraci´ on es la que aparece a a la derecha, que utiliza s´ olo tres colores. Por tanto, χ(C3 ) ≤ 3. Y es f´ acil convencerse de que dos colores no son suficientes. Es decir, que b χ(C3 ) = 3. Para C4 , es f´acil dar una coloraci´on con dos colores, y ´este es el valor m´ınimo que puede tener el n´ umero crom´atico, pues hay aristas. Por tanto, χ(C4 ) = 2. No es dif´ıcil repetir estos argumentos para concluir que: χ(Cn ) =



c

a

b

b

a

2, si n es par

3, si n es impar

De lo anterior deducimos que si un grafo contiene ciclos de orden impar, entonces al menos necesitaremos tres colores para colorearlo.

Ve rs i´o n

El grafo que aparece a la derecha era protagonista en algunas de las discusiones matem´aticas de la pel´ıcula8 El indomable Will Hunting. Su n´ umero crom´atico es 3: al menos requiere tres colores, pues hay ciclos de orden impar. Y es f´acil dar una coloraci´ on que utilice s´ olo esos tres colores.

Consideremos el grafo Rn , que llamaremos grafo rueda, que tiene n + 1 v´ertices. Vemos inmediatamente que el v´ertice central es especial. Cualquier coloraci´ on del grafo le asignar´a un color que ya no podremos volver a usar en el resto del grafo. Pero una vez hayamos coloreado el v´ertice central con un color y nos aseguremos de que no lo volvemos a usar, lo que nos queda es uno circular con n v´ertices, as´ı que χ (R n ) =



3, si n es par; 4, si n es impar.

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 8.4.2 y 8.4.3). 8

Good Will Hunting era el t´ıtulo original de la pel´ıcula dirigida por Gus van Sant en 1997. Es la historia de un hu´erfano (Matt Damon) con problemas psicol´ogicos pero que resulta tener un talento natural para las Matem´ a ticas; es descubierto por un profesor del MIT y toma contacto con un psic´ologo (Robin Williams). Protagonizada tambi´en por 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 24 de noviembre de 2003)

595

8.4. Coloreando grafos

Para el grafo del cubo Qn , para n ≥ 2, como hay aristas, de nuevo χ(Qn ) ≥ 2. Pero el cubo es un grafo bipartito (no completo, recordemos la discusi´ on del final de la subsecci´ on 8.1.3), as´ı que χ(Qn ) = 2. ♣

8.4.1.

pr eli m in ar

En general, y 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). Las cotas que hemos obtenido hasta aqu´ı no son muy precisas, en general (a´ un obtendremos alguna m´as, v´eanse las proposiciones 8.11 y 8.12). Tendremos que esperar a conocer el concepto de polinomio crom´atico (en la secci´on 8.5) para obtener un algoritmo (quiz´ as laborioso) para calcular n´ umeros crom´aticos.

Coloraciones de grafos: relaci´ on con listas y particiones en bloques

Colorear un grafo nos servir´ a para describir de otra manera el problema de construir listas con restricciones. Al fin y al cabo, colorear un grafo G de n v´ertices con k colores es lo mismo que formar listas con repetici´ on permitida de longitud n con los s´ımbolos (colores) {a1 , . . . , a k }, de manera que si {i, j} ∈ A(G), los s´ımbolos que aparecen en las posiciones i y j de la lista son distintos.

Una observaci´on interesante, que nos ser´ au ´ til en ciertos argumentos sobre coloreado es que

Ve rs i´o n

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 son vecinos en G. Y a cada bloque le asignamos un n´ umero de 1 a k distinto.

Es conveniente reflexionar sobre estas equivalencias, que nos permitir´ an abordar algunos problemas sobre listas con prohibiciones con este nuevo lenguaje de grafos. Algunos ejemplos de estas equivalencias ser´ıan: Colorear 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 (n´ otese que no son listas sin repetici´on: la lista (a, b, a) es v´ alida aqu´ı). Colorear el grafo vac´ıo Nn con k colores, us´ andolos todos, es lo mismo que partir el conjunto {1, . . . , n} en k bloques no vac´ıos y luego etiquetar cada bloque con un n´ umero de 1 a k.

Ahora bien, si lo que queremos es colorear el grafo vac´ıo Nn utilizando a lo sumo los colores {a1 , . . . , ak }, entonces estamos formando, simplemente, las n−listas con repetici´ on permitida y sin restricciones con k s´ımbolos. Si tratamos de colorear el grafo completo Kn con k colores, est´ a claro que lo que estamos haciendo es formar listas de longitud n con k s´ımbolos sin repetici´on. (versi´ on preliminar 24 de noviembre de 2003)

Cap´ıtulo 8. Grafos

596

8.4.2.

Algoritmo austero para colorear

pr eli m in ar

Buscamos un procedimiento que nos permita colorear un grafo G = (V, A) con |V | = n, dado un conjunto de colores S = {a, b, . . . } (en principio no limitamos el n´ umero de colores que utilizaremos), de manera que el n´ umero de colores utilizado sea el menor posible. Lo llamaremos9 algoritmo austero, y consta de los siguientes pasos: Paso inicial. 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 , . . . , v n ) .

Ahora asignaremos colores a los v´ertices siguiendo la ordenaci´on elegida. 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.

Ve rs i´o n

k-´ esimo paso. ¿C´omo coloreamos el v´ertice vk , teniendo en cuenta que ya hemos coloreado los k − 1 anteriores? En la lista 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.

Ejemplo 8.4.2 Consideremos el siguiente grafo, en el que ya hemos asignado un orden a los v´ ertices: v1 ◦

v2 ◦

v3◦

v4 ◦ ◦v5

◦ ◦ v7 v6 A v1 le asignamos el color a. Como v2 es vecino de v1 (que ya ha sido previamente coloreado con a), para colorear v2 no podemos utilizar el color a: { a, b, c, d, . . . }

−→

escogemos b.

El v´ertice v3 s´olo tiene un vecino que ya haya sido coloreado, el v2 con b, as´ı que {a,  b, c, d, . . . }

−→

escogemos a.

9

En la literatura anglosa jona se denomina greedy algorithm, que se podr´ıa traducir por algoritmo voraz, acaparador, avaricioso. . . Nuestra traducci´on trata de captar la filosof´ıa del algoritmo, que supone elegir, en cada paso, la opci´ on m´ a s econ´omica, hasta conseguir la coloraci´ on completa.

(versi´ on preliminar 24 de noviembre de 2003)

597

8.4. Coloreando grafos v4 v5 v6 v7

hay hay hay hay

disponibles disponibles disponibles disponibles

{ a,  b, c, d, . . . } {a, b,  c, d, . . . } { a, b, c, d, . . . } { a, b, c, d, . . . }

−→ −→ −→ −→

escogemos c. escogemos a. escogemos b. escogemos b.

pr eli m in ar

Para Para Para Para

Y obtenemos finalmente la coloraci´ on a b ◦ ◦

c ◦

a◦

◦a

◦ ◦ b b As´ı que el algoritmo austero nos permite colorear el grafo con tres colores (el m´ınimo necesario, obs´ervese que hay ciclos de longitud impar). ♣ Y deber´ıamos preguntarnos si este algoritmo siempre funciona de manera ´optima, es decir, si produce siempre una coloraci´on que emplea justo tantos colores como nos diga el n´ umero crom´ atico. El siguiente ejemplo nos muestra que no siempre es as´ı. Ejemplo 8.4.3 Consideremos el grafo del cubo Q3 . Encontramos ordenaciones que utilizan: 1

a

Ve rs i´o n

4

b

6

7

c d

−→

3

a

2

8

1

5

d

c

5

a

b

3

4

2

1

b

−→

8

7

c

3 colores

c a

6

b

c

4

a

b

6

b

7

−→

3

a

2 colores

a

2 8

4 colores

b

b 5

b

a

Esta u ´ltima es la mejor coloraci´on que se puede hacer, pues, recordemos, el cubo Q3 es un grafo bipartito. Dos ense˜ nanzas de este ejemplo: una “buena” ordenaci´on inicial de los v´ertices produce el mejor resultado posible. Y, si comprob´aramos todas las ordenaciones de (versi´ on preliminar 24 de noviembre de 2003)

Cap´ıtulo 8. Grafos

598

v´ertices posibles, ver´ıamos que nunca se utilizan m´as de cuatro colores (por cierto, todos los v´ertices son de grado tres). ¿Es esto algo que ocurre siempre? Lo vemos en un momento. ♣

1 3 5

2n − 1

pr eli m in ar

Ejemplo 8.4.4 Consideremos el grafo bipartito con 2n v´ ertices y tal que cada v´ ertice de la izquierda est´ a unido a todos los de la derecha excepto al que se sit´ ua enfrente suyo. Y establezcamos dos ordenaciones distintas de los v´ ertices: 2 4 6

1 2 3

n+1 n+2 n+3

2n

n

2n

La ordenaci´ on de los v´ertices de la izquierda hace que el algoritmo austero utilice n colores. La de la derecha, sin embargo, hace que el algoritmo austero utilice s´olo 2 colores, que es lo mejor posible (recordemos que el n´ umero crom´atico es 2). Si tomamos n muy grande, nos da una idea de lo “sensible” que es el resultado del algoritmo austero a la ordenaci´ on inicial. ♣ As´ı que conviene definir algunos criterios para ordenar “bien” los v´ertices de un grafo, de manera que el algoritmo sea eficaz. Para ello, necesitamos entender en mayor profundidad el funcionamiento del algoritmo. Empecemos dando una cota sobre el “peor” resultado que puede dar.

Ve rs i´o n

Ejemplo 8.4.5 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 los v´ertices que sean vecinos de vk y que, adem´ as, sean anteriores a vk (que sean del tipo vj , con j < k). Por tanto, en cada paso (como mucho) habr´a tantos colores prohibidos como 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. ♣ El argumento se puede generalizar para obtener una cota superior para el n´ umero crom´atico de un grafo: Proposici´ on 8.11 Sea G un grafo y sea ∆(G) su m´ aximo grado (todos los v´ ertices de G son de grado ≤ ∆(G)). En estas condiciones, el algoritmo austero utiliza a lo sumo ∆(G) + 1 colores. Por tanto, χ(G) ≤ ∆(G) + 1 . La raz´ on es la misma que la que se detallaba en el ejemplo del cubo. Obs´ervese que esta cota puede no ser muy buena (por ejemplo, consid´erese el ejemplo de un grafo bipartito). • Observaci´ on ¿C´omo funciona el algoritmo austero? En cada paso k, el n´ umero de colores prohibidos es el n´ umero de colores utilizados en los v´ertices vecinos y anteriores:     # {colores prohibidos} ≤ m´ın # vecinos , #anteriores = m´ın # vecinos, k − 1 . (versi´ on preliminar 24 de noviembre de 2003)

599

8.4. Coloreando grafos

pr eli m in ar

Una buena ordenaci´on ser´ a aqu´ella en la que, en cada paso, ese m´ınimo sea peque˜ no. As´ı que interesar´ a colocar los v´ertices de mayor grado al principio (cuando el n´ umero de v´ertices anteriores es peque˜ no; as´ı se “neutralizan” 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). En todo caso, es bueno saber que siempre existe una ordenaci´on de los v´ertices de un grafo para la que el algoritmo austero es o´ptimo, emplea exactamente χ(G) colores (cons´ ultese el ejercicio 8.4.4). El problema es que no hay un criterio, m´ as all´a de las observaciones que hemos dado, que nos permita obtener esta ordenaci´ on. En ciertas circunstancias, podemos mejorar la estimaci´ on sobre el n´ umero crom´ atico de un grafo: Proposici´ on 8.12 Si G es un grafo conexo con m´ aximo grado ∆(G), pero en el que existe al menos un v´ ert...