Em teoria dos grafos o teorema da coloração do caminho, conhecido até recentemente como a conjectura da coloração do caminho, lida com instruções sincronizadas. O problema envolve se, usando essas instruções, pode-se alcançar ou localizar um objeto ou o destino de qualquer outro ponto dentro de uma rede (que pode ser uma representação das ruas de uma cidade ou de um labirinto). No mundo real, este fenômeno seria como se você ligasse para um amigo para pedir o caminho para a casa dele, e ele lhe desse um conjunto de caminhos que funcionou, independente de onde você começou. Este teorema também tem implicações em dinâmica simbólica.
O teorema foi conjecturado pela primeira vez por Roy Adler e Benjamin Weiss (1970). E foi provado por Avraham Trahtman (2009).
Exemplo e intuição right|thumb|Um grafo direcionado com uma coloração de sincronização A imagem à direita mostra um grafo direcionado com oito vértices em que cada vértice tem grau de saída 2. (Cada vértice, nesse caso, também tem grau de entrada 2, mas isto não é necessário para existir uma coloração de sincronização.) As arestas deste grafo tem sido coloridas de vermelho e azul para criar uma coloração sincronizadora.
Por exemplo, considere o vértice marcado de amarelo. Não importa por onde você começa no grafo, se você percorrer todas as nove arestas através do caminho "azul-vermelho-vermelho-azul-vermelho-vermelho-azul-vermelho-vermelho", você acabará no vértice amarelo. Igualmente, se você percorrer todas as nove arestas através do caminho "azul-azul-vermelho-azul-azul-vermelho-azul-azul-vermelho", você sempre acabará no vértice marcado de verde, não importa por onde você comece.
O teorema da coloração do caminho afirma que para uma certa categoria de grafos direcionados, é sempre possível criar tal coloração.
Descrição matemática Seja G um grafo direcionado finito, fortemente conexo, onde todos os vértices têm o mesmo grau de saída k. Seja A um alfabeto contendo os valores 1, ..., k. Uma coloração sincronizadora (também conhecida como uma coloração colapsável) em G é uma marcação das arestas em G com valores de A de tal modo que (1) cada vértice tem exatamente uma extremidade de saída com uma determinada marcação e (2) para cada vértice v no grafo, existe uma palavra w sobre A de modo que todos os caminhos em G correspondentes a w terminam em v.
A terminologia coloração sincronizadora é devido à relação entre esta noção e a noção de palavra sincronizadora em teoria dos autômatos finitos.
Para uma tal coloração existir, é necessário que G seja aperiódico.. O teorema da coloração do caminho afirma que aperidiocidade é também suficiente para uma tal coloração existir. Portanto, o problema da coloração do caminho pode ser apresentado de forma sucinta como: Todo grafo direcionado aperiódico finito fortemente conexo de grau de saída uniforme tem uma coloração sincronizadora.
Resultados parciais anteriores Resultados parciais ou casos especiais anteriores incluem o seguinte: Se G é um grafo direcionado aperiódico finito fortemente conexo sem arestas múltiplas, e G contém um ciclo simples de comprimento primo que é um subconjunto próprio de G, então G tem uma coloração sincronizadora. (O'Brien 1981)
Se G é um grafo direcionado aperiódico finito fortemente conexo (múltiplas arestas permitido) e todo vértice tem o mesmo grau de entrada e grau de saída k, então G tem uma coloração sincronizadora. (Kari 2003)
Ver também Teorema das quatro cores Coloração de grafos
Notas
Referências . . . . . Categoria:Teoria dos autômatos Categoria:Combinatória Categoria:Matemática e cultura