Loading AI tools
De Wikipedia, la enciclopedia libre
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.[1] Usualmente, este problema se plantea en términos coloquiales como:
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[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. Las definiciones y teoremas han sido adaptados de aquí y aquí.
|
|
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.
|
Por tanto, es periódico si existe una -partición cíclica de para algún entero . Si no es periódico, se dice que es aperiódico. Además, un grafo fuertemente conexo aperiódico y externo-regular, es usualmente llamado un grafo AGW.
|
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.
|
Sea entonces el mapeo del subconjunto a través de y sea el conjunto maximal de estados tal que .
|
Un par de vértices (estados) y sincronizados son llamados estables si para cualquier palabra , el par y es también sincronizado.
Sea un autovector izquierdo con componentes positivas sin divisores comunes con la matriz de adyacencia de un grafo con vértices . La -ésima componente del vector es llamado el peso del vértice y denotado por . La suma de los pesos de los vértices de un subconjunto se denota por y se llama el peso de .
|
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:
|
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:
|
|
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.[5][7]
Para que un coloreo sincronizado existan, es necesario que el dígrafo sea aperiódico.[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:
|
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.
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 . Actualmente existen algoritmos de orden y 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.[7]
En términos generales, la mayoría de los algoritmos proceden así:
Algoritmo del problema de coloreo de carreteras |
Entrada: Un grafo . Procedimiento:
Salida: Un coloreo sincronizado del 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).). La complejidad de dicho algoritmo es del orden , 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 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.[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.[6][7]
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.[9]
En 1964 Jan Černý conjeturó que es una cota superior para la longitud de la más corta palabra sincronizada para cualquier autómata (grafo AGW) de estados. El problema de estimar la longitud de las palabras sincronizadas tiene una larga historia, y se conoce como la conjetura de Černý.[10] A lo largo de los años se ha ido acotando dicha cantidad, siendo una de las mejores estimaciones .[11] Sin embargo, David Eppstein demostró que el problema de encontrar la palabra sincronizada más corta posible es un problema NP-completo.[12]
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.