| Property |
Value |
| dbo:abstract
|
- 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)
- 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)
|
| dbo:namedAfter
| |
| dbo:thumbnail
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 12000 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| prop-fr:wikiPageUsesTemplate
| |
| rdfs:comment
|
- 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)
- 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)
|
| rdfs:label
|
- Théorème de Gallai-Hasse-Roy-Vitaver (fr)
- Théorème de Gallai-Hasse-Roy-Vitaver (fr)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:depiction
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageWikiLink
of | |
| is oa:hasTarget
of | |
| is foaf:primaryTopic
of | |
