Teorema da coloração do caminho: diferenças entre revisões

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]]).<ref>{{cite news |last = Seigel-Itzkovich|first = Judy|title = Russian immigrant solves math puzzle|pages = |publisher = The Jerusalem Post|date = 2008-02-08|url = http://www.jpost.com/Home/Article.aspx?id=91431|accessdate = 2010-09-13}}</ref> 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 trabalhoufuncionou, sem importar a partirindependente de onde você começou. Este teorema também tem implicações em dinâmica simbólica.

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 de sincronizaçãosincronizadora.

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. SimilarmenteIgualmente, 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.

FaçamosSeja ''G'' um [[grafo direcionado]] finito, fortemente conectadoconexo, onde todos os vértices temtêm o mesmo grau de saída ''k''. FaçamosSeja <span>''A''</span> um alfabeto contendo os valores 1, ..., ''k''. Uma ''coloração de sincronizaçãosincronizadora'' (também conhecidoconhecida como uma ''coloração flexívelcolapsá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 de sincronizaçãosincronizadora'' é devido aà relação entre esta noção e a noção de palavra de sincronizaçãosincronizadora em teoria dos [[Máquina de estados finitos|autômatos finitos]].

Para uma tal coloração existir, é necessário que ''G'' seja aperiódico.<ref>{{harvtxt|Hegde|Jain|2005}}.</ref> 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 brevementede forma sucinta como:

: ''Todo grafo direcionado aperiódico finito fortemente ligadoconexo de grau de saída uniforme tem uma coloração de sincronizaçãosincronizadora.''

* Se ''G'' é um grafo direcionado aperiódico finito fortemente ligadoconexo sem arestas múltiplas, e ''G'' contém um ciclo simples de comprimento [[número primo|primo]] que é um subconjunto próprio de ''G'', então ''G'' tem uma coloração de sincronizaçãosincronizadora. (O'Brien 1981)<br>

* Se ''G'' é um grafo direcionado aperiódico finito fortemente ligadoconexo (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 de sincronizaçãosincronizadora. (Kari 2003)<br>