Metraipolis › archive › dc_359b3a26dc24

Coloration gloutonne — Wikipedia (fr)

Source
Wikipedia (fr)
Original
https://fr.wikipedia.org/wiki/Coloration_gloutonne
License (as archived)
CC-BY-SA-4.0
Archived
2026-11-05T06:58:54.328Z
SHA-256 of the archived text
468609041b64f8d97344407c31ee73036a6e726e61a85a8e2f050ca990bc242c
Stable URL of this page
https://metraipolis.com/documento/dc_359b3a26dc24

How to cite

Coloration gloutonne — Wikipedia (fr) — Wikipedia (fr), https://fr.wikipedia.org/wiki/Coloration_gloutonne (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_359b3a26dc24 (Metraipolis archive dc_359b3a26dc24, sha256 468609041b64f8d97344407c31ee73036a6e726e61a85a8e2f050ca990bc242c)
BibTeX
@misc{dc359b3a26dc24,
  title = {Coloration gloutonne — Wikipedia (fr)},
  howpublished = {Wikipedia (fr)},
  url = {https://fr.wikipedia.org/wiki/Coloration_gloutonne},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_359b3a26dc24; sha256 468609041b64f8d97344407c31ee73036a6e726e61a85a8e2f050ca990bc242c},
  year = {2026}
}

Archived text

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

Dans l'étude des problèmes de coloration de graphes en mathématiques et en informatique, une coloration gloutonne ou coloration séquentielle est une coloration des sommets d'un graphe obtenue par un algorithme glouton qui examine les sommets du graphe en séquence et attribue à chaque sommet la première couleur disponible. Les colorations gloutonnes peuvent être obtenues en temps linéaire, mais elles n'utilisent en général pas le nombre minimum possible de couleurs. Différents choix pour la suite des sommets produisent généralement des colorations différentes du graphe donné. Une grande partie de l'étude des colorations gloutonnes porte donc sur la façon de trouver un bon ordre. Il existe toujours un ordre qui produit une coloration optimale, et même si l'on trouve aisément pour de nombreuses classes particulières de graphes, ils sont difficiles à trouver en général. Les stratégies couramment utilisées pour l'ordre des sommets impliquent de choisir les sommets de degré élevé avant les sommets de degré inférieur, ou de choisir des sommets avec moins de couleurs disponibles de préférence aux sommets qui sont moins contraints. Des variantes de coloration gloutonne consistent à choisir les couleurs par un algorithme online, donc sans connaissance de la structure de la partie non colorée du graphe, ou de choisir d'autres couleurs que la première couleur disponible afin de réduire le nombre total de couleurs. Des algorithmes de coloration gloutonne ont été appliqués à des problèmes d'ordonnancement et d'allocation de registres, à l'analyse de jeux combinatoires et aux preuves d'autres résultats mathématiques, notamment le théorème de Brooks sur la relation entre coloration et degré. D'autres concepts de théorie des graphes dérivés des colorations gloutonnes incluent le nombre de Grundy d'un graphe (le plus grand nombre de couleurs que l'on peut trouver dans une coloration gloutonne), et les graphes bien colorés, qui sont les graphes pour lesquels toutes les colorations gloutonnes utilisent le même nombre de couleurs.

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 «Coloration gloutonne» — https://fr.wikipedia.org/wiki/Coloration_gloutonne
Wikidata Q5601715: «tipo di colorazione dei grafi» (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q5601715
Autori: i contributori di Wikipedia (cronologia: https://fr.wikipedia.org/wiki/Coloration_gloutonne?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 239623816, consultata il 2026-11-05T06:53:35.010Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 7b7ee465a64983fec44c61431da2d97d3e3b02c98fd5b446e46355c1710634db