Teorema de coloración de carreteras
En la teoría de grafos, el teorema de coloración de carreteras , conocido anteriormente como la conjetura de coloración de carreteras , trata de instrucciones sincronizadas . El problema consiste en saber si mediante el uso de tales instrucciones se puede alcanzar o ubicar un objeto o destino desde cualquier otro punto dentro de una red (que podría ser una representación de las calles de una ciudad o un laberinto ). [1] En el mundo real, este fenómeno sería como si llamaras a un amigo para preguntarle cómo llegar a su casa y él te dio un conjunto de direcciones que funcionaron sin importar desde dónde partiste. Este teorema también tiene implicaciones en la dinámica simbólica .
El teorema fue conjeturado por primera vez por Roy Adler y Benjamin Weiss ( 1970 ). Fue probado por Avraham Trahtman ( 2009 ).
La imagen de la derecha muestra un gráfico dirigido en ocho vértices en los que cada vértice tiene un grado de salida 2. (Cada vértice en este caso también tiene un grado de entrada 2, pero eso no es necesario para que exista una coloración sincronizada). Los bordes de este gráfico se han coloreado en rojo y azul para crear un color sincronizado.
Por ejemplo, considere el vértice marcado en amarillo. No importa en qué parte del gráfico comience, si recorre los nueve bordes en la caminata "azul-rojo-rojo—azul-rojo-rojo—azul-rojo-rojo", terminará en el vértice amarillo. Del mismo modo, si recorre los nueve bordes en la caminata "azul-azul-rojo-azul-azul-rojo-azul-azul-rojo", siempre terminará en el vértice marcado en verde, sin importar dónde comenzó.
El teorema de coloración de carreteras establece que para una determinada categoría de grafos dirigidos, siempre es posible crear tal coloración.
Sea G un grafo dirigido finito, fuertemente conexo , donde todos los vértices tienen el mismo grado exterior k . Sea A el alfabeto que contiene las letras 1, ..., k . Una coloración sincronizada (también conocida como coloración colapsable ) en G es un etiquetado de los bordes en G con letras de A tal que (1) cada vértice tiene exactamente un borde saliente con una etiqueta dada y (2) para cada vértice v en el gráfico, existe una palabra w sobre A tal que todos los caminos en G correspondiente a w termina en v .
