Coloration des arêtes d'un graphe
En théorie des graphes et en algorithmique, une coloration des arêtes d'un graphe consiste à attribuer à chaque arête une couleur, en évitant que deux arêtes ayant une extrémité commune soient de la même couleur.
La figure ci-contre est un exemple de coloration d'arêtes correcte. On vérifie en effet qu'aucun sommet n'est commun à deux arêtes de même couleur. On remarquera qu'ici, il n'aurait pas été possible de colorer les arêtes du graphe avec seulement deux couleurs.
Définition
modifierMentionnée sans précision supplémentaire, l'expression « coloration des arêtes d'un graphe » désigne le fait d'attribuer à chaque arête une couleur, de sorte que deux arêtes adjacentes (c'est-à-dire ayant une extrémité commune) n'aient jamais la même couleur. (C'est une notion duale de celle de coloration des sommets d'un graphe.)
Le nombre minimal de couleurs nécessaire pour réaliser la coloration des arêtes d'un graphe G est appelé indice chromatique de G ou nombre chromatique des arêtes de G et noté χ′(G), ou parfois χ1(G). Il ne doit pas être confondu avec le nombre chromatique (des sommets) de G, noté χ(G).
Propriétés
modifierSi Δ(G) est le degré maximum de G et μ(G) sa multiplicité (le nombre maximum d'arêtes par paire de sommets), alors :
- χ′(G) = 1 si et seulement si G est un couplage.
- χ′(G) ≥ Δ(G).
- χ′(G) ≤ Δ(G) + 1 (théorème de Vizing).
- χ′(G) ≤ Δ(G) + μ(G), où G peut être un multigraphe.
- χ′(G) = Δ(G) dès que G est un graphe biparti (théorème de Kőnig sur les graphes bipartis).
- χ′(G) = Δ(G) dès que G est un graphe simple planaire tel que Δ(G) ≥ 7 (cf. section suivante).
Classification des graphes et détermination de leur nombre chromatique
modifierComme énoncé ci-dessus, χ′(G) est toujours égal à Δ(G) ou à Δ(G) + 1. G est dit de classe 1 dans le premier cas et de classe 2 dans le second.
En 1981, Holyer a prouvé[1] que la détermination de l'appartenance d'un graphe simple à l'une ou l'autre de ces deux classes est un problème NP-complet. Cependant, pour certains cas particuliers, il existe des règles permettant de conclure rapidement.
Par exemple, Vizing a établi[2] qu'un graphe simple planaire de degré maximum au moins égal à 8 est toujours de classe 1, et conjecturé qu'il en était de même pour un degré maximum égal à 6 ou 7 (on connaît des graphes simples planaires de degré maximum 2, 3, 4 ou 5 et de classe 2). Sanders (en) et Zhao[3] ont démontré le cas Δ(G) = 7 de sa conjecture.
Cette conjecture trouve une application dans celle de la coloration totale (en).
Applications
modifierLa coloration des arêtes des graphes complets peut être utilisée pour programmer un tournoi toutes rondes en aussi peu de rondes que possible, de sorte que chaque paire de concurrents s'affronte dans l'une des rondes. Dans cette application, les sommets du graphe correspondent aux concurrents du tournoi, les arêtes correspondent aux jeux et les couleurs des arêtes correspondent aux rondes dans lesquels les jeux sont joués[4].
Une autre application peut être la planification de la fabrication d'un ensemble d’objets avec la contrainte que chaque tâche de fabrication doit être exécutée sur une machine spécifique, empêchant toute autre tâche nécessitant la même machine d’être exécutée en même temps. Si toutes les tâches ont la même durée, alors ce problème peut être formalisé en tant que coloration d'un multigraphe bipartite, dans lequel les sommets d'un côté de la bipartition représentent les objets à fabriquer, les sommets de l'autre côté de la bipartition représentent les machines de fabrication, les arêtes représentent les tâches à exécuter et les couleurs représentent les intervalles de temps dans lesquels chaque tâche peut être effectuée[5].
Notes et références
modifier- (en) Ian Holyer, « The NP-completeness of edge-coloring », SIAM J. Comput., vol. 10, no 4, , p. 718-720 (DOI 10.1137/0210055).
- (ru) V. G. Vizing, « Critical graphs with given chromatic class », Metody Diskret. Analiz., vol. 5, 1965, p. 9-17.
- (en) Daniel P. Sanders et Yue Zhao, « Planar graphs of maximum degree seven are class I », J. Combin. Theory Ser. B, vol. 83, no 2, , p. 201-212 (DOI 10.1006/jctb.2001.2047).
- E. Burke, D. De Werra et J. Kingston, « 5.6.5 Sports Timetabling », dans J. L. Gross et J. Yellen (éditeurs), Handbook of Graph Theory, CRC Press, , 1192 p. (ISBN 978-1-58488-090-5, lire en ligne), p. 462
- D. P. Williamson, L. A. Hall, J. A. Hoogeveen, C. A. J. Hurkens, J. K. Lenstra, S. V. Sevast'janov et D. B. Shmoys, « Short shop schedules », Operations Research, vol. 45, , p. 288–294 (DOI 10.1287/opre.45.2.288, JSTOR 171745, MR 1644998)
Bibliographie
modifier- (en) Tommy R. Jensen et Bjarne Toft, Graph Coloring Problems, John Wiley & Sons, (1re éd. 1995), 320 p. (ISBN 978-1-118-03074-5, lire en ligne)
- (de) Dénes Kőnig, « Über Graphen und ihre Anwendung auf Determinantentheorie und Mengenlehre », Mathematische Annalen, vol. 77, no 4, , p. 453-465 (DOI 10.1007/BF01456961, lire en ligne [archive du ], consulté le )
