PROFILPELAJAR.COM

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).^[1] 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

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.^[2] 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)

Veja também

Notas

↑ Seigel-Itzkovich, Judy (8 de fevereiro de 2008). «Russian immigrant solves math puzzle». The Jerusalem Post. Consultado em 13 de setembro de 2010
↑ Hegde & Jain (2005).

Referências

Adler, R.L.; Weiss, B. (1970), Similarity of automorphisms of the torus, Memoires of the American Mathematical Society, 98 .
Hegde, Rajneesh; Jain, Kamal (2005), «A min-max theorem about the road coloring conjecture», Proc. EuroComb 2005 (PDF), Discrete Mathematics & Theoretical Computer Science, pp. 279–284 .
Kari, Jarkko (2003), «Synchronizing finite automata on Eulerian digraphs», Theoretical Computer Science, 295 (1-3): 223–232, doi:10.1016/S0304-3975(02)00405-X .
O'Brien, G. L. (1981), «The road-colouring problem», Israel Journal of Mathematics, 39 (1–2): 145–154, doi:10.1007/BF02762860 .
Trahtman, Avraham N. (2009), «The road coloring problem», Israel Journal of Mathematics, 172 (1): 51–60, arXiv:0709.0099, doi:10.1007/s11856-009-0062-5 .