Teorema da coloração do caminho

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

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.[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

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

Referências