Coloreado de grafos

Pedro González Ruiz

Resumen

En ésta página dispone de un programa para colorear cualquier grafo. Este concepto se explica más adelante y es muy útil para resolver muchos problemas. Se presentan varios ejemplos para que pueda entenderlo. Debe ejecutarse en un emulador de terminal o dentro de emacs bajo el sistema operativo Linux. Está hecho en stklos, una implementación de Scheme, un dialecto de Lisp. No es necesario saber Lisp para poder manejarlo, aunque debe seguir escrupulosamente la sintaxis del lenguaje para evitar errores. Dispone de un apartado dentro de éste artículo, a modo de pequeño tutorial, para comprender la sintaxis y semántica de ésta versión de Lisp, al que se adaptará rápidamente.

Descarga e instalación del intérprete de Lisp

Descarga

Debe tener instalado el compilador de C para completar éste apartado. En fin, descargue los fuentes del programa en

Descargar el intérprete de Lisp

Como es habitual, elija la última versión.

Instalación

Abra un emulador de terminal, por ejemplo xterm. Sitúese en un directorio (carpeta) dentro de su propio espacio donde tenga permiso de escritura (supongamos que se llama maniobras). Copie aquí el archivo descargado, y descomprímalo, introduciendo:

pedro@servidor2:~/maniobras> tar zxvf stklos-1.10.tar.gz 
      

Mucha información saldrá en pantalla. Liste el directorio:

pedro@servidor2:~/maniobras> ls -al
total 5968
drwxr-xr-x  3 pedro users      51 feb  9 12:47 .
drwxr-xr-x 84 pedro users    4096 feb  9 11:02 ..
drwxr-xr-x 14 pedro users    4096 dic 31  2011 stklos-1.10
-rw-r--r--  1 pedro users 6097807 feb  9 12:47 stklos-1.10.tar.gz
	

Cámbiese al directorio creado por la orden tar:

pedro@servidor2:~/maniobras> cd stklos-1.10/
	

Debe leerse, básicamente, los archivos README e INSTALL. No obstante, éste tipo de programas se construyen con los siguientes pasos:

1. Ejecute el programa de configuración configure, el cual intenta determinar el tipo de sistema que Vd. tiene y las herramientas que debe tener instaladas para que todo funcione. En pocas palabras, con el compilador de C, las librerías fundamentales para el enlazado y el mantenedor de proyectos make es suficiente para que todo vaya bien. No obstante, si algo le falta, configure se lo hará saber, lo instala y vuelva a ejecutar. En fin, introduzca:

   pedro@servidor2:~/maniobras/stklos-1.10> ./configure
   	    

   Mucha información saldrá en pantalla. Si todo ha ido bien, ésta orden finalizará con un informe, que en mi caso concreto es:

   SUMMARY
   *******
                  System:  Linux-4.1.39-56-default
                 OS nick:  LINUX_4_1
                 OS type:  unix
         Install prefix :  /usr/local
              C compiler:  gcc
       Compilation flags:  -g -O2
          Thread support:  pthreads
   System libraries used:  libffi libpcre libgmp libgc
      Compiled libraries: 
    
   If this is correct, you can just type 'make' now at your shell prompt.
   Otherwise, re-run 'configure' with correct options.
   	    

2. En mi caso, lo que propone configure es suficiente, así que, ahora procedemos a crear el intérprete, para lo cual, entramos:

   pedro@servidor2:~/maniobras/stklos-1.10> make
   	    

   Otra vez, mucha información saldrá en pantalla. Si todo ha ido bien, debe aparecer algo parecido a las últimas líneas que a continuación se muestran:

   make[1]: Leaving directory '/home/pedro/maniobras/stklos-1.10/doc'
   make[1]: Entering directory '/home/pedro/maniobras/stklos-1.10'
   make[1]: Nothing to be done for 'all-am'.
   make[1]: Leaving directory '/home/pedro/maniobras/stklos-1.10'
   	    

3. Por último, tenemos que instalar el programa, lo que debe hacerse como usuario root. Así pues, sin moverse del directorio en el que se encuentra, entre (para convertirse en root):

   pedro@servidor2:~/maniobras/stklos-1.10> su
   Contraseña:
   	    

   Finalmente, como root, escriba:

   servidor2:/home/pedro/maniobras/stklos-1.10 # make install
   	    

   con lo que el programa se habrá instalado en /usr/local/bin. Comprobémoslo:

   pedro@servidor2:~/maniobras/stklos-1.10> ls -al /usr/local/bin/
   	    

   Muestro las últimas líneas:

   ....
   -rwxr-xr-x 1 root root 2374160 sep 12  2016 stklos
   -rwxr-xr-x 1 root root    4603 sep 12  2016 stklos-compile
   -rwxr-xr-x 1 root root    2350 sep 12  2016 stklos-config
   -rwxr-xr-x 1 root root  113799 sep 12  2016 stklos-genlex
   -rwxr-xr-x 1 root root   51589 sep 12  2016 stklos-pkg
   -rwxr-xr-x 1 root root    1099 sep 12  2016 stklos-script
   	    

Comprobación de funcionamiento del intérprete

Asegúrese de que tiene paso para ejecutar programas en /usr/local/bin. Para ello, introduzca:

pedro@servidor2:~/maniobras> echo $PATH
/home/pedro/bin:/usr/local/bin:/usr/bin:/bin:/usr/bin/X11:/usr/games
	

Observe que, en mi caso, yo lo tengo. Si no fuera así, escriba:

pedro@servidor2:~/maniobras> PATH=$PATH:/usr/local/bin
	

En un emulador de terminal (xterm, konsole, etc.), introduzca:

pedro@servidor2:~/maniobras> stklos
*   STklos version 1.10
 *  Copyright (C) 1999-2011 Erick Gallesio - Universite de Nice 
* * [Linux-4.1.27-27-default-x86_64/pthread/no-readline/utf8]
	

Si observa esto, o algo parecido, es que el intérprete se construyó bien. No obstante, para asegurarnos, hacemos unas cuantas pruebas:

stklos> (+ 1 2 3 4)
10
stklos> (expt 2 100)
1267650600228229401496703205376
stklos> (string-append "Cervantes " "escribió " "El Quijote.")
"Cervantes escribió El Quijote."
	

es decir 1 + 2 + 3 + 4 = 10 y 2^100=1267650600228229401496703205376.

Salga del programa, entrando:

stklos> (exit)
      

o bien, pulsando la combinación Ctrl-D.

Concepto de grafo y coloreado

Un grafo es un ente matemático abstracto formado por vértices o nodos, y conexiones entre dichos nodos, llamadas aristas o enlaces. Por ejemplo, la siguiente figura representa un grafo:

Los vértices son {v₁,v₂,v₃,v₄,v₅,v₆,v₇}, y según vemos, hay una arista (conexión) entre v₁ y v₂, pero no la hay entre v₂ y v₄.

Puede interpretar el grafo de muchas formas. Veamos algunos ejemplos.

1. Los nodos son pueblos y las aristas, carreteras, entonces el grafo anterior nos muestra que hay una carretera que te lleva de v₁ a v₂. Si quiere ir desde v₁ hasta v₄, tiene dos posibilidades para hacerlo, por el camino (v₁,v₂,v₃,v₄), o bien (v₁,v₂,v₅,v₄).
2. Los vértices son países y un enlace entre dos nodos indica que ambos son lindantes, es decir, tienen frontera común. Así, v₁ y v₂ son fronterizos, mientras que v₂ y v₄ no.

3. Los vértices son grupos de alumnos y una arista entre nodos indica que que esos dos grupos tienen al menos un profesor en común. Así, v₄ y v₆ tienen profesores comunes, mientras que v₅ y v₆ no.

   Si queremos hacer una reunión global de profesores para comentar la evolución de sus grupos de alumnos, en un aula podrían reunirse los profesores de v₅, y a esa misma hora, en otra aula, los de v₆. Sin embargo, los de v₄ y v₅ deben ir en horas distintas, pues al haber, al menos, un profesor en común entre ambos grupos, éste no podría estar en ambos lugares a la vez.

Concepto de coloreado de un grafo

Entendido ya el concepto de grafo pasemos al de coloreado. Se entiende por coloreado de un grafo el asignar a cada vértice un color con la condición de que si dos vértices son adyacentes, es decir, hay una arista o enlace entre ellos, entonces, ambos deben tener colores diferentes.

Por ejemplo, la siguiente figura es un coloreado del grafo de más arriba.

En el ejemplo planteado antes sobre la reunión global de los profesores, en una hora y en 4 aulas, juntaríamos a los profesores de los grupos (v₁,v₃,v₅,v₆), y a la siguiente hora, en 2 aulas a (v₂,v₄). En otras palabras, en 2 horas hemos resuelto el problema. Como es evidente, la solución trivial es utilizar 6 horas, una por cada curso. Gracias al coloreado del grafo, hemos mejorado, los profesores lo agradecen y todos contentos.

Pequeña introducción a Lisp

Antes de empezar a colorear grafos, es conveniente familiarizarse un poco con el lenguaje Lisp. No pretendo mostrar aquí un tutorial, sino un par de conceptos que una vez aprendidos, hagan más simple la comprensión de lo que sigue.

En Lisp, el elemento fundamental de trabajo es la lista, que consiste en un conjunto de elementos dispuestos en un orden determinado. La representación externa es un paréntesis de apertura (, los elementos separados por espacios en blanco, y un paréntesis de cierre ), es decir:

l = (e₁ e₂ ... e_n)

donde e₁ e₂ ... y e_n son los elementos. Estos a su vez pueden ser listas u otro tipo de datos, por ejemplo, si todos son números, la lista l puede considerarse como un vector de n componentes o un punto del espacio afín de n dimensiones. Si el orden de los elementos es irrelevante y son todos distintos, la lista l puede ser considerada como un conjunto de n objetos, etc..

Una función también se representa como una lista, en concreto, la primera componente es el nombre de la función y el resto sus argumentos. Lisp utiliza la notación prefija, que salvo pequeñas diferencias, coincide con la notación matemática funcional habitual. Por ejemplo, una función de nombre f con tres variables x,y,z, en matemáticas se escribe como:

