In graph theory the road coloring theorem, known previously as the road coloring conjecture, deals with synchronized instructions. The issue involves whether by using such instructions, one can reach or locate an object or destination from any other point within a network (which might be a representation of city streets or a maze). In the real world, this phenomenon would be as if you called a friend to ask for directions to his house, and he gave you a set of directions that worked no matter where you started from. This theorem also has implications in symbolic dynamics.
| Attributes | Values |
|---|
| rdf:type
| |
| rdfs:label
| - Teorema del coloreo de carreteras (es)
- Coloriage des routes (fr)
- Road coloring theorem (en)
- Teorema da coloração do caminho (pt)
- Vägfärgningsproblemet (sv)
- Теорема о раскраске дорог (ru)
|
| rdfs:comment
| - Le coloriage des routes est un problème combinatoire qui relève à la fois de la théorie des graphes et en théorie des automates. Il s'agit d'une propriété de synchronisation dans un réseau routier. La question est de savoir si l'on peut « colorier » les routes d'un réseau routier (ou, de manière équivalente, colorier les arcs d'un graphe fini) de telle sorte que, quel que soit le point de départ, en suivant la séquence de routes de même nom (ou de même couleur), on arrive au même point d'arrivée. Le problème du coloriage des routes et la conjecture correspondante (la conjecture du coloriage des routes) ont d'abord été formulés par Adler et Weiss en 1970. Le théorème correspondant, le théorème du coloriage des routes, a été démontré par Avraham Trahtman en 2009. (fr)
- Inom grafteori är vägfärningsproblemet ett problem som rör graffärgning. Problemet är om det är möjligt att i ett nätverk kunna skapa instruktioner som gör att man kan ta sig till en specifik punkt från alla punkter med samma instruktion. Problemet ställdes först av Benjamin Weiss och Roy Adler 1970. September 2007 visade att det var möjligt att skapa såna instruktioner. (sv)
- В теории графов теорема о раскраске дорог, известная до недавнего времени как гипотеза о раскраске дорог, имеет дело с инструкциями синхронизации. Задача ставится в нахождении таких инструкций, чтобы независимо от начального положения объекта можно было бы дойти до пункта назначения в сети (которая может представлять собой улицы города или лабиринт). В реальном мире можно данную задачу представить как набор инструкций для вашего друга, по которым он может добраться до вашего дома независимо от того, где он находится сейчас. Теорема также имеет приложение в символической динамике. (ru)
- En teoría de grafos el teorema de coloreo de carreteras, teorema del camino coloreado o, conocido antiguamente como la conjetura del coloreo de carreteras, es un problema de coloreo de grafos planos. El planteamiento inicial, en términos intuitivos, consiste en que dada una red (grafo que representa ya sea una ciudad o laberinto) con determinadas condiciones, y dada una posición en el mismo, buscar si existe, y cuál es, una serie de instrucciones que independientemente del posicionamiento inicial, permitan llegar a la posición requerida.Usualmente, este problema se plantea en términos coloquiales como: (es)
- In graph theory the road coloring theorem, known previously as the road coloring conjecture, deals with synchronized instructions. The issue involves whether by using such instructions, one can reach or locate an object or destination from any other point within a network (which might be a representation of city streets or a maze). In the real world, this phenomenon would be as if you called a friend to ask for directions to his house, and he gave you a set of directions that worked no matter where you started from. This theorem also has implications in symbolic dynamics. (en)
- 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. (pt)
|
| foaf:depiction
| |
| dct:subject
| |
| Wikipage page ID
| |
| Wikipage revision ID
| |
| Link from a Wikipage to another Wikipage
| |
| Link from a Wikipage to an external page
| |
| sameAs
| |
| dbp:wikiPageUsesTemplate
| |
| thumbnail
| |
| has abstract
| - En teoría de grafos el teorema de coloreo de carreteras, teorema del camino coloreado o, conocido antiguamente como la conjetura del coloreo de carreteras, es un problema de coloreo de grafos planos. El planteamiento inicial, en términos intuitivos, consiste en que dada una red (grafo que representa ya sea una ciudad o laberinto) con determinadas condiciones, y dada una posición en el mismo, buscar si existe, y cuál es, una serie de instrucciones que independientemente del posicionamiento inicial, permitan llegar a la posición requerida.Usualmente, este problema se plantea en términos coloquiales como: Supongamos que alguien visita una ciudad que no conoce, con la peculiaridad de que dicho lugar no contiene ninguna clase de señal indicativa. Luego de haber vagado un par de horas, el visitante le pide ayuda a alguien para llegar a determinado lugar, contándole que no sabe dónde está. ¿Existe alguna serie de instrucciones que se le puedan dar al turista para que, independientemente de dónde se encuentre, pueda llegar a su destino? Este teorema fue conjeturado por primera vez por , y en 1970 y replanteado en 1977, siendo probado 37 años después, en 2007 por el israelí de origen ruso . Sus aplicaciones van desde la cartografía hasta el y la teoría de automatización. (es)
- In graph theory the road coloring theorem, known previously as the road coloring conjecture, deals with synchronized instructions. The issue involves whether by using such instructions, one can reach or locate an object or destination from any other point within a network (which might be a representation of city streets or a maze). In the real world, this phenomenon would be as if you called a friend to ask for directions to his house, and he gave you a set of directions that worked no matter where you started from. This theorem also has implications in symbolic dynamics. The theorem was first conjectured by Roy Adler and Benjamin Weiss. It was proved by Avraham Trahtman. (en)
- Le coloriage des routes est un problème combinatoire qui relève à la fois de la théorie des graphes et en théorie des automates. Il s'agit d'une propriété de synchronisation dans un réseau routier. La question est de savoir si l'on peut « colorier » les routes d'un réseau routier (ou, de manière équivalente, colorier les arcs d'un graphe fini) de telle sorte que, quel que soit le point de départ, en suivant la séquence de routes de même nom (ou de même couleur), on arrive au même point d'arrivée. Le problème du coloriage des routes et la conjecture correspondante (la conjecture du coloriage des routes) ont d'abord été formulés par Adler et Weiss en 1970. Le théorème correspondant, le théorème du coloriage des routes, a été démontré par Avraham Trahtman en 2009. (fr)
- 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). (pt)
- Inom grafteori är vägfärningsproblemet ett problem som rör graffärgning. Problemet är om det är möjligt att i ett nätverk kunna skapa instruktioner som gör att man kan ta sig till en specifik punkt från alla punkter med samma instruktion. Problemet ställdes först av Benjamin Weiss och Roy Adler 1970. September 2007 visade att det var möjligt att skapa såna instruktioner. (sv)
- В теории графов теорема о раскраске дорог, известная до недавнего времени как гипотеза о раскраске дорог, имеет дело с инструкциями синхронизации. Задача ставится в нахождении таких инструкций, чтобы независимо от начального положения объекта можно было бы дойти до пункта назначения в сети (которая может представлять собой улицы города или лабиринт). В реальном мире можно данную задачу представить как набор инструкций для вашего друга, по которым он может добраться до вашего дома независимо от того, где он находится сейчас. Теорема также имеет приложение в символической динамике. (ru)
|
| prov:wasDerivedFrom
| |
| page length (characters) of wiki page
| |
| foaf:isPrimaryTopicOf
| |
| is Link from a Wikipage to another Wikipage
of | |
![[RDF Data]](/fct/images/sw-rdf-blue.png)
![[cxml]](/fct/images/cxml_doc.png)
![[csv]](/fct/images/csv_doc.png)
![[text]](/fct/images/ntriples_doc.png)
![[turtle]](/fct/images/n3turtle_doc.png)
![[ld+json]](/fct/images/jsonld_doc.png)
![[rdf+json]](/fct/images/json_doc.png)
![[rdf+xml]](/fct/images/xml_doc.png)
![[atom+xml]](/fct/images/atom_doc.png)
![[html]](/fct/images/html_doc.png)
