Teorema del coloreo de carreteras

En teoría de grafos el teorema de coloreo de carreteras, teorema del camino coloreado o, conocido antiguamente como la conjetura del coloreo de carreteras, es un problema de coloreo de grafos planos. El planteamiento inicial, en términos intuitivos, consiste en que dada una red (grafo que representa ya sea una ciudad o laberinto) con determinadas condiciones, y dada una posición en el mismo, buscar si existe, y cuál es, una serie de instrucciones que independientemente del posicionamiento inicial, permitan llegar a la posición requerida.​ Usualmente, este problema se plantea en términos coloquiales como:

Un grafo dirigido con un coloreo que siempre que se sigan las instrucciones "azul-rojo-rojo-azul-rojo-rojo-azul-rojo-rojo", respetando la dirección de las flechas, independientemente del nodo inicial, conduce al nodo amarillo. Análogamente, las instrucciones "azul-azul-rojo-azul-azul-rojo-azul-azul-rojo" siempre conducen al nodo verde.

Supongamos que alguien visita una ciudad que no conoce, con la peculiaridad de que dicho lugar no contiene ninguna clase de señal indicativa. Luego de haber vagado un par de horas, el visitante le pide ayuda a alguien para llegar a determinado lugar, contándole que no sabe dónde está. ¿Existe alguna serie de instrucciones que se le puedan dar al turista para que, independientemente de dónde se encuentre, pueda llegar a su destino?

Este teorema fue conjeturado por primera vez por Roy Adler, Wayne Goodwyn y Benjamin Weiss en 1970​ y replanteado en 1977,​ siendo probado 37 años después, en 2007 por el israelí de origen ruso Avraham Trahtman.​​ Sus aplicaciones van desde la cartografía hasta el simbolismo dinámico y la teoría de automatización.​

Nociones previas

La notación usada a continuación es la dada por Trahtman en su demostración original. Las definiciones y teoremas han sido adaptados de aquí y aquí.

Grafos AGW

En un dígrafo, llamamos al conjunto de todas las aristas que salen de un vértice un manojo (bunch, en inglés) si cada una de dichas aristas llega a un solo vértice.

Un dígrafo $D$ se dice externo-regular o con grado externo uniforme si existe un entero $\Delta$ tal que el grado exterior de todo vértice (número de aristas que parten de él) tiene como valor $\Delta$.

Cabe mencionar que análogamente, existe la noción de dígrafo interno-regular y que, dado un grafo externo-regular, esto no implica que también sea interno-regular o viceversa.

Un dígrafo $D$ es periódico si es posible encontrar una partición en el conjunto de vértices, $V(D)$, de $k\geq 2$ subconjuntos, $V_{1},V_{2},\ldots ,V_{k},V_{k+i}=1$ tal que si $(u,v)$ es una arista, entonces $u\in V_{i},\,v\in V_{i+1}$ para algún $i$ en $1\leq i\leq k$. Tal partición de $V(D)$ es llamada una $k$-partición cíclica de $D$.

Por tanto, $D$ es periódico si existe una $k$-partición cíclica de $V(D)$ para algún entero $k\geq 2$. Si $D$ no es periódico, se dice que $D$ es aperiódico. Además, un grafo fuertemente conexo aperiódico y externo-regular, es usualmente llamado un grafo AGW.

Coloreo sincronizado

Dado un dígrafo $D$, un coloreado $c$ del grafo se dice propio si cualesquiera dos aristas incidentes al mismo vértice de $D$ tienen asignado distinto color. Para un dígrafo fuertemente conexo $D$ con grado exterior regular $\Delta$ un $\Delta$-coloreo propio $c$ se dice sincronizado si para cualquier vértice $v$ de $D$, existe una secuencia $s_{v}$ de colores tal que para todo vértice $u$ de $D$, el camino dirigido con vértice inicial $u$ determinado por $s_{v}$ tiene como vértice final $v$. En este caso, la secuencias $s_{v}$ se dice una secuencia sincronizada del vértice $v$.

