Teorema da coloração do caminho: diferenças entre revisões
concordancia |
|||
| Linha 1: | Linha 1: | ||
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 |
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 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 <span>(</span>[[1970]]<span>)</span>. E foi provado por Avraham Trahtman <span>(</span>[[2009]]<span>)</span>. |
O teorema foi conjecturado pela primeira vez por Roy Adler e Benjamin Weiss <span>(</span>[[1970]]<span>)</span>. E foi provado por Avraham Trahtman <span>(</span>[[2009]]<span>)</span>. |
||
| Linha 5: | Linha 5: | ||
== Exemplo e intuição == |
== Exemplo e intuição == |
||
[[Ficheiro:Road_coloring_conjecture.svg|right|thumb|Um grafo direcionado com uma coloração de sincronização]] |
[[Ficheiro:Road_coloring_conjecture.svg|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 |
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. |
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. |
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 === |
=== 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 <span>''A''</span> 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 |
A terminologia ''coloração sincronizadora'' é devido à relação entre esta noção e a noção de palavra sincronizadora 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 |
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 de forma sucinta como: |
||
: ''Todo grafo direcionado aperiódico finito fortemente |
: ''Todo grafo direcionado aperiódico finito fortemente conexo de grau de saída uniforme tem uma coloração sincronizadora.'' |
||
== Resultados parciais anteriores == |
== Resultados parciais anteriores == |
||
Resultados parciais ou casos especiais anteriores incluem o seguinte: |
Resultados parciais ou casos especiais anteriores incluem o seguinte: |
||
* Se ''G'' é um grafo direcionado aperiódico finito fortemente |
* Se ''G'' é um grafo direcionado aperiódico finito fortemente conexo 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 sincronizadora. (O'Brien 1981)<br> |
||
* Se ''G'' é um grafo direcionado aperiódico finito fortemente |
* 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)<br> |
||
== Veja também == |
== Veja também == |
||
Revisão das 15h04min de 17 de julho de 2015
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.
