Aller au contenu

Coloration gloutonne

Un article de Wikipédia, l'encyclopédie libre.
Deux colorations gloutonnes du même graphe couronne pour des ordres différents sur les sommets. La numérotation de droite se généralise aux graphes bicolores à n sommets, et l'algorithme glouton utilise n/2 couleurs.

Dans l'étude des problèmes de coloration de graphes en mathématiques et en informatique, une coloration gloutonne ou coloration séquentielle[1] 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.

Algorithme[modifier | modifier le code]

La coloration gloutonne pour un ordre de sommets donné peut être calculée par un algorithme qui s'exécute en temps linéaire. L'algorithme traite les sommets dans l'ordre donné, en attribuant une couleur à chacun au fur et à mesure qu'il est traité. Les couleurs peuvent être représentées par les entiers et chaque sommet reçoit la couleur qui est le plus petit entier qui n'est pas déjà utilisé par l'un de ses voisins. Pour trouver la plus petite couleur disponible, on peut utiliser un tableau qui compte le nombre de voisins de chaque couleur (ou qui représente l'ensemble des couleurs des voisins), puis parcourir le tableau pour trouver l'indice de sa première valeur nulle[2].

En langage Python, l'algorithme peut être exprimé sous la forme suivante : 

def first_available(color_list):
  """Calcule le plus petit entier naturel qui n'est pas dans la liste des couleurs."""
  color_set = set(color_list)
  count = 0
  while True:
    if count not in color_set:
      return count
    count += 1

def greedy_color(G, order):
  """Détermine la coloration gloutonne de G pour l'ordre donné. 
  La représentation de G est supposée être comme dans https://www.python.org/doc/essays/graphs/
  et doit permettre les parcours des voisins d'un sommet par une boucle de la forme "for w in G[node]".
  La valeur calculée est un dictionnaire qui associe à chaque sommet sa couleur."""
  color = dict()
  for node in order:
    used_neighbour_colors = [color[nbr] for nbr in G[node]
                            if nbr in color]
    color[node] = first_available(used_neighbour_colors)
  return color

La procédure first_available prend un temps proportionnel à la longueur de sa liste d'arguments, car il effectue deux boucles, une sur la liste elle-même et une sur une liste des couleurs de même longueur. Le temps global de l'algorithme de coloration est dominé par les appels à ce sous-programme. Chaque arête du graphe contribue à un seul de ces appels, celui de l'extrémité de l'arête qui se trouve le plus loin dans l'ordre des sommets. Par conséquent, la somme des longueurs des listes d'arguments jusqu'à first_available et le temps total de l'algorithme sont proportionnels au nombre d'arêtes du graphe.

Un autre algorithme, produisant la même coloration[3], consiste à déterminer les ensembles de sommets de même couleur, une couleur à la fois. Dans cette méthode, chaque classe de couleur est calculée en examinant les sommets dans l'ordre donné. Lorsque ce parcours rencontre un sommet non coloré qui n'a pas de voisin dans , on ajoute à . De cette façon, devient un stable maximal parmi les sommets qui n'ont pas encore reçu des couleurs plus petites. L'algorithme trouve ainsi itérativement les classes de couleurs jusqu'à ce que tous les sommets soient colorés. Cependant, cette méthode demande plusieurs parcours du graphe, un parcours pour chaque classe de couleur, au lieu de la méthode décrite ci-dessus qui n'utilise qu'un seul parcours[4].

Choix de l'ordre[modifier | modifier le code]

Des ordres différents pour les sommets d'un graphe peuvent conduire la coloration gloutonne à utiliser des nombres différents de couleurs, allant du nombre optimal de couleurs à, dans certains cas, un nombre de couleurs proportionnel au nombre de sommets du graphe. Par exemple, un graphe couronne (qui est un graphe formé de deux ensembles disjoints de n/2 sommets {a1, a2, ... } et {b1, b2, ... } avec une arête entre ai à bj chaque fois qui i ≠ j ) peut être un cas particulièrement mauvais pour la coloration gloutonne : avec l'ordre des sommets a1, b1, a2, b2, ..., une coloration gloutonne utilise n/2 couleurs, une couleur pour chaque paire (ai, bi). Cependant, le nombre optimal de couleurs pour ce graphe est de deux, une couleur pour les sommets ai et une autre pour les sommets bi[5]. Il existe aussi des graphes tels qu'avec une probabilité élevée, un ordre de sommets choisi au hasard conduit à un nombre de couleurs beaucoup plus grand que le minimum[6]. Par conséquent, il importe de choisir avec soin l'ordre des sommets pour une coloration gloutonne.

Bons ordres[modifier | modifier le code]

Les sommets d'un graphe peuvent toujours être ordonnés de telle sorte que l'algorithme glouton produise une coloration optimale ; en effet, étant donné une coloration optimale, on peut ordonner les sommets par leurs couleurs puis, lorsqu'on utilise un algorithme glouton avec cet ordre, la coloration résultante est automatiquement optimale[7]. Cependant, parce que la coloration optimale d'un graphe est un problème NP-complet, tout sous-problème qui permettrait de résoudre ce problème rapidement, y compris la recherche d'un ordre optimal pour la coloration gloutonne, est NP-difficile[8].

Dans les graphes d'intervalles et les graphes cordaux, si les sommets sont ordonnés dans l'ordre opposé de l'ordre d'élimination parfait, alors les voisins précédent chaque sommet forment une clique. Cette propriété a pour effet que la coloration gloutonne produit une coloration optimale, car elle n'utilise jamais plus de couleurs qu'il n'en faut pour chacune de ces cliques. Un ordre d'élimination peut être trouvé en temps linéaire, lorsqu'il existe[9].

Mieux encore, tout ordre d'élimination parfait est héréditairement optimal, ce qui signifie qu'il est optimal à la fois pour le graphe lui-même et pour tous ses sous-graphes induits. Les graphes parfaitement ordonnables (qui incluent les graphes cordaux, les graphes de comparabilité et les graphes à distance héréditaire) sont par définition les graphes qui ont un ordre héréditairement optimal[10]. Reconnaître qu'un graphe est parfaitement ordonnable est également NP-complet[11].

Ordre mauvais[modifier | modifier le code]

Article détaillé : nombre de Grundy.

Le nombre de couleurs produites par la coloration gloutonne pour le plus mauvais des ordres d'un graphe donné est appelé son nombre de Grundy[12]. Trouver un bon ordre des sommets pour une coloration gloutonne est difficile, et il en est de même pour trouver un mauvais ordre des sommets. Il est NP-complet de déterminer, pour un graphe donné G et un nombre k, s'il existe un ordre des sommets de G qui force l'algorithme glouton à utiliser au moins k couleurs. En particulier, cela signifie aussi qu'il est difficile de trouver le plus mauvais ordre pour G[12].

Graphes où l'ordre est non pertinent[modifier | modifier le code]

Les graphes bien colorés (en) sont les graphes pour lesquels toutes les colorations de sommets produisent le même nombre de couleurs. Dans ces graphes, ce nombre est égal à la fois au nombre chromatique et au nombre de Grundy[12]. Ces graphes incluent les cographes, qui sont exactement les graphes dans lesquels tous les sous-graphes induits sont bien colorés[13]. Cependant, il est co-NP-complet de déterminer si un graphe est bien coloré[12].

Si un graphe aléatoire est tiré selon le modèle d'Erdős-Rényi (en) avec une probabilité constante pour l'inclusion de chaque arête, alors tout ordre des sommets choisi indépendamment des arêtes du graphe conduit à une coloration dont le nombre de couleurs est proche du double de la valeur optimale avec grande probabilité. On ne sait pas s'il existe une méthode en temps polynomial pour trouver des colorations sensiblement meilleures pour ces graphes[3].

Dégénérescence[modifier | modifier le code]

Le prisme triangulaire et l'anti-prisme carré sont des graphes pour lesquels la coloration gloutonne avec l'ordre dégénéré donne un nombre de couleurs plus grand que le nombre optimal.

Comme il est difficile de trouver un ordre optimal des sommets, des heuristiques ont été utilisées pour tenter de réduire le nombre de couleurs sans garantir un nombre optimal de couleurs. Un ordre couramment utilisé pour la coloration gloutonne est de choisir un sommet v de degré minimum, d'ordonner récursivement le sous-graphe sans le sommet v, puis de re placer v comme dernier dans l'ordre. Le plus grand des degrés d'un sommet supprimé que cet algorithme rencontre est appelé la dégénérescence du graphe, et est notée d. Dans le contexte de la coloration gloutonne, la même stratégie d'ordonnancement est également appelée « ordre avec le plus petit en dernier »[14]. Cet ordre des sommets et la dégénérescence peuvent être calculés en temps linéaire[15]. Il peut être considéré comme une version améliorée d'une méthode antérieure appelée la « stratégie du plus grand d'abord » qui trie les sommets dans l'ordre décroissant de leurs degrés[16].

Avec l'ordre de dégénérescence, la coloration gloutonne utilise au plus d + 1 couleurs. En effet, chaque sommet, lorsqu'il est coloré, a au plus d voisins déjà colorés, donc l'une des d + 1 couleurs est libre pour son utilisation. La coloration gloutonne avec l'ordre de dégénérescence peut trouver des colorations optimales pour certaines classes de graphes, y compris les arbres, les pseudo-forêts et les graphes en couronne [17]. Markossian, Gasparian & Reed (1996)[18] définissent un graphe comme étant -parfait si, pour et chaque sous-graphe induit de , le nombre chromatique est égal à la dégénérescence plus un. Pour ces graphes, l'algorithme glouton avec l'ordre de dégénérescence est toujours optimal[19]. Tout graphe -parfait doit être un graphe sans trou pair, car les cycles pairs ont un nombre chromatique égal à deux et une dégénérescence égale à deux, et ne satisfont pas à l'égalité dans la définition des graphes -parfaits. Si un graphe et son graphe complémentaire sont tous les deux sans trou pair, ils sont tous les deux -parfaits. Les graphes qui sont à la fois des dgraphes parfaits et -parfaits sont exactement les graphes cordaux. Sur les graphes sans trou pair plus généralement, l'ordre de dégénérescence se rapproche de la coloration optimale à au plus le double du nombre optimal de couleurs : son rapport d'approximation est de 2[18]. Sur les graphes de disques unitaires, son rapport d'approximation est de 3[20]. Le prisme triangulaire est le plus petit graphe pour lequel l'un de ses ordres de dégénérescence conduit à une coloration non optimale, et le l'antiprisme carré est le plus petit graphe qui ne peut pas être coloré de manière optimale en utilisant l'un de ses ordres de dégénérescence[17].

Ordres adaptatifs[modifier | modifier le code]

Brélaz (1979) propose une stratégie, qu'il appelle DSatur, pour l'ordonnancement des sommets dans la coloration gloutonne qui intercale la construction de l'ordonnancement avec le processus de coloration. Dans sa version de l'algorithme de coloration gloutonne, le sommet suivant à colorier à chaque étape est celui qui a le plus grand nombre de couleurs distinctes dans son voisinage. En cas d'égalité, un sommet de degré maximal dans le sous-graphe des sommets non colorés est choisi parmi les sommets liés. En gardant la trace des ensembles de couleurs voisines et de leurs cardinalités à chaque étape, il est possible d'implémenter cette méthode en temps linéaire.

Cette méthode permet de trouver les colorations optimales pour les graphes bipartis[21],, les graphes cactus, les graphes roues, les graphes à au plus six sommets, et presque tous les graphes -colorables[22]. Lévêque et Maffray[23] ont affirmé en 2005 que cette méthode permet aussi de trouver des colorations optimales pour les graphes de Meyniel (en), mais ils ont plus tard trouvé un contre-exemple[23].

Autres schémas de sélection de couleurs[modifier | modifier le code]

Il est possible de définir des variantes de l'algorithme de coloration gloutonne dans lesquelles les sommets du graphe donné sont colorés séquentiellement mais dans lesquels la couleur choisie pour chaque sommet n'est pas nécessairement la première couleur disponible. Ces variantesiincluent des méthodes dans lesquelles la partie non colorée du graphe est inconnue de l'algorithme, ou dans lesquelles l'algorithme dispose d'une certaine liberté pour faire des choix de coloration meilleurs que ne le ferait l'algorithme glouton de base.

Sélection en ligne[modifier | modifier le code]

Des variantes de stratégies de sélection de couleurs ont été étudiées dans le cadre des algorithmes en ligne. Dans ce cas, les sommets d'un graphe sont présentés un par un dans un ordre arbitraire à un algorithme de coloration ; l'algorithme ne peut choisir une couleur pour chaque sommet uniquement sur la base des couleurs et des contiguïtés parmi les sommets déjà traités. Dans ce contexte, on mesure la qualité d'une stratégie de sélection de couleurs par son rapport de compétitivité qui est le rapport entre le nombre de couleurs qu'il utilise et le nombre optimal de couleurs pour le graphe donné[24].

Sans autre restriction sur le graphe, le rapport de compétitivité optimal n'est que légèrement sous-linéaire[25]. Pour les graphes d'intervalles, un ratio constant est possible[26], tandis que pour les graphes bipartis et les graphes creux, un rapport logarithmique peut être atteint. En effet, pour les graphes creux, la stratégie standard de coloration gloutonne qui consiste à choisir la première couleur disponible permet d'atteindre ce rapport compétitif, et il est possible de prouver une limite inférieure correspondante sur le rapport compétitif de tout algorithme de coloration en ligne[24].

Coloration parcimonieuse[modifier | modifier le code]

Une coloration parcimonieuse, pour un graphe et un ordre des sommets donnés, est par définition une coloration produite par un algorithme glouton qui colorie les sommets dans l'ordre donné, et qui n'introduit une nouvelle couleur que lorsque toutes les couleurs précédentes sont adjacentes au sommet donné, mais l'algorithme peut choisir laquelle des couleurs utiliser (au lieu de toujours choisir la plus petite) lorsqu'il est capable de réutiliser une couleur existante. Le nombre chromatique ordonné est le plus petit nombre de couleurs que l'on peut obtenir de cette manière pour l'ordonnancement donné, et le nombre ochromatique est le plus grand nombre chromatique ordonné parmi toutes les colorations de sommets d'un graphe donné. Malgré sa définition différente, le nombre ochromatique est toujours égal au nombre de Grundy[27].

Applications[modifier | modifier le code]

La coloration gloutonne, comme elle est rapide et, dans de nombreux cas, n'utilise que peu de couleurs, peut être utilisée dans des applications où une coloration bonne sans être optimale est souhaitée. L'une des premières applications de l'algorithme glouton concerne des problèmes tels que l'ordonnancement des travaux, dans lequel une collection de tâches doit être affectée à un ensemble donné de créneaux horaires, en évitant que des tâches incompatibles ne soient affectées au même créneau horaire[4]. Elle peut aussi être utilisée dans les compilateurs pour l'allocation de registres, en l'appliquant à un graphe dont les sommets représentent les valeurs à affecter aux registres et dont les arêtes représentent les conflits entre deux valeurs qui ne peuvent être affectées au même registre[28]. Dans de nombreux cas, ces graphes d'interférence sont des graphes cordaux, ce qui permet de produire une affectation optimale des registres par coloration gloutonne[29].

En théorie des jeux combinatoires, pour un jeu impartial donné sous la forme d'un graphe acyclique orienté dont les sommets représentent les positions du jeu et les arêtes les mouvements valides d'une position à l'autre, l'algorithme de coloration gloutonne (utilisant l'inverse d'un ordre topologique du graphe) calcule la valeur de Nim de chaque position. Ces valeurs peuvent être utilisées pour déterminer le jeu optimal dans tout jeu unique ou toute somme disjonctive de jeux[30].

Pour un graphe de degré maximal Δ, toute coloration gloutonne utilise au plus Δ + 1 couleurs. Le théorème de Brooks dit qu'à deux exceptions près, à savoir des cliques et des cycles impairs, au plus Δ couleurs sont nécessaires. Une preuve du théorème de Brooks consiste à trouver un ordonnancement des sommets dans lequel les deux premiers sommets sont adjacents au dernier sommet sans être adjacents entre eux, et tel que chaque sommet autre que le dernier a au moins un voisin suivant. Pour un tel ordonnancement, l'algorithme de coloration glouton utilise au plus Δ couleurs[31].

Notes et références[modifier | modifier le code]

  1. ↑ Mitchem (1976).
  2. ↑ Hoàng et Sritharan 2016, Theorem 28.33, p. 738 ; Husfeldt 2015, Algorithm G
  3. ↑ a et b Frieze et McDiarmid (1997).
  4. ↑ a et b Welsh et Powell (1967).
  5. ↑ Johnson 1974 ; Husfeldt 2015.
  6. ↑ Kučera 1991 ; Husfeldt 2015.
  7. ↑ Husfeldt (2015).
  8. ↑ Maffray (2003).
  9. ↑ Rose, Lueker et Tarjan (1976).
  10. ↑ Chvátal 1984 ; Husfeldt 2015.
  11. ↑ Middendorf et Pfeiffer (1990).
  12. ↑ a b c et d Zaker (2006).
  13. ↑ Christen et Selkow (1979).
  14. ↑ Mitchem 1976 ; Husfeldt 2015.
  15. ↑ Matula et Beck (1983).
  16. ↑ Welsh et Powell 1967 ; Husfeldt 2015.
  17. ↑ a et b Kosowski et Manuszewski (2004).
  18. ↑ a et b Markossian, Gasparian et Reed (1996).
  19. ↑ Markossian, Gasparian et Reed 1996 ; Maffray 2003.
  20. ↑ Gräf, Stumpf et Weißenfels (1998).
  21. ↑ Brélaz (1979).
  22. ↑ Janczewski et al. (2001).
  23. ↑ a et b Lévêque et Maffray (2005).
  24. ↑ a et b Irani (1994).
  25. ↑ Lovász, Saks et Trotter 1989 ; Vishwanathan 1992.
  26. ↑ Kierstead et Trotter (1981).
  27. ↑ Simmons 1982 ; Erdős et al. 1987.
  28. ↑ Poletto et Sarkar 1999. Poletto et Sarkar décrivent leur méthode d'allocation de registres comme n'étant pas basée sur la coloration de graphes, mais elle semble être la même que la coloration gloutonne.
  29. ↑ Pereira et Palsberg (2005).
  30. ↑ Décrit par exemple dans la section 1.1 de Nivasch 2006.
  31. ↑ Lovász (1975).

Bibliographie[modifier | modifier le code]

Ce document provient de « https://fr.wikipedia.org/w/index.php?title=Coloration_gloutonne&oldid=210166189 ».