Teorema de coloración de carreteras

En teoría de grafos, el teorema de coloración de caminos , conocido anteriormente como la conjetura de coloración de caminos , trata sobre instrucciones sincronizadas . El problema consiste en determinar si, mediante el uso de dichas instrucciones, se puede alcanzar o localizar un objeto o destino desde cualquier otro punto dentro de una red (que podría ser una representación de calles de una ciudad o un laberinto ). ^{[ 1 ]} En el mundo real, este fenómeno sería como si llamaras a un amigo para pedirle indicaciones para llegar a su casa y él te diera un conjunto de indicaciones que funcionaran independientemente de dónde partieras. Este teorema también tiene implicaciones en la dinámica simbólica .

El teorema fue conjeturado por primera vez por Roy Adler y Benjamin Weiss . ^{[ 2 ]} Fue demostrado por Avraham Trahtman en 2009. ^{[ 3 ]}

La imagen de la derecha muestra un grafo dirigido con ocho vértices , donde cada vértice tiene un grado de salida  de 2. (En este caso, cada vértice también tiene un grado de entrada  de 2, pero esto no es necesario para que exista una coloración sincronizada). Las aristas de este grafo se han coloreado de rojo y azul para crear una coloración sincronizada.

Por ejemplo, consideremos el vértice marcado en amarillo. Sin importar el punto de partida en el grafo, si recorremos las nueve aristas en la secuencia "azul-rojo-rojo—azul-rojo-rojo—azul-rojo-rojo", llegaremos al vértice amarillo. De manera similar, si recorremos las nueve aristas en la secuencia "azul-azul-rojo—azul-azul-rojo—azul-azul-rojo", siempre llegaremos al vértice marcado en verde, independientemente del punto de partida.

El teorema de coloración de caminos establece que, para una determinada categoría de grafos dirigidos, siempre es posible crear dicha coloración.

Entre los resultados parciales o de casos especiales anteriores se incluyen los siguientes:

• Si G es un grafo dirigido aperiódico fuertemente conexo finito sin aristas múltiples , y G contiene un ciclo simple de longitud prima que es un subconjunto propio de G , entonces G tiene una coloración sincronizadora. ^{[ 5 ]}
• Si G es un grafo dirigido aperiódico fuertemente conexo finito (se permiten múltiples aristas) y cada vértice tiene el mismo grado de entrada y grado de salida k , entonces G tiene una coloración sincronizadora. ^{[ 6 ]}

• Teorema de los cuatro colores
• Coloreado de gráficos

• Adler, Roy L.; Weiss , Benjamin (1970), Similitud de automorfismos del toro , Memoirs of the American Mathematical Society , vol.  98, doi : 10.1090/memo/0098.
• Hegde, Rajneesh; Jain, Kamal ( 2005), "Un teorema min-max sobre la conjetura de coloración de carreteras", Actas de EuroComb 2005 , Matemáticas Discretas e Informática Teórica, págs. 279–284 .
• Kari, Jarkko (2003), "Sincronización de autómatas finitos en digrafos eulerianos", Theoretical Computer Science , 295 ( 1–3 ): 223–232 , doi : 10.1016/S0304-3975(02)00405-X.
• O'Brien, GL (1981), "El problema de la coloración de carreteras", Israel Journal of Mathematics , 39 ( 1–2 ): 145–154 , doi : 10.1007/BF02762860.
• Trahtman, Avraham N. (2009), "El problema de la coloración de carreteras", Israel Journal of Mathematics , 172 (1): 51– 60, arXiv : 0709.0099 , doi : 10.1007/s11856-009-0062-5.