| Property |
Value |
| dbo:abstract
|
- En théorie des graphes et en théorie de complexité des calculs, un graphe de Frankl-Rödl est un graphe dont les sommets sont les sommets d'un hypercube, et les arêtes joignent des sommets qui sont à une même distance paire fixe les uns des autres. Les graphes de ce type sont paramétrés par la dimension de l'hypercube et par la distance entre les sommets déclarés adjacents. Les graphes de Frankl-Rödl portent le nom de Péter Frankl et Vojtěch Rödl, qui ont démontré en 1987 que, pour certaines valeurs des paramètres du graphe, ils ont un nombre de stabilité (taille du stable maximal) petit et un nombre chromatique élevé. Depuis, ces graphes sont devenus intéressants en complexité de calcul, comme des exemples qui sont difficiles pour la programmation semi-définie basée sur des algorithmes d'approximation du problème de couverture par sommets et pour les problèmes de coloration de graphes. Ses propriétés algorithmiques ont été utilisés pour remettre en question la conjecture des jeux uniques. (fr)
- En théorie des graphes et en théorie de complexité des calculs, un graphe de Frankl-Rödl est un graphe dont les sommets sont les sommets d'un hypercube, et les arêtes joignent des sommets qui sont à une même distance paire fixe les uns des autres. Les graphes de ce type sont paramétrés par la dimension de l'hypercube et par la distance entre les sommets déclarés adjacents. Les graphes de Frankl-Rödl portent le nom de Péter Frankl et Vojtěch Rödl, qui ont démontré en 1987 que, pour certaines valeurs des paramètres du graphe, ils ont un nombre de stabilité (taille du stable maximal) petit et un nombre chromatique élevé. Depuis, ces graphes sont devenus intéressants en complexité de calcul, comme des exemples qui sont difficiles pour la programmation semi-définie basée sur des algorithmes d'approximation du problème de couverture par sommets et pour les problèmes de coloration de graphes. Ses propriétés algorithmiques ont été utilisés pour remettre en question la conjecture des jeux uniques. (fr)
|
| dbo:namedAfter
| |
| dbo:thumbnail
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 10911 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| prop-fr:caption
|
- Le graphe est composé de deux copies du graphe de Turán . (fr)
- Le graphe est composé de deux copies du graphe de Clebsch 5-régulier. (fr)
- Le graphe est composé de deux copies du graphe de Turán . (fr)
- Le graphe est composé de deux copies du graphe de Clebsch 5-régulier. (fr)
|
| prop-fr:height
|
- 195 (xsd:integer)
- 200 (xsd:integer)
|
| prop-fr:image
|
- 1 (xsd:integer)
- Clebsch graph.svg (fr)
|
| prop-fr:width
|
- 195 (xsd:integer)
- 200 (xsd:integer)
|
| prop-fr:wikiPageUsesTemplate
| |
| dct:subject
| |
| rdfs:comment
|
- En théorie des graphes et en théorie de complexité des calculs, un graphe de Frankl-Rödl est un graphe dont les sommets sont les sommets d'un hypercube, et les arêtes joignent des sommets qui sont à une même distance paire fixe les uns des autres. Les graphes de ce type sont paramétrés par la dimension de l'hypercube et par la distance entre les sommets déclarés adjacents. (fr)
- En théorie des graphes et en théorie de complexité des calculs, un graphe de Frankl-Rödl est un graphe dont les sommets sont les sommets d'un hypercube, et les arêtes joignent des sommets qui sont à une même distance paire fixe les uns des autres. Les graphes de ce type sont paramétrés par la dimension de l'hypercube et par la distance entre les sommets déclarés adjacents. (fr)
|
| rdfs:label
|
- Graphe de Frankl-Rödl (fr)
- Graphe de Frankl-Rödl (fr)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:depiction
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageWikiLink
of | |
| is oa:hasTarget
of | |
| is foaf:primaryTopic
of | |