Esta terminología de coloreo sincronizado es dada por la relación entre la noción de palabra sincronizada en la teoría de autómatas finitos.

Palabras sincronizadas

Dígrafo con palabra de sincronización BRB para el nodo 1, donde R corresponde a arista roja y B corresponde a arista azul.

Véase también: Teoría de autómatas

Si existe un camino en un autómata desde el estado ${\boldsymbol {p}}$ al estado ${\boldsymbol {q}}$ y las aristas del camino son $\sigma _{1},\sigma _{2},\ldots ,\sigma _{k}$, en ese orden, luego para $s=\sigma _{1},\sigma _{2},\cdots ,\sigma _{k}\in \Sigma ^{+}$, escribimos ${\boldsymbol {q}}={\boldsymbol {p}}s$.

Sea entonces $Ps$ el mapeo del subconjunto $P\subseteq G$ a través de $s\in \Sigma ^{+}$ y sea $Ps^{-1}$ el conjunto maximal de estados $Q$ tal que $Qs\subseteq P$.

Una palabra (también conocida como cadena) $s\in \Sigma ^{+}$ es llamada palabra sincronizada del autómata con grafo de transición $D$ si $|Ds|=1$. Por otro lado, un par de vértices ${\boldsymbol {p}}$ y ${\boldsymbol {q}}$ de un grafo se dicen sincronizados si existe $s\in \Sigma ^{+}$ tal que ${\boldsymbol {p}}s={\boldsymbol {q}}s$. En el caso contrario, es decir, si para todo $s\in \Sigma ^{+}$, ${\boldsymbol {p}}s\neq {\boldsymbol {q}}s$, llamamos al par de vértices punto muerto (deadlock, en inglés).

Un par de vértices (estados) ${\boldsymbol {p}}$ y ${\boldsymbol {q}}$ sincronizados son llamados estables si para cualquier palabra $u$, el par ${\boldsymbol {p}}u$ y ${\boldsymbol {q}}u$ es también sincronizado.

Conjuntos F-maximales

Sea $u$ un autovector izquierdo con componentes positivas sin divisores comunes con la matriz de adyacencia de un grafo $G$ con vértices ${\boldsymbol {p_{1}}},{\boldsymbol {p_{2}}},\ldots ,{\boldsymbol {p_{n}}}$. La $i$-ésima componente $u_{i}$ del vector es llamado el peso del vértice ${\boldsymbol {p_{i}}}$ y denotado por $w{\boldsymbol {p_{i}}}$. La suma de los pesos de los vértices de un subconjunto $D\subseteq G$ se denota por $w(D)$ y se llama el peso de $D$.

Dado un grafo $G$, un subconjunto $D\subseteq G$ se dice ${\boldsymbol {F}}$-maximal si $w(D)$ es maximal y $|Ds|=1$ para alguna palabra $s\in \Sigma ^{+}$.

Historia y antecedentes

El problema fue inicialmente planteado por Adler, Goodwyn y Weiss en un artículo de la Sociedad estadounidense de Matemática en 1970. Este fue enunciado explícitamente para grafos AGW cuyo máximo común divisor de la longitud de todos sus ciclos sea 1:

Para un grafo aperiódico con grado exterior uniforme, deberá existir un coloreo de aristas tal que para cierta secuencia, independiente del vértice inicial, seguir dicha secuencia de colores siempre llevará al mismo vértice. Adler, Goodwyn & Weiss, 1970

Por más de 30 años, muchos matemáticos intentaron resolver este problema, e incluso se hicieron progresos para casos particulares. Los dos más notables son:

Si un dígrafo $D$ es finito fuertemente conexo aperiódico sin aristas múltiples, y $D$ contiene un ciclo simple de longitud prima como subconjunto propio de $D$, entonces $D$ posee un coloreo sincronizado. O' Brien, 1981

