¿Alguna vez te has desesperado en un cruce de semáforos, sospechando que el tuyo tarda demasiado en ponerse verde? Con un puñado de matemáticas, un chorretón de dibujos y una pizca de color, podrás saber si estás en lo cierto… o si no te queda otra que esperar.

Un ejemplo fácil

Hay cruces sin mucho misterio. Por ejemplo, si son dos calles de sentido único: Primero pasan unos y luego otros. Si ambos movimientos son igual de importantes, sus luces verdes durarán lo mismo; pongamos que un minuto cada una, para que las cuentas sean redondas.

Los unos tienen un primer minuto de luz verde y un segundo minuto de luz roja. Los otros, al revés. Y así no habrá choques. El ciclo de luces durará dos minutos; si tienes mala suerte y justo cuando llegas se te pone la luz roja, tendrás que esperar un minuto [gracias a @rufreber por su observación].

Otro ejemplo y una primera técnica

La cosa se complica un poco si tienes una calle de doble sentido cruzándose con otra de sentido único. Más aún si hay giros de una calle a la otra, sobre todo si para girar tienes que atravesar por completo otro carril.

Para pensar cómo resolver el problema, puedes representar los movimientos en un esquema y unirlos cuando son incompatibles (en matemáticas esto es un grafo). [Observación: Para que no resulte demasiado complicado, con este grafo estamos permitiendo algunos movimientos simultáneos hacia una misma dirección, como A->D y C->D. Gracias a MrQeu por apuntar que esto no estaba tan claro.]

Ahora solo tienes que decidir en qué minuto tendrá luz verde cada movimiento, asegurándote de que movimientos incompatibles suceden en minutos distintos (en matemáticas se llama coloración del grafo). En nuestro ejemplo puedes conseguirlo usando 3 minutos.

Y con esta técnica es imposible hacerlo en menos tiempo (en matemáticas se dice que el número cromático de ese grafo es 3). Pero hay otra técnica para hacerte esperar menos.

La mejor solución posible

El truco está en darse cuenta de que el ciclo de semáforos es eso, un ciclo, y puedes pegar el final de cada línea de tiempo con su inicio. Así es posible conseguir una duración de 2.5 minutos para nuestro ejemplo.

Y ese número es lo mejor que se puede conseguir para ese cruce (en matemáticas se le llama número cromático circular de ese grafo).

Ya sabes: La próxima vez que te toque una luz roja, en lugar de esas cosas que solemos hacer en los semáforos, mejor cuéntales a tus acompañantes cómo las matemáticas ayudan a esperar menos 😉

Nota 1: Este blog se presenta a los Premios 20Blogs, por estos motivos. Si te gusta, puedes contribuir con tu voto en

http://bit.ly/cifrasyteclas20minutos

(¡ojo!, los votos no son las estrellitas; si tienes dudas puedes leer esto). ¡Gracias!

Nota 2: Esta entrada ha llegado a portada en Menéame. ¡Gracias!
Nota 3: Esta entrada ha resultado ganadora de la Edición 6.1 del Carnaval de Matemáticas, cuyo blog anfitrión es Tito Eliatron Dixit.

Recuerda que puedes seguirnos en Twitter, en Facebook, en YouTube y en Google +.

Para saber más:

Para incluir la luz ámbar bastaría con que ésta le robara un trocito a la luz verde.

Hay un motivo para la poca diferencia entre la primera solución y la segunda. Resulta hay muy poca diferencia entre el número cromático circular (chi_c) y el número cromático usual (chi). Más precisamente, [chi-1<chi_c leq chi] Así que lo más que puedes ganar usando la solución más afinada será lo que dure una luz verde, en nuestro caso un minuto.

Si quieres, puedes probar a dibujar el grafo de tu cruce preferido y usar el software matemático libre Sage para calcular su número cromático, es decir, la primera solución. Aquí tienes un ejemplo del código, en el que solo tienes que cambiar a tu gusto las conexiones de cada vértice.

Calcular el número crómatico circular de un grafo es, igual que sucede para el número cromático habitual, un problema NP-duro. En general, eso suele suponer que es un problema computacionalmente costoso, pero en este caso hay algunos métodos para calcularlo sin perder la dignidad. Como ejemplo, puedes leer el artículo Circular coloring of graphs via linear programming and tabu search. Para el coloreado usual puedes echar un vistazo a Network Resources for Coloring a Graph (sugerido por mi amigo @Zifra, ¡muchas gracias!)

Un coloreado circular de un grafo consiste en:

• Asignar a cada vértice (en nuestro caso, cada movimiento) un arco de circunferencia con longitud 1 (en nuestro caso, el minuto que ese movimiento va a tener luz verde).
• Hacerlo de forma que dos vértices unidos por una arista (en nuestro caso, dos movimientos en conflicto) siempre tengan arcos que no se solapan (en nuestro caso, luces verdes que no se solapan).
• Entonces, el tamaño de ese coloreado circular es la longitud total de la circunferencia (en nuestro caso, la longitud del ciclo de luces verdes visto como un ciclo circular).

La figura muestra cómo, pegando los extremos inicial y final de la línea de tiempo anterior, obtenemos un coloreado circular en el que cada vértice (movimiento) es el inicio de un arco (de luz verde) con longitud 1.

Por supuesto, el problema se puede complicar bastante más. Por ejemplo, puede haber movimientos más importantes que otros, para los que nos interese que la luz verde dure más tiempo. Esto se correspondería con poner pesos en las aristas del grafo y es un caso que también se estudia al estudiar el número cromático circular. Puedes encontrar más información en Circular chromatic number: a survey y en Recent Developments in Circular Colouring of Graphs.

Y la cosa se complica aún más cuando quieres sincronizar unos cruces con otros. Quizá te interesen los artículos Planificación de Ciclos en Semáforos con PSO: Casos de Estudio sobre Málaga y Sevilla y/o Validación Inteligente para la Sincronización de Semáforos Basada en Feature Models.

Por último, si tienes espíritu ingenieril y quieres cacharrear con este problema, puedes consultar estos proyectos sobre cruces de semáforos del INTEF.

Imágenes

La imagen del Boom es de raphaeljeanneret, en openclipart. La imagen con muchos semáforos es de @Doug88888, en Flickr. El resto de imágenes son de creación propia. Todas tienen licencia Creative Commons.