Teorema del coloreo de carreteras

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.

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: Plantilla:Cita

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

Plantilla:AP Plantilla:Definición Plantilla:Definición 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. Plantilla:Definición Por tanto, $D$ es periódico si existe una $k$-partición cíclica de $V(D)$ para algún entero $k\ge 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

Plantilla:AP Plantilla:Definición 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.

Plantilla:VT Plantilla:Definición Sea entonces $Ps$ el mapeo del subconjunto $P\subseteq G$ a través de $s\in {\mathrm{\Sigma }}^{+}$ y sea $P{s}^{-1}$ el conjunto maximal de estados $Q$ tal que $Qs\subseteq P$. Plantilla:Definición Un par de vértices (estados) $𝒑$ y $𝒒$ sincronizados son llamados estables si para cualquier palabra $u$, el par $𝒑u$ y $𝒒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 ${𝒑}_1,{𝒑}_2,\dots ,{𝒑}_{𝒏}$. La $i$-ésima componente $u_i$ del vector es llamado el peso del vértice ${𝒑}_{𝒊}$ y denotado por $w{𝒑}_{𝒊}$. 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$. Plantilla:Definición

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: Plantilla:Teorema 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: Plantilla:Teorema Plantilla:Teorema 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: Plantilla:Teorema

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í: Plantilla:Algoritmo

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 Plantilla:Enlace roto). 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

Plantilla:AP 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ý

Plantilla:AP 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

• Plantilla:Citation
• Plantilla:Citation.
• Plantilla:Citation.
• Plantilla:Citation.
• Plantilla:Citation.
• Plantilla:Citation.
• Plantilla:Citation.
• Plantilla:Citation.