Metraipolis › archive › dc_9ddfe5afbb81
Graphe de Frankl-Rödl — Wikipedia (fr)
- Source
- Wikipedia (fr)
- Original
- https://fr.wikipedia.org/wiki/Graphe_de_Frankl-R%C3%B6dl
- License (as archived)
- CC-BY-SA-4.0
- Archived
- 2026-11-08T03:10:58.161Z
- SHA-256 of the archived text
7a29b4d1820f0bb53508fd06dd4843b5aaa6f01ef5773180bbe6eb7e492cda0a- Stable URL of this page
https://metraipolis.com/documento/dc_9ddfe5afbb81
How to cite
Graphe de Frankl-Rödl — Wikipedia (fr) — Wikipedia (fr), https://fr.wikipedia.org/wiki/Graphe_de_Frankl-R%C3%B6dl (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_9ddfe5afbb81 (Metraipolis archive dc_9ddfe5afbb81, sha256 7a29b4d1820f0bb53508fd06dd4843b5aaa6f01ef5773180bbe6eb7e492cda0a)
BibTeX
@misc{dc9ddfe5afbb81,
title = {Graphe de Frankl-Rödl — Wikipedia (fr)},
howpublished = {Wikipedia (fr)},
url = {https://fr.wikipedia.org/wiki/Graphe_de_Frankl-R%C3%B6dl},
note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_9ddfe5afbb81; sha256 7a29b4d1820f0bb53508fd06dd4843b5aaa6f01ef5773180bbe6eb7e492cda0a},
year = {2026}
}Archived text
Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (fr), https://fr.wikipedia.org/wiki/Graphe_de_Frankl-R%C3%B6dl. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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. Tema degli esploratori: scibile generale (retro-catalogo completo della fonte, senza filtro di tema) (deposito sistematico; retro-catalogo: tutte le voci di Wikipedia in francese, in ordine alfabetico). Fonte: Wikipedia in francese, voce «Graphe de Frankl-Rödl» — https://fr.wikipedia.org/wiki/Graphe_de_Frankl-R%C3%B6dl Wikidata Q25304863: «graph used in computational complexity theory and graph theory» (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q25304863 Autori: i contributori di Wikipedia (cronologia: https://fr.wikipedia.org/wiki/Graphe_de_Frankl-R%C3%B6dl?action=history). Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza. Estratto dell'introduzione non modificato nel contenuto; revisione 226744411, consultata il 2026-11-08T03:07:39.016Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: b88cae52f12fd32c23ab86f67aab92c6424b19feb2fa41523e870874e689bf4d