| dbo:abstract
|
- In graph theory, the Gallai–Hasse–Roy–Vitaver theorem is a form of duality between the colorings of the vertices of a given undirected graph and the orientations of its edges. It states that the minimum number of colors needed to properly color any graph equals one plus the length of a longest path in an orientation of chosen to minimize this path's length. The orientations for which the longest path has minimum length always include at least one acyclic orientation. This theorem implies that every orientation of a graph with chromatic number contains a simple directed path with vertices; this path can be constrained to begin at any vertex that can reach all other vertices of the oriented graph. (en)
- En théorie des graphes, le théorème de Gallai-Hasse-Roy-Vitaver énonce une dualité entre les colorations des sommets d'un graphe non orienté donné et les orientations de ses arêtes. Il dit que le nombre minimum de couleurs nécessaires pour colorer un graphe G (son nombre chromatique) est égal à 1 plus la longueur du plus long chemin dans une orientation de G choisie pour minimiser la longueur de ce chemin. Les orientations pour lesquelles le chemin le plus long a une longueur minimale comprennent toujours au moins une orientation acyclique. Une des conséquences du théorème est que toute orientation d'un graphe de nombre chromatique k contient un chemin orienté simple avec k sommets ; ce chemin peut être forcé à commencer en n'importe quel sommet à partir duquel on peut atteindre tous les autres sommets du graphe orienté. (fr)
- Теорема Галлаи – Хассе – Роя – Витавера — это вид двойственности между раскрасками вершин заданного неориентированного графа и ориентациями его рёбер. Теорема утверждает, что минимальное число красок, необходимых для правильной раскраски любого графа G, на единицу больше длины в ориентации графа G, в которой эта длина пути минимальна. В ориентации, в которых путь максимальной длины имеет минимальную длину, всегда входит по меньшей мере одна ациклическая ориентация. Альтернативная формулировка той же теоремы утверждает, что любая ориентация графа с хроматическим числом k содержит простой ориентированный путь с k вершинами. Можно наложить условия, чтобы путь начинался в любой вершине, и чтобы из этой вершины можно было достичь любую другую вершину ориентированного графа. (ru)
|
| dbo:thumbnail
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 14706 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| gold:hypernym
| |
| rdf:type
| |
| rdfs:comment
|
- In graph theory, the Gallai–Hasse–Roy–Vitaver theorem is a form of duality between the colorings of the vertices of a given undirected graph and the orientations of its edges. It states that the minimum number of colors needed to properly color any graph equals one plus the length of a longest path in an orientation of chosen to minimize this path's length. The orientations for which the longest path has minimum length always include at least one acyclic orientation. (en)
- En théorie des graphes, le théorème de Gallai-Hasse-Roy-Vitaver énonce une dualité entre les colorations des sommets d'un graphe non orienté donné et les orientations de ses arêtes. Il dit que le nombre minimum de couleurs nécessaires pour colorer un graphe G (son nombre chromatique) est égal à 1 plus la longueur du plus long chemin dans une orientation de G choisie pour minimiser la longueur de ce chemin. Les orientations pour lesquelles le chemin le plus long a une longueur minimale comprennent toujours au moins une orientation acyclique. (fr)
- Теорема Галлаи – Хассе – Роя – Витавера — это вид двойственности между раскрасками вершин заданного неориентированного графа и ориентациями его рёбер. Теорема утверждает, что минимальное число красок, необходимых для правильной раскраски любого графа G, на единицу больше длины в ориентации графа G, в которой эта длина пути минимальна. В ориентации, в которых путь максимальной длины имеет минимальную длину, всегда входит по меньшей мере одна ациклическая ориентация. (ru)
|
| rdfs:label
|
- Gallai–Hasse–Roy–Vitaver theorem (en)
- Théorème de Gallai-Hasse-Roy-Vitaver (fr)
- Теорема Галлаи — Хассе — Роя — Витавера (ru)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:depiction
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