f(x,y,z)

y en Lisp (desplace el paréntesis izquierdo de la expresión anterior un lugar a la izquierda y quite las comas) sería así:

(f x y z)

Sin embargo, en matemáticas es habitual utilizar también la notación infija, en la que la función va situada entre sus argumentos. Por ejemplo, la suma de cuatro variables se escribe como:

x + y + z + t

En Lisp, no, ya que siendo coherente con la notación prefija, se escribiría así:

(+ x y z t)

Veamos un ejemplo más, el cociente

(x + y + z) ⁄ (u - v)

se escribiría en Lisp como

(/ (+ x y z) (- u v))

es decir, siempre una lista. Observe como la lista anterior tiene tres componentes. La primera es el símbolo / y la segunda y tercera son listas.

Lisp, por defecto, siempre evalúa cualquier expresión que se encuentre en su camino. Esto es necesario aprenderlo bien. Veámoslo con un ejemplo. Supongamos que x = 2, y = 3, u = 8, v = 4. Consideremos la expresión:

(* (+ x y) (- u v))

Sustituyendo las variables por sus valores, quedaría como:

(* (+ 2 3) (- 8 4))

El intérprete evaluaría las sublistas internas:

(* 5 4)

y finalmente, evaluaría ésta última lista para devolver el valor 20, y aquí pararía la evaluación, pues un número se evalúa a sí mismo.

Para que no todo sea teórico, hagámoslo interactuando con el intérprete, y para ello, es conveniente ejecutar éste dentro de emacs, pues podemos recuperar entradas anteriores y corregir o cambiar sin tener que volver a teclearlo todo de nuevo. Entre en emacs y pulse Alt x. En la línea inferior (minibuffer) aparece M-x. Escriba la palabra shell, y pulse enter. Esto crea un emulador de terminal dentro de emacs. A continuación, ejecute el intérprete, escribiendo stklos. Véamoslo:

pedro@servidor2:~/maniobras> stklos
*   STklos version 1.10
 *  Copyright (C) 1999-2011 Erick Gallesio - Universite de Nice 
* * [Linux-4.4.114-42-default-x86_64/pthread/no-readline/utf8]
stklos> (* (+ 2 3) (- 8 4))
20
stklos> 
      

Para moverse en el histórico de órdenes, las combinaciones de teclas son Alt p y Alt n, o bien, moverse con las flechas arriba y abajo, y pulsar enter. Si es posible, haga las prácticas que siguen con emacs mejor que con un emulador de terminal.

En definitiva, siempre que Lisp encuentra una lista

l = (f a₁ a₂ ... a_n)

considera que el primer elemento de la lista es una función f y el resto de la lista, es decir, (a₁ a₂ ... a_n) son los argumentos de dicha función. Esto es lo normal. Repitiendo, para fijar ideas, en matemáticas se escribiría como:

f(a₁,a₂, ...,a_n)

Si, por ejemplo, escribimos

(1 2 3 4)

Lisp entenderá que estamos llamando a una función cuyo nombre es el número 1 y cuyos argumentos son (2 3 4). Evidentemente, esto no es correcto y el intérprete mostrará un mensaje de error.

stklos> (1 2 3 4)
**** Error:
%execute: bad function `1'. Cannot be applied
	(type ",help" for more information)
stklos> 
      

Sin embargo, a veces necesitamos que el intérprete no se comporte así, es decir, no queremos que evalúe una lista. Veamos un ejemplo, escribimos la función sumav con dos argumentos que son listas, y esperamos que devuelva la suma habitual de vectores en n dimensiones. En fin:

stklos> (define (sumav l1 l2) (map + l1 l2))
;; sumav
      

Si introduzco

stklos> (sumav (5 0 -3 4) (2 1 7 8))
**** Error:
%execute: bad function `5'. Cannot be applied
	(type ",help" for more information)
      

y ocurre lo que ya sabíamos, cuando esperábamos el resultado

(7 1 4 12)

consistente en sumar los números correspondientes a cada coordenada.

En fin, por lo explicado antes, Lisp, al encontrar la lista (5 0 -3 4) intentará llamar a la función de nombre 5 y se produce el error. Idéntico comentario a la otra lista (2 1 7 8).

Para evitar esto, se utiliza el apóstrofo ', el cual, cuando está situado a la izquierda de una lista, obliga al intérprete a que no evalúe la lista, con lo que, la forma correcta de conseguir lo que queremos es, introduciendo:

stklos> (sumav '(5 0 -3 4) '(2 1 7 8))
(7 1 4 12)
stklos> (sumav '(2 3 1 -12 4 7 8) '(1 2 3 4 5 6))
(3 5 4 -8 9 13)
stklos> (sumav '(4 5) '(6 7))
(10 12)
      

Ahora sí. Con esto acaba ésta pequeña introducción a Lisp. Si está interesado en este lenguaje, busque en internet manuales y tutoriales donde aprenderlo.

Representación de grafos

En un grafo, la lista de adyacencia de un vértice o nodo es el conjunto de todos aquellos vértices que conectan con él. Por ejemplo, en el grafo

la lista de adyacencia del vértice v₂ es (v₁,v₃,v₅), la de v₄ es (v₆,v₅,v₃), mientras que la de v₁ es (v₂)

Un grafo se representa en el programa como una lista de listas, donde cada lista componente es tal que su primer elemento es un vértice y el resto, la lista de adyacencia de ese vértice. Formalmente hablando:

grafo = ((v₁ v₁₁ v₁₂ ... v_1,n1) (v₂ v₂₁ v₂₂ ... v_2,n2) ... (v_m v_m1 v_m2 ... v_m,nm))

Así, si escogemos, por ejemplo, la primera sublista

(v₁ v₁₁ v₁₂ ... v_1,n1)

entonces, v₁ es un vértice y (v₁₁ v₁₂ ... v_1,n1) su lista de adyacencia.

El intérprete de Lisp no tiene problemas con separar las sublistas en líneas y sangrarlas para mejorar la legibilidad. Así pues, visto lo anterior, el grafo de la figura se representaría en el programa como:

(define grafo1 '(
		 (v1 v2)
		 (v2 v1 v3 v5)
		 (v3 v2 v4)
		 (v4 v3 v5 v6)
		 (v5 v2 v4)
		 (v6 v4)
		 ))
      

El orden en la lista de adyacencia es completamente irrelevante, aunque eso sí, el primer elemento de cada sublista tiene que ser el nodo. Para el resto, cualquier permutación es válida. En otras palabras, la lista de adyacencia es un conjunto. Para aclarar, por ejemplo, la información del vértice v₂ también podría ser (v₂ v₃ v₅ v₁) o (v₂ v₅ v₁ v₃).

Un ejemplo más, el grafo

se representaría como

(define grafo2 '(
		(v1 v2 v3 v4)
		(v2 v1 v4 v5)
		(v3 v1 v6 v4 v7)
		(v4 v1 v2 v3 v6 v7 v9 v5)
		(v5 v2 v4 v7 v8 v9)
		(v6 v3 v4 v7)
		(v7 v3 v6 v4 v5)
		(v8 v5)
		(v9 v5 v4)
		))
      

Descarga y manejo del programa

Descargue el programa en el siguiente enlace

coloreado.tgz

Abra un emulador de terminal, por ejemplo xterm. Sitúese en un directorio (carpeta) dentro de su propio espacio donde tenga permiso de escritura (supongamos que se llama maniobras). Copie aquí el archivo descargado, y descomprímalo, introduciendo:

pedro@servidor2:~/maniobras> tar zxvf coloreado.tgz 
coloreado.stk
ejemplos.stk
      

Liste el directorio:

pedro@servidor2:~/maniobras> ls -al
total 40
drwxr-xr-x  2 pedro users    68 feb  9 11:39 .
drwxr-xr-x 89 pedro users  4096 feb  9 11:13 ..
-rw-r--r--  1 pedro users 13619 feb  9 11:30 coloreado.stk
-rw-r--r--  1 pedro users  5967 feb  9 11:31 coloreado.tgz
-rw-r--r--  1 pedro users  6685 feb  9 11:30 ejemplos.stk
      

El archivo coloreado.tgz no lo necesita más, así que puede borrarlo si lo desea. El archivo coloreado.stk es el programa y ejemplos.stk contiene algunos ejemplos de grafos y datos necesarios para las explicaciones que siguen. Son archivos de texto, y por consiguiente, puede verlos con cualquier editor de textos.

Sin más demora, pasamos ya a practicar. Suponemos que el directorio de trabajo es ~/maniobras, y es en éste directorio donde están situados los archivos coloreado.stk y ejemplos.stk. Entre en emacs, y pulse Alt x. En la línea inferior (minibuffer) aparece M-x. Escriba la palabra shell, y pulse enter. Esto crea un emulador de terminal dentro de emacs.

pedro@servidor2:~> cd ~/maniobras/
pedro@servidor2:~/maniobras> stklos
*   STklos version 1.10
 *  Copyright (C) 1999-2011 Erick Gallesio - Universite de Nice 
* * [Linux-4.4.114-42-default-x86_64/pthread/no-readline/utf8]
stklos> (load "coloreado.stk")
      

Con esto, cargamos el programa, de camino también se carga ejemplos.stk. En fin, se acabaron los preparativos, ya podemos comenzar a trabajar.

Ejemplo 1 (grafo1)

Comencemos con el grafo

ya visto en explicaciones previas. Está definido en ejemplos.stk como:

(define grafo1 '(
		 (v1 v2)
		 (v2 v1 v3 v5)
		 (v3 v2 v4)
		 (v4 v3 v5 v6)
		 (v5 v2 v4)
		 (v6 v4)
		 ))
      

stklos> grafo1
((v1 v2) (v2 v1 v3 v5) (v3 v2 v4) (v4 v3 v5 v6) (v5 v2 v4) (v6 v4))
      

Para verlo en vertical, escriba:

stklos> (for-each (lambda(x) (format #t "~a\n" x)) grafo1)
(v1 v2)
(v2 v1 v3 v5)
(v3 v2 v4)
(v4 v3 v5 v6)
(v5 v2 v4)
(v6 v4)
      

Cuando se edita un grafo, es usual introducir un enlace de a a b y no hacerlo de b a a. Para evitar éste error, el programa proporciona un predicado (es-consistente?) que retorna verdadero si el grafo está bien definido o falso, si no lo está. El símbolo de verdadero en Lisp es #t y falso es #f. En fin:

stklos> (es-consistente? grafo1)
#t
      

Para colorear grafo1, introduzca:

stklos> (coloreado grafo1)
((1 v2 v4) (2 v5 v3 v6 v1))
      

lo que quiere decir (los colores son números) que asignamos el color 1 a los vértices {v₂,v₄} y el color 2 a los vértices {v₁,v₃,v₅,v₆}. Vd., por su cuenta, puede cambiar los números por colores, y cambiar 1 por rojo, 2 por verde, o cualquier otro color.

La función coloreado admite dos argumentos opcionales que son:

1. cc, (con colores), booleano. Si es verdadero (valor por defecto), se muestran los colores. En caso contrario, no.
2. al, (aleatorio), booleano. Por defecto es falso. Quiere decir que cuando está coloreando y dispone de varias opciones, si es #t elige al azar una de ellas, y si es #f (por defecto), elige la primera. Con ésta opción puede obtener soluciones distintas cada vez que llama a la función.

stklos> (coloreado grafo1 :cc #f)
((v2 v4) (v5 v3 v6 v1))
      

Observe que los números han desaparecido. Si quiere colores de verdad, introduzca:

stklos> (map cons '(rojo verde) (coloreado grafo1 :cc #f))
((rojo v2 v4) (verde v5 v3 v6 v1))
      

También

stklos> (coloreado grafo1 :al #t)
((1 v2 v6) (2 v4 v1) (3 v5 v3))
stklos> (coloreado grafo1 :al #t)
((1 v2 v6) (2 v4 v1) (3 v5 v3))
stklos> (coloreado grafo1 :al #t)
((1 v2 v4) (2 v5 v6 v1 v3))
      

Observe que en el primer ejemplo, se ha coloreado el grafo con tres colores, mientras que en el ejemplo anterior se hizo con dos. Esto nos lleva a otro problema, el del número cromático, que más adelante comentaremos.

Ejemplo 2 (grafo2)

Sigamos con

visto también anteriormente. Está definido en ejemplos.stk como:

(define grafo2 '(
		(v1 v2 v3 v4)
		(v2 v1 v4 v5)
		(v3 v1 v6 v4 v7)
		(v4 v1 v2 v3 v6 v7 v9 v5)
		(v5 v2 v4 v7 v8 v9)
		(v6 v3 v4 v7)
		(v7 v3 v6 v4 v5)
		(v8 v5)
		(v9 v5 v4)
		))
      

stklos> grafo2
((v1 v2 v3 v4) (v2 v1 v4 v5) (v3 v1 v6 v4 v7) (v4 v1 v2 v3 v6 v7 v9 v5)
(v5 v2 v4 v7 v8 v9) (v6 v3 v4 v7) (v7 v3 v6 v4 v5) (v8 v5) (v9 v5 v4))
stklos> (for-each (lambda(x) (format #t "~a\n" x)) grafo2)
(v1 v2 v3 v4)
(v2 v1 v4 v5)
(v3 v1 v6 v4 v7)
(v4 v1 v2 v3 v6 v7 v9 v5)
(v5 v2 v4 v7 v8 v9)
(v6 v3 v4 v7)
(v7 v3 v6 v4 v5)
(v8 v5)
(v9 v5 v4)
stklos> (es-consistente? grafo2)
#t
      

En fin

stklos> (coloreado grafo2)
((1 v4 v8) (2 v5 v3) (3 v7 v1 v9) (4 v6 v2))
      

Como siempre, si queremos cambiar los números por colores

stklos> (map cons '(rojo azul verde amarillo) (coloreado grafo2 :cc #f))
((rojo v4 v8) (azul v5 v3) (verde v7 v1 v9) (amarillo v6 v2))
      

Ejemplo 3 (andalucia)

Andalucía es la región de España en la que vivo. Un mapa de ella es

El grafo de la región es:

Un enlace entre provincias indica que lindan entre ellas, es decir, son fronterizas.

Está definido en ejemplos.stk como:

(define andalucia '(
	(almeria granada)
	(granada almeria malaga cordoba jaen)
	(malaga cadiz sevilla cordoba granada)
	(cadiz malaga sevilla huelva)
	(huelva sevilla cadiz)
	(sevilla huelva cadiz malaga cordoba)
	(cordoba sevilla jaen granada malaga)
	(jaen cordoba granada)
))
      

stklos> (es-consistente? andalucia)
#t
      

En fin

stklos> (coloreado andalucia)
((1 sevilla granada) (2 cordoba cadiz almeria) (3 malaga jaen huelva))
      

El grafo coloreado es:

y volviendo al mapa:

Ejemplo 4 (petersen)

Veamos ahora el grafo de Petersen.

Está definido en ejemplos.stk como:

(define petersen '(
		   (v1 v2 v5 w1)
		   (v2 v1 v3 w2)
		   (v3 v2 v4 w3)
		   (v4 v3 v5 w4)
		   (v5 v1 v4 w5)
		   (w1 v1 w3 w4)
		   (w2 v2 w5 w4)
		   (w3 v3 w1 w5)
		   (w4 v4 w1 w2)
		   (w5 v5 w2 w3)
		   )
  )
      

stklos> (es-consistente? petersen)
#t
stklos> (coloreado petersen)
((1 w2 w1 v3 v5) (2 w4 w3 v1) (3 w5 v2 v4))
      

En fin

Ejemplo 5 (España)

Vamos a colorear España, mi nación.

Está definido en ejemplos.stk como:

(define españa '(
		 (almería murcia albacete granada)
		 (granada almería murcia albacete jaén córdoba málaga)
		 (málaga granada córdoba sevilla cádiz)
		 (cádiz málaga sevilla huelva)
		 (huelva cádiz sevilla badajoz)
		 (sevilla huelva cádiz málaga córdoba badajoz)
		 (córdoba jaén ciudad-real badajoz sevilla málaga granada)
		 (jaén albacete ciudad-real córdoba granada)

		 (huesca navarra zaragoza lérida)
		 (zaragoza tarragona lérida huesca navarra la-rioja soria guadalajara teruel)
		 (teruel castellón tarragona zaragoza guadalajara cuenca valencia)

		 (asturias lugo león cantabria)

		 (madrid ávila toledo cuenca guadalajara segovia)
		 (toledo cuenca madrid ávila cáceres badajoz ciudad-real)
		 (ciudad-real albacete cuenca toledo badajoz córdoba jaén)
		 (cuenca valencia teruel guadalajara madrid toledo ciudad-real albacete)
		 (guadalajara madrid cuenca teruel zaragoza soria segovia)

		 (cantabria asturias león palencia burgos vizcaya)
		 (burgos soria la-rioja álava vizcaya cantabria palencia valladolid segovia)
		 (la-rioja soria zaragoza navarra álava burgos)
		 (soria guadalajara zaragoza navarra la-rioja burgos segovia)
		 (segovia madrid guadalajara soria burgos valladolid ávila)
		 (ávila cáceres salamanca valladolid segovia madrid toledo)
		 (valladolid salamanca zamora león palencia burgos segovia ávila)
		 (palencia burgos cantabria león valladolid)

		 (barcelona tarragona lérida gerona)
		 (tarragona barcelona lérida zaragoza teruel castellón)
		 (lérida huesca zaragoza tarragona barcelona gerona)
		 (gerona lérida barcelona)

		 (cáceres badajoz toledo ávila salamanca)
		 (badajoz huelva sevilla córdoba ciudad-real toledo cáceres)

		 (la-coruña lugo pontevedra)
		 (lugo la-coruña orense pontevedra león asturias)
		 (orense zamora león lugo pontevedra)
		 (pontevedra orense lugo la-coruña)

		 (león zamora valladolid palencia cantabria asturias lugo orense)
		 (zamora salamanca valladolid león orense)
		 (salamanca cáceres ávila valladolid zamora)

		 (albacete murcia alicante valencia cuenca ciudad-real jaén granada almería)
		 (murcia alicante albacete granada almería)

		 (navarra guipúzcoa álava la-rioja soria zaragoza huesca)

		 (castellón valencia teruel tarragona)
		 (valencia albacete alicante castellón teruel cuenca)
		 (alicante murcia albacete valencia)

		 (vizcaya cantabria burgos álava guipúzcoa)
		 (álava guipúzcoa vizcaya burgos la-rioja navarra)
		 (guipúzcoa álava vizcaya navarra)
		 )
  )
      

Que el lector me perdone si he puesto un enlace de más o de menos, es decir, si he puesto fronterizas a provincias que no lo son, o al revés, no he puesto lindantes a provincias que lo son.

stklos> (es-consistente? españa)
#t
stklos> (coloreado españa)
((1 burgos albacete zaragoza |león| badajoz |ávila| |málaga| pontevedra |castellón| |guipúzcoa| barcelona) (2 cuenca valladolid |córdoba| soria |álava| cantabria tarragona lugo |cáceres| murcia |cádiz| huesca gerona) (3 teruel ciudad-real segovia granada navarra |lérida| sevilla palencia salamanca orense vizcaya asturias alicante |la-coruña|) (4 guadalajara toledo valencia la-rioja |jaén| zamora |almería| huelva) (5 madrid))
      

o mejor

stklos> (for-each (lambda(x) (format #t "~a\n" x)) (coloreado españa))
(1 burgos albacete zaragoza león badajoz ávila málaga pontevedra castellón guipúzcoa barcelona)
(2 cuenca valladolid córdoba soria álava cantabria tarragona lugo cáceres murcia cádiz huesca gerona)
(3 teruel ciudad-real segovia granada navarra lérida sevilla palencia salamanca orense vizcaya asturias alicante la-coruña)
(4 guadalajara toledo valencia la-rioja jaén zamora almería huelva)
(5 madrid)
      

¡Un desastre, el mapa de España con 5 colores!. El teorema de los cuatro colores afirma que cualquier mapa puede colorearse con 4 colores y nuestra función lo ha hecho con cinco.

En fin, no nos pongamos nerviosos. Dentro del programa, disponemos de la función coloreado-aleatorio-numero que llama a la función habitual coloreado de forma aleatoria tantas veces como se desee y devuelve un coloreado del grafo con el número mínimo de colores que encontró en el camino. Veámoslo:

(define p (coloreado-aleatorio-numero españa 100))
;; p
stklos> p
((1 burgos zamora pontevedra granada |ávila| |lérida| |cádiz| valencia badajoz navarra guadalajara asturias) (2 albacete palencia teruel huelva lugo la-rioja |córdoba| huesca salamanca toledo vizcaya barcelona segovia) (3 zaragoza valladolid murcia |álava| |cáceres| sevilla ciudad-real cantabria |castellón| orense |la-coruña| gerona madrid) (4 |león| alicante cuenca soria tarragona |almería| |málaga| |guipúzcoa| |jaén|))
      

Esto ya está mucho mejor, España coloreada con cuatro colores. Hemos llamado a la función coloreado 100 veces de forma aleatoria. Para ver el resultado mejor:

stklos> (for-each (lambda(x) (format #t "~a\n" x)) p)
(1 burgos zamora pontevedra granada ávila lérida cádiz valencia badajoz navarra guadalajara asturias)
(2 albacete palencia teruel huelva lugo la-rioja córdoba huesca salamanca toledo vizcaya barcelona segovia)
(3 zaragoza valladolid murcia álava cáceres sevilla ciudad-real cantabria castellón orense la-coruña gerona madrid)
(4 león alicante cuenca soria tarragona almería málaga guipúzcoa jaén)
      

Y pasando al mapa

La función coloreado-aleatorio-numero dispone también de un argumento opcional, que es el ya comentado antes cc, es decir, con color o sin color. El argumento aleatorio no lo tiene, ya que siempre es aleatorio. Probemos 1000 o 10000 veces para ver si salen menos colores:

stklos> (coloreado-aleatorio-numero españa 1000)
((1 burgos alicante |guipúzcoa| barcelona |jaén| |almería| zamora badajoz |castellón| asturias cuenca |málaga| zaragoza pontevedra |ávila|) (2 albacete |cáceres| valladolid soria huesca orense |cádiz| madrid |córdoba| |álava| |la-coruña| cantabria teruel gerona) (3 |león| sevilla guadalajara |lérida| salamanca vizcaya la-rioja murcia valencia ciudad-real) (4 segovia huelva granada tarragona toledo lugo navarra palencia))
stklos> (coloreado-aleatorio-numero españa 10000)
((1 burgos |lérida| pontevedra cuenca murcia |ávila| |málaga| asturias zamora |jaén| navarra |castellón| huelva) (2 albacete |álava| salamanca teruel palencia badajoz soria gerona lugo huesca madrid |cádiz|) (3 zaragoza |la-coruña| granada vizcaya segovia ciudad-real sevilla |león| alicante |cáceres| barcelona) (4 valladolid cantabria orense la-rioja |almería| tarragona guadalajara toledo valencia |córdoba| |guipúzcoa|))
      

No. Parece que con menos de 4 colores no puede ser. Finalmente, sin colores:

stklos> (for-each (lambda(x) (format #t "~a\n" x)) (coloreado-aleatorio-numero españa 100 :cc #f))
(burgos sevilla ciudad-real ávila pontevedra asturias tarragona zamora navarra valencia gerona murcia guadalajara)
(albacete salamanca huesca teruel huelva guipúzcoa segovia palencia barcelona lugo córdoba la-rioja toledo)
(zaragoza málaga jaén león vizcaya madrid la-coruña cáceres castellón alicante almería)
(cuenca lérida granada cantabria valladolid cádiz álava badajoz orense soria)
      

Ejemplo 6 (Horario de reuniones)

En éste apartado vamos también a colorear un grafo, pero no disponemos de él, en principio, sino que tenemos que construirlo. El problema es el siguiente:

Partimos de una lista de cursos por profesor, es decir, por cada profesor, los cursos en los que éste da clase, y queremos hacer un horario de reuniones (en España se llaman evaluciones), es decir, a una determinada hora se reunen todos los profesores que dan clase a un curso, en la siguiente hora, igual, pero otro curso, y así sucesivamente.

Cualquiera puede pensar que el problema es trivial, con el siguiente razonamiento. Si tengo 10 cursos, a primera hora se reunen los profesores del primer curso, a segunda hora, los del segundo, y así sucesivamente. Ahora bien, si dos cursos no tienen profesores en común, ambos pueden reunirse a la misma hora, esto no genera ningún conflicto y ganaríamos una hora.

Para entenderlo bien, empecemos con un ejemplo simple y para ello consideremos las siguiente lista incluída es ejemplos.stk:

(define cpp0 '(
	       (p1 g1 g2 g3)
	       (p2 g2 g4 g5)
	       (p3 g5 g6 g7)
	       )
  )
      

Está formada por siete cursos, {g₁,g₂,g₃,g₄,g₅,g₆,g₇} y tres profesores {p₁,p₂,p₃} que dan clase a estos cursos. El significado de la lista debe estar claro (recuerde de lo que partimos, lista de cursos por profesor), es decir, el profesor p₁ da clase en los cursos {g₁,g₂,g₃}, p₂ en {g₂,g₄,g₅} y p₃ en {g₅,g₆,g₇}. Es evidente que en el horario que queremos hacer,los cursos g₁ y g₂ no pueden ir a la misma hora, ya que el profesor p₁, da clase en los dos, y por tanto, no puede estar en dos sitios a la vez. Introduzca:

stklos> (construye-grafo cpp0)
((g1 g2 g3) (g2 g3 g1 g4 g5) (g3 g1 g2) (g4 g5 g2) (g5 g2 g4 g6 g7) (g6 g7 g5) (g7 g5 g6))
      

Éste es el grafo de trabajo. Comentemos, por ejemplo, la primera componente {g₁,g₂,g₃}. Nos muestra que g₁ no puede ir a la misma hora que g₂, pues hay un profesor común, que es p₁. Tampoco puede ir g₁ con g₃, por la misma razón. En fin, comprendido esto, un coloreado de éste grafo resuelve el problema. Introduzca:

stklos> (define grafo (construye-grafo cpp0))
;; grafo
stklos> grafo
((g1 g2 g3) (g2 g3 g1 g4 g5) (g3 g1 g2) (g4 g5 g2) (g5 g2 g4 g6 g7) (g6 g7 g5) (g7 g5 g6))
      

Mejor así, asignamos el grafo, le damos un nombre, con lo que no tenemos que estar continuamente escribiendo construye-grafo. Ahora sí, introduzca:

stklos> (coloreado grafo)
((1 g2 g6) (2 g5 g1) (3 g3 g4 g7))
      

y problema resuelto. Con la solución trivial, necesitaríamos siete horas (una por cada curso), mientras que con el coloreado solo necesitamos tres, así pues, el horario quedaría de la siguiente forma:

Día X
Hora	Cursos
1	g2,g6
2	g5,g1
3	g3,g4,g7

Hay varias utilidades dentro del programa, en concreto, una lista inversa a la incial ccp0, la proporciona la función lista-de-profesores-por-curso. Para verlo, introduzca:

stklos> (lista-de-profesores-por-curso cpp0)
((g1 p1) (g2 p1 p2) (g3 p1) (g4 p2) (g5 p2 p3) (g6 p3) (g7 p3))
      

Es decir, la misma información que la original, pero puesta de otra forma, es decir, los cursos en cabeza, y los profesores en el resto. Con esta manera se comprende mejor la tabla anterior, pues, por ejemplo g₂ y g₆ van a la vez, puesto que no tienen profesores comunes. Si todavía quiere más información, introduzca:

stklos> (profesores-comunes cpp0)
((g1 g2 p1) (g1 g3 p1) (g1 g4) (g1 g5) (g1 g6) (g1 g7) (g2 g3 p1) (g2 g4 p2) (g2 g5 p2) (g2 g6) (g2 g7) (g3 g4) (g3 g5) (g3 g6) (g3 g7) (g4 g5 p2) (g4 g6) (g4 g7) (g5 g6 p3) (g5 g7 p3) (g6 g7 p3))
      

No se ve muy bien, así que, mejor escribimos:

stklos> (for-each (lambda(x) (format #t "~a\n" x)) (profesores-comunes cpp0))
(g1 g2 p1)
(g1 g3 p1)
(g1 g4)
(g1 g5)
(g1 g6)
(g1 g7)
(g2 g3 p1)
(g2 g4 p2)
(g2 g5 p2)
(g2 g6)
(g2 g7)
(g3 g4)
(g3 g5)
(g3 g6)
(g3 g7)
(g4 g5 p2)
(g4 g6)
(g4 g7)
(g5 g6 p3)
(g5 g7 p3)
(g6 g7 p3)
      

En otras palabras, todas las intersecciones de cursos, cada sublista es una lista de al menos dos componentes, la primera y segunda con los cursos y la tercera si la hay, los profesores comunes a ambos cursos. Por ejemplo, los cursos g₅ y g₆ tienen en común el profesor p₃, mientras que g₄ y g₇ no tienen ningún profesor en común.

Ejemplo 7 (Horario de reuniones más grande)

Visto el ejemplo anterior, consideremos lo mismo, pero con un archivo de datos más grande, y para ello, veamos la siguiente lista incluida en ejemplos.stk:

(define cpp1 '(
			      (hugo 2eso-b 3eso-b 4eso-a 1bac-b 2bac-a)
			      (pablo 1bac-a 1bac-c 2bac-a 3eso-b)
			      (alejandro 1bac-b 1bac-c 1bac-d 2bac-c 2bac-e 4eso-b)
			      (alvaro 2eso-a 2eso-d 3eso-c 1bac-a 1bac-c 2bac-a 2bac-c)
			      (david 2eso-b 2eso-c 2eso-d 1bac-a 1bac-b 1bac-c 1bac-d 2bac-a)
			      (lucas 4eso-a 1bac-b 1bac-c 1bac-d 2bac-a)
			      (mateo 3eso-a 3eso-b 4eso-b 1bac-a 1bac-c)
			      (elsa 3eso-c 3eso-d 4eso-a 1bac-d 2bac-b)
			      (candela 4eso-a 4eso-b 2eso-d 1bac-c 1bac-d)
			      (manuel 4eso-a 4eso-b 4eso-c 1bac-a 1bac-b 1bac-d 2bac-a 2bac-b 2bac-c 2bac-d)
			      (carlota 3eso-a 1bac-a 2bac-a 2bac-b)
			      (mario 2eso-a 2eso-c 3eso-d 1bac-a 2bac-a)
			      (marina 1eso-a 1eso-c 3eso-d 2bac-c)
			      (jimena 2eso-a 1bac-a 1bac-b 2bac-b)
			      (olivia 4eso-c 1bac-a 1bac-c 2bac-c 2bac-d 2bac-e)
			      (javier 2eso-a 2eso-d 3eso-c 3eso-d 1bac-c 2bac-e)
			      (rocio 2bac-c 2bac-d 2bac-e 3eso-c)
			      (laura 3eso-b 1bac-b 2bac-c 2bac-d 2bac-e)
			      (sergio 1bac-c 1bac-d 2bac-c 2bac-d 2bac-e)
			      (valentina 3eso-a 4eso-c 1bac-a 1bac-c 2bac-a 2bac-c)
			      (paula 1bac-b 2bac-e 1eso-b 3eso-a)
			      (sofia 1eso-c 1eso-d 4eso-a 1bac-b 2bac-e)
			      (valeria 2eso-c 3eso-a 3eso-b 1bac-b 2bac-d)
			      (antonio 1eso-a 1eso-b 1eso-e 2eso-a 2eso-b 2eso-c)
			      (diego 1eso-a 1eso-b 3eso-a 3eso-b 3eso-c 3eso-d 4eso-b 4eso-c)
			      (nora 1eso-a 1eso-b 1eso-c 1eso-d 1eso-e)
			      (marcos 1eso-a 1eso-c 1eso-d 1eso-e)
			      (carlos 1eso-a 1eso-b 1eso-c 1eso-d 2eso-b 3eso-a 3eso-b 3eso-d)
			      (ariadna 2eso-b 3eso-c 3eso-d 4eso-a 4eso-b 4eso-c 2bac-a 2bac-b 2bac-c)
			      (vera 2bac-a 2bac-d 2bac-e 1bac-d)
			      (bruno 1eso-a 1eso-b 1eso-e 2eso-d 4eso-a 4eso-b 4eso-c)
			      (leonor 1eso-b 4eso-c 2bac-b)
			      (alba 4eso-a 4eso-b 2bac-a 2bac-b 2bac-d 2bac-e)
			      (ivan 2eso-d 3eso-a 3eso-c 4eso-a 2bac-b)
			      (julia 1eso-c 3eso-a 3eso-b 4eso-a 4eso-c 2bac-b)
			      (gonzalo 2bac-a 2bac-d 2bac-e 1bac-d)
			      (hector 4eso-c)
			      (dario 2eso-a 2eso-c 3eso-a 3eso-b 3eso-c 4eso-b)
			      (nerea 4eso-a 4eso-c)
			      (samuel 3eso-b 3eso-d 4eso-a 4eso-b 4eso-c)
			      (victor 2eso-a 2eso-d 3eso-c)
			      (blanca 1eso-a 1eso-b 1eso-c 1eso-d 1eso-e 2eso-a 3eso-a 3eso-c)
			      (ruben 1eso-b 1eso-c 1eso-d 1eso-e 2eso-b 2eso-c 3eso-d)
			      (gabriel 2eso-a 2eso-b 2eso-c 2eso-d 4eso-b)
			      (marta 1eso-a 1eso-b 1eso-c 1eso-d 1eso-e 2eso-b 2eso-c 3eso-a 3eso-b 3eso-c 3eso-d 1bac-a 1bac-b)
			      (emma 2eso-a 2eso-b 2eso-c 2eso-d 3eso-a 3eso-b 3eso-c 3eso-d)
			      (alberto 1eso-a 1eso-e 3eso-b 3eso-c 4eso-a 4eso-b)
			      (guillermo 3eso-b 3eso-d 4eso-c 1bac-c 2bac-c)
			      (jesus 2eso-b 2eso-c 2eso-d 1bac-b 1bac-c 1bac-d)
			      (luis 1eso-d 2eso-c 2eso-d 1bac-b 1bac-d)
			      (juan 4eso-a 1bac-b 2bac-b)
			      ))
      

Los datos anteriores son una simulación aleatoria sobre un hipotético centro docente español, y como dicen en las películas, cualquier parecido con la realidad es pura coincidencia.

Ahora debemos aprender a distinguir entre curso y grupo. Un curso es un nivel educativo y un grupo es un conjunto de alumnos que estudian un curso. La sintaxis de un grupo es curso-letra siendo letra una letra de la a a la z. Por ejemplo, 1bac (1º de bachillerato) es un curso, mientras que 1bac-a es un grupo de alumnos que estudian 1º de bachillerato. También 1bac-b es otro grupo de alumnos, distinto del anterior, que estudian también 1º de bacillerato.

Puede ordenar la lista anterior, para aclararse mejor, pero antes necesitamos unos conceptos previos. El orden de los cursos, de menor a mayor es el siguiente:

1eso, 2eso, 3eso, 4eso, 1bac, 2bac

Observe que no coincide con el orden alfabético que sería:

1bac, 1eso, 2bac, 2eso, 3eso, 4eso

A cada curso hay asociado un número, el 1 a 1eso, el 2 a 2eso, el 3 a 3eso, el 4 a 4eso, el 5 a 1bac y el 6 a 2bac, con lo que ordenar cursos es ordenar sus números asociados. En el programa hay definidas dos relaciones de orden, que son:

1. orden-de-grupos. Ésta relación de orden es lo que en matemáticas se llama orden léxico-gráfico, en concreto, los cursos se ordenan en base al criterio anterior y las letras en el orden alfabético habitual.
2. orden-alfabetico-simbolos. El orden alfabético habitual.

Podemos ordenar la lista cpp1 cn la función ordena-lista, que toma como argumento una lista de la forma:

l = ((o₁ v₁₁ v₁₂ ... v_1,n1) (o₂ v₂₁ v₂₂ ... v_2,n2) ... (o_m v_m1 v_m2 ... v_m,nm))

y admite dos argumentos opcionales que son: rop, relación de orden para las cabezas de las sublistas (por defecto es orden-alfabetico-simbolos) y ror, relación de orden para el resto de cada sublista (por defecto, también es orden-alfabetico-simbolos). En nuestro caso rop es correcto, pero ror no, así que introducimos:

stklos> (ordena-lista cpp1 :ror orden-de-grupos)
....
      

Como siempre, mejor utilizar for-each:

stklos> (for-each (lambda(x) (format #t "~a\n" x)) (ordena-lista cpp1 :ror orden-de-grupos))
(alba 4eso-a 4eso-b 2bac-a 2bac-b 2bac-d 2bac-e)
(alberto 1eso-a 1eso-e 3eso-b 3eso-c 4eso-a 4eso-b)
(alejandro 4eso-b 1bac-b 1bac-c 1bac-d 2bac-c 2bac-e)
(alvaro 2eso-a 2eso-d 3eso-c 1bac-a 1bac-c 2bac-a 2bac-c)
(antonio 1eso-a 1eso-b 1eso-e 2eso-a 2eso-b 2eso-c)
(ariadna 2eso-b 3eso-c 3eso-d 4eso-a 4eso-b 4eso-c 2bac-a 2bac-b 2bac-c)
(blanca 1eso-a 1eso-b 1eso-c 1eso-d 1eso-e 2eso-a 3eso-a 3eso-c)
(bruno 1eso-a 1eso-b 1eso-e 2eso-d 4eso-a 4eso-b 4eso-c)
(candela 2eso-d 4eso-a 4eso-b 1bac-c 1bac-d)
(carlos 1eso-a 1eso-b 1eso-c 1eso-d 2eso-b 3eso-a 3eso-b 3eso-d)
(carlota 3eso-a 1bac-a 2bac-a 2bac-b)
(dario 2eso-a 2eso-c 3eso-a 3eso-b 3eso-c 4eso-b)
(david 2eso-b 2eso-c 2eso-d 1bac-a 1bac-b 1bac-c 1bac-d 2bac-a)
(diego 1eso-a 1eso-b 3eso-a 3eso-b 3eso-c 3eso-d 4eso-b 4eso-c)
(elsa 3eso-c 3eso-d 4eso-a 1bac-d 2bac-b)
(emma 2eso-a 2eso-b 2eso-c 2eso-d 3eso-a 3eso-b 3eso-c 3eso-d)
(gabriel 2eso-a 2eso-b 2eso-c 2eso-d 4eso-b)
(gonzalo 1bac-d 2bac-a 2bac-d 2bac-e)
(guillermo 3eso-b 3eso-d 4eso-c 1bac-c 2bac-c)
(hector 4eso-c)
(hugo 2eso-b 3eso-b 4eso-a 1bac-b 2bac-a)
(ivan 2eso-d 3eso-a 3eso-c 4eso-a 2bac-b)
(javier 2eso-a 2eso-d 3eso-c 3eso-d 1bac-c 2bac-e)
(jesus 2eso-b 2eso-c 2eso-d 1bac-b 1bac-c 1bac-d)
(jimena 2eso-a 1bac-a 1bac-b 2bac-b)
(juan 4eso-a 1bac-b 2bac-b)
(julia 1eso-c 3eso-a 3eso-b 4eso-a 4eso-c 2bac-b)
(laura 3eso-b 1bac-b 2bac-c 2bac-d 2bac-e)
(leonor 1eso-b 4eso-c 2bac-b)
(lucas 4eso-a 1bac-b 1bac-c 1bac-d 2bac-a)
(luis 1eso-d 2eso-c 2eso-d 1bac-b 1bac-d)
(manuel 4eso-a 4eso-b 4eso-c 1bac-a 1bac-b 1bac-d 2bac-a 2bac-b 2bac-c 2bac-d)
(marcos 1eso-a 1eso-c 1eso-d 1eso-e)
(marina 1eso-a 1eso-c 3eso-d 2bac-c)
(mario 2eso-a 2eso-c 3eso-d 1bac-a 2bac-a)
(marta 1eso-a 1eso-b 1eso-c 1eso-d 1eso-e 2eso-b 2eso-c 3eso-a 3eso-b 3eso-c 3eso-d 1bac-a 1bac-b)
(mateo 3eso-a 3eso-b 4eso-b 1bac-a 1bac-c)
(nerea 4eso-a 4eso-c)
(nora 1eso-a 1eso-b 1eso-c 1eso-d 1eso-e)
(olivia 4eso-c 1bac-a 1bac-c 2bac-c 2bac-d 2bac-e)
(pablo 3eso-b 1bac-a 1bac-c 2bac-a)
(paula 1eso-b 3eso-a 1bac-b 2bac-e)
(rocio 3eso-c 2bac-c 2bac-d 2bac-e)
(ruben 1eso-b 1eso-c 1eso-d 1eso-e 2eso-b 2eso-c 3eso-d)
(samuel 3eso-b 3eso-d 4eso-a 4eso-b 4eso-c)
(sergio 1bac-c 1bac-d 2bac-c 2bac-d 2bac-e)
(sofia 1eso-c 1eso-d 4eso-a 1bac-b 2bac-e)
(valentina 3eso-a 4eso-c 1bac-a 1bac-c 2bac-a 2bac-c)
(valeria 2eso-c 3eso-a 3eso-b 1bac-b 2bac-d)
(vera 1bac-d 2bac-a 2bac-d 2bac-e)
(victor 2eso-a 2eso-d 3eso-c)
      

Espero que con este ejemplo haya quedado claro. Los profesores han sido ordenados por orden alfabético y los grupos por su relación de orden.

¿Cuántos profesores y grupos tenemos?. Buena pregunta, la respuesta a la primera es sencilla:

stklos> (length cpp1)
51
      

Es decir, 51 profesores. La respuesta a la segunda es más difícil. Primero, aislamos los cursos:

stklos> (a-conjunto (unionv (map resto cpp1)))
(2bac-a 2bac-d 2bac-e 1eso-b 1eso-c 1bac-a 2eso-a 3eso-a 1eso-a 1eso-e 3eso-c 4eso-b 3eso-b 3eso-d 4eso-c 2bac-c 2eso-b 1bac-c 1eso-d 2eso-c 2eso-d 1bac-d 4eso-a 1bac-b 2bac-b)
      

Mejor, lo ordenamos:

stklos> (sort (a-conjunto (unionv (map resto cpp1))) orden-de-grupos)
(1eso-a 1eso-b 1eso-c 1eso-d 1eso-e 2eso-a 2eso-b 2eso-c 2eso-d 3eso-a 3eso-b 3eso-c 3eso-d 4eso-a 4eso-b 4eso-c 1bac-a 1bac-b 1bac-c 1bac-d 2bac-a 2bac-b 2bac-c 2bac-d 2bac-e)
      

y finalmente

stklos> (length (a-conjunto (unionv (map resto cpp1))))
25
      

Es decir, 25 grupos. Para el horario de evaluaciones, la solución trivial es a hora por grupo, como tenemos 25, y si lo hacemos por la tarde en 5 horas, de 4 a 9, estaríamos cinco días. Teniendo en cuenta que el sábado y domingo no se trabaja, estaríamos liados con las reuniones una semana. Todo esto con la solución trivial. Veamos ahora qué puede aportar el algoritmo de coloreado.

stklos> (define grafo (construye-grafo cpp1))
;; grafo
stklos> grafo
....
      

Mejor no verlo. En fin:

stklos> (coloreado grafo)
((1 1bac-a) (2 3eso-c) (3 1bac-b) (4 3eso-d 2bac-d) (5 3eso-b 1bac-d) (6 3eso-a) (7 4eso-b 1eso-c) (8 2eso-b 2bac-e) (9 2eso-d) (10 4eso-a 2eso-a) (11 4eso-c 2eso-c) (12 2bac-c 1eso-b) (13 2bac-b 1bac-c 1eso-a) (14 2bac-a 1eso-e) (15 1eso-d))
      

No está mal, 15 sesiones. Vamos a ver si con el aleatorio ganamos algo. Introducimos:

stklos> (coloreado-aleatorio-numero grafo 100)
((1 1bac-a) (2 3eso-c) (3 1bac-b) (4 3eso-d 2bac-d) (5 3eso-b 1bac-d) (6 3eso-a) (7 4eso-b 1eso-d) (8 2eso-b 2bac-e) (9 2eso-d 1eso-c) (10 4eso-a 2eso-c) (11 4eso-c 2eso-a) (12 2bac-c 1eso-b) (13 2bac-b 1bac-c 1eso-e) (14 2bac-a 1eso-a))
      

Mejor, 14 sesiones. Hemos ganado una hora. Que trabaje un poco más:

stklos> (coloreado-aleatorio-numero grafo 1000)
((1 1bac-a) (2 3eso-c) (3 1bac-b) (4 3eso-d 2bac-d) (5 3eso-b 1bac-d) (6 3eso-a) (7 4eso-b 1eso-d) (8 2eso-b 2bac-e) (9 2eso-d 1eso-c) (10 4eso-a 2eso-a) (11 4eso-c 2eso-c) (12 2bac-c 1eso-b) (13 2bac-b 1eso-a 1bac-c) (14 2bac-a 1eso-e))
stklos> (coloreado-aleatorio-numero grafo 50000)
((1 1bac-a) (2 3eso-c) (3 1bac-b) (4 3eso-d 2bac-d) (5 3eso-b 1bac-d) (6 3eso-a) (7 4eso-b 1eso-d) (8 2eso-b 2bac-e) (9 2eso-d 1eso-c) (10 4eso-a 2eso-a) (11 4eso-c 2eso-c) (12 2bac-c 1eso-e) (13 1eso-b 2bac-a) (14 2bac-b 1bac-c 1eso-a))
      

Parece que no se puede. Lo dejamos así, nuestro horario quedaría como:

Día X
Hora	Cursos
1	1bac-a
2	3eso-c
3	1bac-b
4	3eso-d, 2bac-d
5	3eso-b, 1bac-d
6	3eso-a
7	4eso-b, 1eso-d
8	2eso-b, 2bac-e
9	2eso-d, 1eso-c
10	4eso-a, 2eso-a
11	4eso-c, 2eso-c
12	2bac-c, 1eso-e
13	1eso-b, 2bac-a
14	2bac-b, 1bac-c, 1eso-a

Veamos más utilidades. La lista de profesores por curso:

stklos> (lista-de-profesores-por-curso cpp1)
((2eso-b hugo david antonio carlos ariadna ruben gabriel marta emma jesus)
(3eso-b hugo pablo mateo laura valeri
....
      

No está mal. Más claro:

stklos> (for-each (lambda(x) (format #t "~a\n" x)) (lista-de-profesores-por-curso cpp1))
(2eso-b hugo david antonio carlos ariadna ruben gabriel marta emma jesus)
(3eso-b hugo pablo mateo laura valeria diego carlos julia dario samuel marta emma alberto guillermo)
(4eso-a hugo lucas elsa candela manuel sofia ariadna bruno alba ivan julia nerea samuel alberto juan)
(1bac-b hugo alejandro david lucas manuel jimena laura paula sofia valeria marta jesus luis juan)
....
      

Tampoco está mal, pero desordenado. Finalmente:

stklos> (for-each (lambda(x) (format #t "~a\n" x)) (ordena-lista (lista-de-profesores-por-curso cpp1) :rop orden-de-grupos))
(1eso-a alberto antonio blanca bruno carlos diego marcos marina marta nora)
(1eso-b antonio blanca bruno carlos diego leonor marta nora paula ruben)
(1eso-c blanca carlos julia marcos marina marta nora ruben sofia)
(1eso-d blanca carlos luis marcos marta nora ruben sofia)
(1eso-e alberto antonio blanca bruno marcos marta nora ruben)
(2eso-a alvaro antonio blanca dario emma gabriel javier jimena mario victor)
(2eso-b antonio ariadna carlos david emma gabriel hugo jesus marta ruben)
(2eso-c antonio dario david emma gabriel jesus luis mario marta ruben valeria)
(2eso-d alvaro bruno candela david emma gabriel ivan javier jesus luis victor)
(3eso-a blanca carlos carlota dario diego emma ivan julia marta mateo paula valentina valeria)
(3eso-b alberto carlos dario diego emma guillermo hugo julia laura marta mateo pablo samuel valeria)
(3eso-c alberto alvaro ariadna blanca dario diego elsa emma ivan javier marta rocio victor)
(3eso-d ariadna carlos diego elsa emma guillermo javier marina mario marta ruben samuel)
(4eso-a alba alberto ariadna bruno candela elsa hugo ivan juan julia lucas manuel nerea samuel sofia)
(4eso-b alba alberto alejandro ariadna bruno candela dario diego gabriel manuel mateo samuel)
(4eso-c ariadna bruno diego guillermo hector julia leonor manuel nerea olivia samuel valentina)
(1bac-a alvaro carlota david jimena manuel mario marta mateo olivia pablo valentina)
(1bac-b alejandro david hugo jesus jimena juan laura lucas luis manuel marta paula sofia valeria)
(1bac-c alejandro alvaro candela david guillermo javier jesus lucas mateo olivia pablo sergio valentina)
(1bac-d alejandro candela david elsa gonzalo jesus lucas luis manuel sergio vera)
(2bac-a alba alvaro ariadna carlota david gonzalo hugo lucas manuel mario pablo valentina vera)
(2bac-b alba ariadna carlota elsa ivan jimena juan julia leonor manuel)
(2bac-c alejandro alvaro ariadna guillermo laura manuel marina olivia rocio sergio valentina)
(2bac-d alba gonzalo laura manuel olivia rocio sergio valeria vera)
(2bac-e alba alejandro gonzalo javier laura olivia paula rocio sergio sofia vera)
      

Perfecto. Finalmente, para comprobar que el horario es correcto.

stklos> (profesores-comunes cpp1)
((1bac-a 1bac-b david jimena manuel marta) (1bac-a 1bac-c alvaro david mateo
olivia pablo valentina) (1bac-a 1ba
....
      

No se ve bien. Con for-each:

stklos> (for-each (lambda(x) (format #t "~a\n" x)) (profesores-comunes cpp1))
(1bac-a 1bac-b david jimena manuel marta)
(1bac-a 1bac-c alvaro david mateo olivia pablo valentina)
...
      

Ordenamos para que quede bien:

stklos> (for-each (lambda(x) (format #t "~a\n" x)) (profesores-comunes cpp1 :rog orden-de-grupos))
(1eso-a 1eso-b antonio blanca bruno carlos diego marta nora)
(1eso-a 1eso-c blanca carlos marcos marina marta nora)
(1eso-a 1eso-d blanca carlos marcos marta nora)
(1eso-a 1eso-e alberto antonio blanca bruno marcos marta nora)
(1eso-a 2eso-a antonio blanca)
(1eso-a 2eso-b antonio carlos marta)
(1eso-a 2eso-c antonio marta)
(1eso-a 2eso-d bruno)
(1eso-a 3eso-a blanca carlos diego marta)
(1eso-a 3eso-b alberto carlos diego marta)
(1eso-a 3eso-c alberto blanca diego marta)
(1eso-a 3eso-d carlos diego marina marta)
(1eso-a 4eso-a alberto bruno)
(1eso-a 4eso-b alberto bruno diego)
(1eso-a 4eso-c bruno diego)
(1eso-a 1bac-a marta)
(1eso-a 1bac-b marta)
(1eso-a 1bac-c)
(1eso-a 1bac-d)
(1eso-a 2bac-a)
(1eso-a 2bac-b)
(1eso-a 2bac-c marina)
(1eso-a 2bac-d)
(1eso-a 2bac-e)
(1eso-b 1eso-c blanca carlos marta nora ruben)
(1eso-b 1eso-d blanca carlos marta nora ruben)
(1eso-b 1eso-e antonio blanca bruno marta nora ruben)
(1eso-b 2eso-a antonio blanca)
(1eso-b 2eso-b antonio carlos marta ruben)
(1eso-b 2eso-c antonio marta ruben)
(1eso-b 2eso-d bruno)
(1eso-b 3eso-a blanca carlos diego marta paula)
(1eso-b 3eso-b carlos diego marta)
(1eso-b 3eso-c blanca diego marta)
(1eso-b 3eso-d carlos diego marta ruben)
(1eso-b 4eso-a bruno)
(1eso-b 4eso-b bruno diego)
(1eso-b 4eso-c bruno diego leonor)
(1eso-b 1bac-a marta)
(1eso-b 1bac-b marta paula)
(1eso-b 1bac-c)
(1eso-b 1bac-d)
(1eso-b 2bac-a)
(1eso-b 2bac-b leonor)
(1eso-b 2bac-c)
(1eso-b 2bac-d)
(1eso-b 2bac-e paula)
(1eso-c 1eso-d blanca carlos marcos marta nora ruben sofia)
(1eso-c 1eso-e blanca marcos marta nora ruben)
(1eso-c 2eso-a blanca)
(1eso-c 2eso-b carlos marta ruben)
(1eso-c 2eso-c marta ruben)
(1eso-c 2eso-d)
(1eso-c 3eso-a blanca carlos julia marta)
(1eso-c 3eso-b carlos julia marta)
(1eso-c 3eso-c blanca marta)
(1eso-c 3eso-d carlos marina marta ruben)
(1eso-c 4eso-a julia sofia)
(1eso-c 4eso-b)
(1eso-c 4eso-c julia)
(1eso-c 1bac-a marta)
(1eso-c 1bac-b marta sofia)
(1eso-c 1bac-c)
(1eso-c 1bac-d)
(1eso-c 2bac-a)
(1eso-c 2bac-b julia)
(1eso-c 2bac-c marina)
(1eso-c 2bac-d)
(1eso-c 2bac-e sofia)
(1eso-d 1eso-e blanca marcos marta nora ruben)
(1eso-d 2eso-a blanca)
(1eso-d 2eso-b carlos marta ruben)
(1eso-d 2eso-c luis marta ruben)
(1eso-d 2eso-d luis)
(1eso-d 3eso-a blanca carlos marta)
(1eso-d 3eso-b carlos marta)
(1eso-d 3eso-c blanca marta)
(1eso-d 3eso-d carlos marta ruben)
(1eso-d 4eso-a sofia)
(1eso-d 4eso-b)
(1eso-d 4eso-c)
(1eso-d 1bac-a marta)
(1eso-d 1bac-b luis marta sofia)
(1eso-d 1bac-c)
(1eso-d 1bac-d luis)
(1eso-d 2bac-a)
(1eso-d 2bac-b)
(1eso-d 2bac-c)
(1eso-d 2bac-d)
(1eso-d 2bac-e sofia)
(1eso-e 2eso-a antonio blanca)
(1eso-e 2eso-b antonio marta ruben)
(1eso-e 2eso-c antonio marta ruben)
(1eso-e 2eso-d bruno)
(1eso-e 3eso-a blanca marta)
(1eso-e 3eso-b alberto marta)
(1eso-e 3eso-c alberto blanca marta)
(1eso-e 3eso-d marta ruben)
(1eso-e 4eso-a alberto bruno)
(1eso-e 4eso-b alberto bruno)
(1eso-e 4eso-c bruno)
(1eso-e 1bac-a marta)
(1eso-e 1bac-b marta)
(1eso-e 1bac-c)
(1eso-e 1bac-d)
(1eso-e 2bac-a)
(1eso-e 2bac-b)
(1eso-e 2bac-c)
(1eso-e 2bac-d)
(1eso-e 2bac-e)
(2eso-a 2eso-b antonio emma gabriel)
(2eso-a 2eso-c antonio dario emma gabriel mario)
(2eso-a 2eso-d alvaro emma gabriel javier victor)
(2eso-a 3eso-a blanca dario emma)
(2eso-a 3eso-b dario emma)
(2eso-a 3eso-c alvaro blanca dario emma javier victor)
(2eso-a 3eso-d emma javier mario)
(2eso-a 4eso-a)
(2eso-a 4eso-b dario gabriel)
(2eso-a 4eso-c)
(2eso-a 1bac-a alvaro jimena mario)
(2eso-a 1bac-b jimena)
(2eso-a 1bac-c alvaro javier)
(2eso-a 1bac-d)
(2eso-a 2bac-a alvaro mario)
(2eso-a 2bac-b jimena)
(2eso-a 2bac-c alvaro)
(2eso-a 2bac-d)
(2eso-a 2bac-e javier)
(2eso-b 2eso-c antonio david emma gabriel jesus marta ruben)
(2eso-b 2eso-d david emma gabriel jesus)
(2eso-b 3eso-a carlos emma marta)
(2eso-b 3eso-b carlos emma hugo marta)
(2eso-b 3eso-c ariadna emma marta)
(2eso-b 3eso-d ariadna carlos emma marta ruben)
(2eso-b 4eso-a ariadna hugo)
(2eso-b 4eso-b ariadna gabriel)
(2eso-b 4eso-c ariadna)
(2eso-b 1bac-a david marta)
(2eso-b 1bac-b david hugo jesus marta)
(2eso-b 1bac-c david jesus)
(2eso-b 1bac-d david jesus)
(2eso-b 2bac-a ariadna david hugo)
(2eso-b 2bac-b ariadna)
(2eso-b 2bac-c ariadna)
(2eso-b 2bac-d)
(2eso-b 2bac-e)
(2eso-c 2eso-d david emma gabriel jesus luis)
(2eso-c 3eso-a dario emma marta valeria)
(2eso-c 3eso-b dario emma marta valeria)
(2eso-c 3eso-c dario emma marta)
(2eso-c 3eso-d emma mario marta ruben)
(2eso-c 4eso-a)
(2eso-c 4eso-b dario gabriel)
(2eso-c 4eso-c)
(2eso-c 1bac-a david mario marta)
(2eso-c 1bac-b david jesus luis marta valeria)
(2eso-c 1bac-c david jesus)
(2eso-c 1bac-d david jesus luis)
(2eso-c 2bac-a david mario)
(2eso-c 2bac-b)
(2eso-c 2bac-c)
(2eso-c 2bac-d valeria)
(2eso-c 2bac-e)
(2eso-d 3eso-a emma ivan)
(2eso-d 3eso-b emma)
(2eso-d 3eso-c alvaro emma ivan javier victor)
(2eso-d 3eso-d emma javier)
(2eso-d 4eso-a bruno candela ivan)
(2eso-d 4eso-b bruno candela gabriel)
(2eso-d 4eso-c bruno)
(2eso-d 1bac-a alvaro david)
(2eso-d 1bac-b david jesus luis)
(2eso-d 1bac-c alvaro candela david javier jesus)
(2eso-d 1bac-d candela david jesus luis)
(2eso-d 2bac-a alvaro david)
(2eso-d 2bac-b ivan)
(2eso-d 2bac-c alvaro)
(2eso-d 2bac-d)
(2eso-d 2bac-e javier)
(3eso-a 3eso-b carlos dario diego emma julia marta mateo valeria)
(3eso-a 3eso-c blanca dario diego emma ivan marta)
(3eso-a 3eso-d carlos diego emma marta)
(3eso-a 4eso-a ivan julia)
(3eso-a 4eso-b dario diego mateo)
(3eso-a 4eso-c diego julia valentina)
(3eso-a 1bac-a carlota marta mateo valentina)
(3eso-a 1bac-b marta paula valeria)
(3eso-a 1bac-c mateo valentina)
(3eso-a 1bac-d)
(3eso-a 2bac-a carlota valentina)
(3eso-a 2bac-b carlota ivan julia)
(3eso-a 2bac-c valentina)
(3eso-a 2bac-d valeria)
(3eso-a 2bac-e paula)
(3eso-b 3eso-c alberto dario diego emma marta)
(3eso-b 3eso-d carlos diego emma guillermo marta samuel)
(3eso-b 4eso-a alberto hugo julia samuel)
(3eso-b 4eso-b alberto dario diego mateo samuel)
(3eso-b 4eso-c diego guillermo julia samuel)
(3eso-b 1bac-a marta mateo pablo)
(3eso-b 1bac-b hugo laura marta valeria)
(3eso-b 1bac-c guillermo mateo pablo)
(3eso-b 1bac-d)
(3eso-b 2bac-a hugo pablo)
(3eso-b 2bac-b julia)
(3eso-b 2bac-c guillermo laura)
(3eso-b 2bac-d laura valeria)
(3eso-b 2bac-e laura)
(3eso-c 3eso-d ariadna diego elsa emma javier marta)
(3eso-c 4eso-a alberto ariadna elsa ivan)
(3eso-c 4eso-b alberto ariadna dario diego)
(3eso-c 4eso-c ariadna diego)
(3eso-c 1bac-a alvaro marta)
(3eso-c 1bac-b marta)
(3eso-c 1bac-c alvaro javier)
(3eso-c 1bac-d elsa)
(3eso-c 2bac-a alvaro ariadna)
(3eso-c 2bac-b ariadna elsa ivan)
(3eso-c 2bac-c alvaro ariadna rocio)
(3eso-c 2bac-d rocio)
(3eso-c 2bac-e javier rocio)
(3eso-d 4eso-a ariadna elsa samuel)
(3eso-d 4eso-b ariadna diego samuel)
(3eso-d 4eso-c ariadna diego guillermo samuel)
(3eso-d 1bac-a mario marta)
(3eso-d 1bac-b marta)
(3eso-d 1bac-c guillermo javier)
(3eso-d 1bac-d elsa)
(3eso-d 2bac-a ariadna mario)
(3eso-d 2bac-b ariadna elsa)
(3eso-d 2bac-c ariadna guillermo marina)
(3eso-d 2bac-d)
(3eso-d 2bac-e javier)
(4eso-a 4eso-b alba alberto ariadna bruno candela manuel samuel)
(4eso-a 4eso-c ariadna bruno julia manuel nerea samuel)
(4eso-a 1bac-a manuel)
(4eso-a 1bac-b hugo juan lucas manuel sofia)
(4eso-a 1bac-c candela lucas)
(4eso-a 1bac-d candela elsa lucas manuel)
(4eso-a 2bac-a alba ariadna hugo lucas manuel)
(4eso-a 2bac-b alba ariadna elsa ivan juan julia manuel)
(4eso-a 2bac-c ariadna manuel)
(4eso-a 2bac-d alba manuel)
(4eso-a 2bac-e alba sofia)
(4eso-b 4eso-c ariadna bruno diego manuel samuel)
(4eso-b 1bac-a manuel mateo)
(4eso-b 1bac-b alejandro manuel)
(4eso-b 1bac-c alejandro candela mateo)
(4eso-b 1bac-d alejandro candela manuel)
(4eso-b 2bac-a alba ariadna manuel)
(4eso-b 2bac-b alba ariadna manuel)
(4eso-b 2bac-c alejandro ariadna manuel)
(4eso-b 2bac-d alba manuel)
(4eso-b 2bac-e alba alejandro)
(4eso-c 1bac-a manuel olivia valentina)
(4eso-c 1bac-b manuel)
(4eso-c 1bac-c guillermo olivia valentina)
(4eso-c 1bac-d manuel)
(4eso-c 2bac-a ariadna manuel valentina)
(4eso-c 2bac-b ariadna julia leonor manuel)
(4eso-c 2bac-c ariadna guillermo manuel olivia valentina)
(4eso-c 2bac-d manuel olivia)
(4eso-c 2bac-e olivia)
(1bac-a 1bac-b david jimena manuel marta)
(1bac-a 1bac-c alvaro david mateo olivia pablo valentina)
(1bac-a 1bac-d david manuel)
(1bac-a 2bac-a alvaro carlota david manuel mario pablo valentina)
(1bac-a 2bac-b carlota jimena manuel)
(1bac-a 2bac-c alvaro manuel olivia valentina)
(1bac-a 2bac-d manuel olivia)
(1bac-a 2bac-e olivia)
(1bac-b 1bac-c alejandro david jesus lucas)
(1bac-b 1bac-d alejandro david jesus lucas luis manuel)
(1bac-b 2bac-a david hugo lucas manuel)
(1bac-b 2bac-b jimena juan manuel)
(1bac-b 2bac-c alejandro laura manuel)
(1bac-b 2bac-d laura manuel valeria)
(1bac-b 2bac-e alejandro laura paula sofia)
(1bac-c 1bac-d alejandro candela david jesus lucas sergio)
(1bac-c 2bac-a alvaro david lucas pablo valentina)
(1bac-c 2bac-b)
(1bac-c 2bac-c alejandro alvaro guillermo olivia sergio valentina)
(1bac-c 2bac-d olivia sergio)
(1bac-c 2bac-e alejandro javier olivia sergio)
(1bac-d 2bac-a david gonzalo lucas manuel vera)
(1bac-d 2bac-b elsa manuel)
(1bac-d 2bac-c alejandro manuel sergio)
(1bac-d 2bac-d gonzalo manuel sergio vera)
(1bac-d 2bac-e alejandro gonzalo sergio vera)
(2bac-a 2bac-b alba ariadna carlota manuel)
(2bac-a 2bac-c alvaro ariadna manuel valentina)
(2bac-a 2bac-d alba gonzalo manuel vera)
(2bac-a 2bac-e alba gonzalo vera)
(2bac-b 2bac-c ariadna manuel)
(2bac-b 2bac-d alba manuel)
(2bac-b 2bac-e alba)
(2bac-c 2bac-d laura manuel olivia rocio sergio)
(2bac-c 2bac-e alejandro laura olivia rocio sergio)
(2bac-d 2bac-e alba gonzalo laura olivia rocio sergio vera)
      

Veamos finalmente una utilidad más incluida en el programa y relacionada con éste asunto. Siga el siguiente orden:

1. Obtenga una solución y asígnela:

   stklos> (define p (construye-grafo cpp1))
   ;; p
   stklos> (define q (coloreado-aleatorio-numero p 100))
   ;; q
   stklos> q
   ((1 1bac-a) (2 3eso-c) (3 1bac-b) (4 3eso-d 2bac-d) (5 3eso-b 1bac-d) (6 3eso-a) (7 4eso-b 1eso-d) (8 2eso-b 2bac-e) (9 2eso-d 1eso-c) (10 4eso-a 2eso-a) (11 4eso-c 2eso-c) (12 2bac-c 1eso-e) (13 1eso-b 2bac-a) (14 2bac-b 1bac-c 1eso-a))
   	  

2. Decida en cuántas sesiones va a celebrar las reuniones. Supongamos que sean 5. Decida también el archivo html de salida. Supongamos que es solucion1.html.

3. Introduzca:

   stklos> (tabla-sesiones-profesores cpp1 q 5 :salida "solucion1.html")
   	  

   Esto produce el archivo solucion1.html. Ábralo con el navegador. Una X en una celda obviamente quiere decir que el profesor relacionado tiene que asistir a esa reunión. Lo que yo he obtenido es (pinche en el siguiente enlace):

   solucion1.html

Si es Vd. un buen profesional, puede mejorar el resultado, pues hay profesores que tienen huecos entre reuniones y se trata de reducirlos. Veamos un par de jugadas que mejoran el horario.

Cambiemos la columna 5 por la 3, es decir, en la 3 ponemos 3eso-b,1bac-d y en la 5 ponemos 1bac-b. Mentalmente, permute las columnas 5 y 3. En fin, a alberto le hemos quitado dos huecos, a alejandro le da igual. Para formalizar la idea, escribimos la gente afectada (ganadores o perdedores), y los que ni ganan ni pierden no los tenemos en cuenta:

alberto	2 → 0 (+2)
dario	2 → 0 (+2)
diego	1 → 0 (+1)
elsa	1 → 0 (+1)
emma	1 → 0 (+1)
jimena	1 → 3 (-2)
mateo	3 → 1 (+2)
pablo	3 → 1 (+2)

es decir, alberto tenía 2 huecos y ahora, con el cambio, no tiene ninguno, luego lo hemos favorecido y le apuntamos un +2. Observe que todo el mundo ha salido beneficiado salvo la pobre jimena a la que le hemos metido un gol. En fin, el resultado neto es que los positivos suman 11 y los negativos 2, en total, 11 - 2 = 9, luego la jugada es buena, ya que ha mejorado a bastantes profesores.

Otra buena jugada es cambiar las columnas 13 y 14. Observen como todos ganan salvo mario y ruben.

Seguramente habrá otras jugadas buenas y casi seguro que mejores que las que yo he expuesto, en fin, eso depende de la habilidad de cada uno.

Número cromático

El programa que hemos explicado en ésta página colorea cualquier grafo, siempre que se sigan las las condiciones que se exigen. En el último ejemplo, gracias al coloreado aleatorio hemos resuelto el problema de las reuniones en 14 sesiones, y claro, la pregunta que cualquiera se hace es obvia: ¿se podría hacer en menos?.

En fin, la pregunta no está mal, pero la respuesta no es sencilla, y lo único que podemos decir es que es posible, y para ello conviene saber qué es el número cromático de un grafo. Se define como el número mínimo de colores necesario para colorearlo. Si éste número es δ, entonces, por definición, el grafo se puede colorear con δ colores, pero no con δ-1. Así pues, el conocimiento de éste número responde a la pregunta anterior. Si sabemos que el grafo de las reuniones es tal que su número cromático es, por ejemplo, 10, entonces, todas las reuniones se harían en 10 horas, y no se podrían hacer en menos. Desafortunadamente, no hay algoritmo actual (salvo el de la fuerza bruta) que permita el cálculo de δ. Más aún, si existiera tal algoritmo, con pequeños cambios se adaptaría a otros problemas, que, repito, actualmente no tienen solución óptima.

El algoritmo proporcionado en éste programa es uno de los que hay para encontrar una solución. Algo se mejora con el de coloreado aleatorio, que algo de fuerza bruta sí que tiene, pero está muy lejos de ser la solución óptima.

Contacto

Si desea hacer algún comentario, utilice la siguiente dirección de correo:

Pedro González Ruiz
Fecha de creación: 5 de febrero de 2019
Fecha de la última modificación: 17 de febrero de 2019

ir a la página principal