Problema De La Coloraci N De Caminos

Conjetura de la coloración de caminos
F. M Alconada Verzini
Facultad de Informática
Universidad Nacional de La Plata
Buenos Aires, Argentina
federico.alconada@icloud.com


 
1

 

Abstract. El problema de la coloración de caminos establece que todo grafo
dirigido aperiódico con grados de salida constantes tiene una coloración
sincronizable. Este teorema fue conjeturado por Adler, Goodwyn yWeiss hace
más de 30 años hasta que, en el año 2007, Avraham Trahtman lo probó.
Este problema ha tenido gran interés para el campo de la teoría de grafos, los
autómatas determinísticos y la dinámica simbólica.
Esta monografía tiene como principal objetivo introducir al lector, de manera
sencilla y comprensible, acerca del problema de la coloración de caminos. Se
presentarán las principalescaracterísticas sobre la conjetura, algoritmos y
teoremas que ayudan a la comprensión integral sobre el tema en cuestión y la
complejidad del problema entre otros aspectos.

Introducción

El problema de la coloración de caminos fue conjeturado por Roy Adler y Benjamin
Weiss en el año 1970.
Dicho problema trata con instrucciones de sincronización. La cuestión radica en
si, a través del uso de estasinstrucciones, se puede alcanzar o localizar un objeto o
destino desde cualquier otro punto dentro de una red.
Imaginemos un mapa con rutas que son coloreadas de tal forma que una
secuencia fija de colores, llamada homing sequence1, guía al viajero a un lugar en
particular sin importar cuál haya sido el punto de comienzo. Dicha coloración de las
rutas se llama coloración sincronizada y, encontrar unacoloración sincronizada es el
objetivo del croblema de la coloración de caminos.
El teorema de la coloración de caminos establece que todo grafo dirigido
aperiódico con vértices cuyos grados de salida son constantes tiene una coloración
sincronizada si el máximo común divisor (MCD) de las longitudes de todos los ciclos
es igual a uno.

1

Informalmente, una home sequence es una secuencia de entradasque, cuando se alimenta a la máquina, se
garantiza que ‘orienta’ a quien aprende: las salidas obtenidas de la home sequence determinan
completamente el estado que alcanzó el autómata al final de la secuencia. Toda máquina de estado finita
tiene una homing sequence.

2
 
 
 
 
 
 F.
 M
 Alconada
 Verzini
 
 

1.1 Ejemplo


 
El gráfico de la derecha muestra un grafo dirigidocon 8
vértices en el cual cada uno de éstos tiene grado de
salida igual a 2 (también el grado de entrada es 2, pero
esto no es necesario que así sea). Las aristas de este
grafo han sido coloreadas de azul y rojo para crear una
coloración sincronizada.
Por ejemplo, consideremos el vértice marcado con
amarillo. No importa desde dónde se comience que
mientras se recorran todas las 9 aristas en elrecorrido
“azul-rojo-rojo—azul-rojo-rojo—azul-rojo-rojo”, se
terminara en el vértice amarillo. De la misma forma, si se recorren todas las 9 aristas
en el recorrido “azul-azul-rojo—azul-rojo-rojo—azul-rojo-rojo”, se terminará el
recorrido llegando al vértice verde, sin importar desde dónde se haya comenzado.
El teorema de la coloración de caminos establece que, para una cierta categoría
de grafosdirigidos, es siempre posible crear una coloración.

2 Aplicaciones del problema
Resolver el problema de la coloración de caminos para cada caso particular no es sólo
un desafío sino que además tiene muchas aplicaciones en diferentes áreas como
programación o sistemas computacionales. Estos sistemas son generalmente
modelados por autómatas de estados finitos (por ejemplo, grafos con etiquetas).Debido a algunas dificultades, el sistema puede tomar una transición errónea.
Estas dificultades pueden deberse por ejemplo a propiedades físicas de los sensores o
la falta de fiabilidad del hardware computacional. Resulta que el comportamiento
asintótico de los autómatas sincronizados es mejor que el de aquellos no
sincronizados. Por ende, los autómatas sincronizados son menos sensibles a los...