Teorema del coloreo de carreteras
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.
[1] Usualmente, este problema se plantea en términos coloquiales como:
Este teorema fue conjeturado por primera vez por Roy Adler, Wayne Goodwyn y Benjamin Weiss en 1970[2] y replanteado en 1977,[3] siendo probado 37 años después, en 2007 por el israelí de origen ruso Avraham Trahtman.
[4][5] Sus aplicaciones van desde la cartografía hasta el simbolismo dinámico y la teoría de automatización.
[6] La notación usada a continuación es la dada por Trahtman en su demostración original.
se dice externo-regular o con grado externo uniforme si existe un entero
es periódico si es posible encontrar una partición en el conjunto de vértices,
del grafo se dice propio si cualesquiera dos aristas incidentes al mismo vértice de
de colores tal que para todo vértice
es llamada palabra sincronizada del autómata con grafo de transición
, llamamos al par de vértices punto muerto (deadlock, en inglés).
sincronizados son llamados estables si para cualquier palabra
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.
Por más de 30 años, muchos matemáticos intentaron resolver este problema, e incluso se hicieron progresos para casos particulares.
es finito fuertemente conexo aperiódico sin aristas múltiples, y
es finito fuertemente conexo aperiódico (las aristas múltiples son permitidas), y todo vértice tiene el mismo grado exterior e interior
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.
[8] 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.
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.
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.
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.
[7] En términos generales, la mayoría de los algoritmos proceden así: Entrada: Un grafo
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).).
[7] 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.
es una cota superior para la longitud de la más corta palabra sincronizada para cualquier autómata (grafo AGW) de
[11] Sin embargo, David Eppstein demostró que el problema de encontrar la palabra sincronizada más corta posible es un problema NP-completo.
