Metraipolis › archive › dc_8ea1e4afad06

Graphe à seuil — Wikipedia (fr)

Source
Wikipedia (fr)
Original
https://fr.wikipedia.org/wiki/Graphe_%C3%A0_seuil
License (as archived)
CC-BY-SA-4.0
Archived
2026-11-08T03:11:50.804Z
SHA-256 of the archived text
b25050b49e01dd27c73eb4c9a13cd4bbfdb88175d80b41d590b4255a69e730e7
Stable URL of this page
https://metraipolis.com/documento/dc_8ea1e4afad06

How to cite

Graphe à seuil — Wikipedia (fr) — Wikipedia (fr), https://fr.wikipedia.org/wiki/Graphe_%C3%A0_seuil (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_8ea1e4afad06 (Metraipolis archive dc_8ea1e4afad06, sha256 b25050b49e01dd27c73eb4c9a13cd4bbfdb88175d80b41d590b4255a69e730e7)
BibTeX
@misc{dc8ea1e4afad06,
  title = {Graphe à seuil — Wikipedia (fr)},
  howpublished = {Wikipedia (fr)},
  url = {https://fr.wikipedia.org/wiki/Graphe_%C3%A0_seuil},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_8ea1e4afad06; sha256 b25050b49e01dd27c73eb4c9a13cd4bbfdb88175d80b41d590b4255a69e730e7},
  year = {2026}
}

Archived text

Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (fr), https://fr.wikipedia.org/wiki/Graphe_%C3%A0_seuil. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

En théorie des graphes, un graphe à seuil est un graphe qui peut être construit, en partant d'un graphe à un seul sommet, par application répétée d'une des deux opérations suivantes : Ajout d'un sommet isolé au graphe. Ajout d'un sommet dominant au graphe, c'est-à-dire d'un sommet connecté à tous les autres sommets. Par exemple, le graphe de la figure ci-contre est un graphe de seuil : il peut être construit en commençant par un graphe à un seul sommet (sommet 1), puis en ajoutant les sept autres dans l'ordre dans lequel ils sont numérotés, les sommets noirs comme sommets isolés et les sommets rouges comme sommets dominants. Les graphes à seuil ont été introduits par Chvátal et Hammer en 1977 . Un chapitre sur les graphes à seuil apparaît dans le livre de Golumbic de 1980, et le livre de Mahadev et Peled de 1995 leur est consacré. Comme le notent Diaconis, Holmes et Janson, parmi les 64 graphes étiquetés à 4 sommets, il y a 46 graphes à seuil ; les 18 autres sont des chaînes à 4 sommets (notés P4), des cycles à 4 sommets (notés C4) et leurs compléments qui sont des paires d'arêtes (notés 2K2). Si on considère les graphes non étiquetés, il y a 11 graphes à 4 sommets, dont 8 sont des graphes à seuil.

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 à seuil» — https://fr.wikipedia.org/wiki/Graphe_%C3%A0_seuil
Wikidata Q943345: «graph that can be constructed with a sequence of operations that add either an isolated vertex or a dominating vertex» (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q943345
Autori: i contributori di Wikipedia (cronologia: https://fr.wikipedia.org/wiki/Graphe_%C3%A0_seuil?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 239368166, consultata il 2026-11-08T03:08:35.721Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 3253aa7d6c975c69f9a03132f7fc3b0880f6a4833f1d7dafd134f7b323d9c7e9