Si un dígrafo $D$ es finito fuertemente conexo aperiódico (las aristas múltiples son permitidas), y todo vértice tiene el mismo grado exterior e interior $k$, entonces $D$ posee un coloreo sincronizado. Kari, 2003

Sin embargo, la conjetura se mantuvo sin probar hasta el 2007 cuando un matemático israelí, llamado Avraham Trahtman, finalmente logró probarla y convertirla en teorema. Trahtman era un científico de la Unión Soviética antes de que tuviese que emigrar a Israel, donde trabajó como guardia de seguridad.​​

Teorema

Dígrafo con coloreo sincronizado, cuya palabra de sincronización para el nodo 3 es "RRR" (o "Rojo-Rojo-Rojo").

Para que un coloreo sincronizado existan, es necesario que el dígrafo $D$ sea aperiódico.​ El teorema del coloreo de carreteras establece también que la aperiodicidad es una condición suficiente para que dicho coloreo exista. Así, dicho teorema se enuncia brevemente de la siguiente manera:

Todo dígrafo finito fuertemente conexo aperiódico de grado exterior uniforme posee un coloreo sincronizado.

Demostración

La prueba es algo extensa (puede ser consultada aquí, 9 páginas; o aquí), pero su idea es bastante simple: dada una estructura adecuada del grafo, siempre se puede encontrar una partición de este en ciclos y árboles. Trahtman probó que existen un subgrafo tal que hay un único árbol no-trivial fuera del ciclo con una única hoja con valor máximo. De hecho, por su definición de subgrafo, cada vértice sólo tienen una arista de salida. Por tanto, siempre y cuando estemos fuera del ciclo, podemos finalizar en el mismo vértice. Así, el problema se reduce a estudiarlo dentro del ciclo. Trahtman probó que siempre se puede seguir una secuencia y entrar en el árbol sin importar el vértice inicial, probando entonces el teorema.

Algoritmo

Antes del artículo de Trahtman, se establecieron intentos indirectos de implementar un algoritmo en la rama de la computación basada en ADN, usando la computación paralela masiva de secuencias de longitud $O(n^{3})$. Actualmente existen algoritmos de orden $O(n^{2})$ y $O(n^{3})$ en el peor de los casos (uno de ellos puede ser consultado aquí). Puesto que la prueba dada por Trahtman es constructiva, la mayoría de dichos algoritmos se basan en los resultados establecidos en la demostración del teorema. Más aún, existen algunos que dado cualquier grafo, verifican si este cumple o no las hipótesis del teorema, y en caso de ser afirmativa la respuesta, encuentran el coloreo correspondiente.​

En términos generales, la mayoría de los algoritmos proceden así:

Algoritmo del problema de coloreo de carreteras

Entrada: Un grafo $G$. Procedimiento: Verificar si el grafo $G$ posee un sumidero (sink, en inglés), es decir, un nodo cuyo grado de salida es nulo y el grado de entrada es positivo (este paso usa el lema 3 de Trahtman y verifica si el grafo posee un par estable): En caso negativo, retornar error ($G$ no es un AGW) y detenerse. En caso afirmativo, reducir el grafo a uno más pequeño usando la congruencia de Trahtman. Repetir hasta que el grafo tenga sólo un sumidero. 2. Encontrar una secuencia de coloreo para $G$ (o su versión reducida, dada por el primer paso). 3. Verificar si el máximo común divisor de la longitud de todos los ciclos es 1: En caso negativo, detenerse y retornar el coloreo encontrado en el segundo paso. En caso positivo, continuar al siguiente paso. 4. Para cada color encontrado previamente, verificar para cada vértice si este tiene dos aristas entrantes. En caso negativo retornar error y detenerse. En caso positivo, continuar al siguiente paso. 5. Encontrar el subgrafo generado por dicho vértice y cambiar este subgrafo por el subgrafo con sólo ciclos. 6. Usar el lema 7 de Trahtman para convertir $G$ en un grafo con un solo árbol no trivial con nivel maximal. 7. Encontrar el coloreo sincronizado dado por la prueba del teorema y retornarlo. Salida: Un coloreo sincronizado del grafo $G$.

Pocos años después del artículo de Trahtman, él publicó en formato libre (paquete TESTAS) el algoritmo arriba enunciado (puede ser consultado y usado aquí (enlace roto disponible en Internet Archive; véase el historial, la primera versión y la última).). La complejidad de dicho algoritmo es del orden $O(n^{2})$, dado que el proceso de hallar los subgrafos y las modificaciones son de tiempo lineal. Luego, iterar los colores hace al algoritmo cuadrático. En el peor de los casos, el algoritmo es de orden $O(n^{3})$ pero esto sucede cuando el número de ciclos (y por tanto, el tamaño del grafo) disminuye lentamente. De igual forma, los bucles no aparecen y el caso de las dos aristas entrantes aparece en rara ocasión. De cualquier manera, la clase de complejidad del algoritmo es cuadrática.​

Aplicaciones

Ciencias de la computación

Autómatas

Representación mediante dígrafos de un autómata finito determinista (AFD).

El teorema es bastante útil en la teoría de autómatas, dado que cuando un autómata está corriendo y encuentra un error, si se cumplen ciertas condiciones (las hipótesis del teorema), existirá entonces una secuencia tal que el autómata puede regresar sobre su proceso hasta un estado "correcto", independientemente de dónde se haya topado con el error.​​

Codificación Huffman

Con ayuda del teorema de coloreo de carreteras, se establece que dada una codificación Huffman, cuando la longitud de las palabras del código son primos relativos, existe otra codificación Huffman (con la misma distribución de longitud) con un decodificador sincronizado.​

Conjetura de Černý

En 1964 Jan Černý conjeturó que $(n-1)^{2}$ es una cota superior para la longitud de la más corta palabra sincronizada para cualquier autómata (grafo AGW) de $n$ estados. El problema de estimar la longitud de las palabras sincronizadas tiene una larga historia, y se conoce como la conjetura de Černý.​ A lo largo de los años se ha ido acotando dicha cantidad, siendo una de las mejores estimaciones $(n^{3}-n)/6$.​ Sin embargo, David Eppstein demostró que el problema de encontrar la palabra sincronizada más corta posible es un problema NP-completo.​

Véase también

• Teorema de los cuatro colores
• Coloración de grafos
• Grafo dirigido
• Anexo:Glosario de teoría de grafos
• Teoría de autómatas

Referencias

Bibliografía

• Wang, Wifu (2011), The Road Coloring Problem .
• Béal, Marie-Pierre; Perrin, Dominique (2008), «A quadratic algorithm for road coloring», Computing Research Repository, arXiv=0803.0726v9 ..
• Béal, Marie-Pierre; Perrin, Dominique (2012), Road Coloring, arXiv=0803.0726v9 ..
• Adler, R.L.; Weiss, B. (1970), «Similarity of automorphisms of the torus», Memoires of the American Mathematical Society 98 ..
• Hegde, Rajneesh; Jain, Kamal (2005), «A min-max theorem about the road coloring conjecture», Discrete Mathematics & Theoretical Computer Science - Proc. EuroComb 2005: 279-284 ..
• Kari, Jarkko (2003), «Synchronizing finite automata on Eulerian digraphs», Theoretical Computer Science 295 (1-3): 223-232, doi:10.1016/S0304-3975(02)00405-X ..
• O'Brien, G. L. (1981), «The road-colouring problem», Israel Journal of Mathematics 39 (1–2): 145-154, doi:10.1007/BF02762860 ..
• Trahtman, Avraham N. (2009), «The road coloring problem», Israel Journal of Mathematics 172 (1): 51-60, arXiv:0709.0099, doi:10.1007/s11856-009-0062-5 ..

• Datos: Q1937896