Coloration, cliques et stables

Problème : nombre chromatique

Le problème de coloriage de graphes, pour un graphe G non orienté, consiste à attribuer une couleur à chaque sommet de telle sorte qu’une même couleur ne soit pas attribuée à deux sommets adjacents.

Lorsque le graphe est planaire, cela revient au problème de coloriage d’une carte géographique.

Le nombre minimum de couleur nécessaire pour colorier le graphe G est appelé nombre chromatique de G, et est noté X(G).

Le problème de trouver le nombre chromatique d’un graphe est un problème Np-complet. Le problème de coloriage d’un graphe avec un nombre limité de couleurs – est-il possible de colorier le graphe avec x couleurs, si oui comment ? – est lui aussi un problème Np-complet.

Un graphe planaire est au plus 4-chromatique.

Une chaîne est au plus 2-chromatique.

Un cycle est au plus 3-chromatique.

Une clique de taille n est n-chromatique.

Problème : cliques

Étant donnés un graphe non orienté G, une clique est un sous-ensemble de sommets qui sont tous connectés deux à deux par des arêtes. En d’autre terme, il s’agit d’un sous-graphe complet.

Trouver une clique w d’ordre k dans un graphe est un problème Np-complet.

Le graphe suivant possède une clique d’ordre 5 :

grapheclique

Problème : stables

Étant donné un graphe non orienté G, un stable  est un sous-ensemble de sommets qui ne sont pas connectés deux à deux par des arêtes. Trouver un stable d’ordre k revient à trouver une clique d’ordre k dans le graphe inverse, c’est-à-dire qu’il possède une arête si elle n’existe pas dans le graphe d’origine, et inversement.

Trouver une stable a d’ordre k dans un graphe est un problème Np-complet.

280px-independent_set_graph-svg

Relation entre les trois problèmes et heuristiques

Nous avons les trois propositions suivantes :

  • a(G)=w(non G)
  • w(G) = a(non G)
  • X(G) >= w(G)

Un stable S de G est dit maximal par inclusion s’il n’existe pas de stable S’ de G tel que S soit strictement contenu dans S’. Une clique K est maximale par inclusion s’il n’existe pas de cliques K’ de G tel que K soit strictement contenu dans K’.

Par cette définition, on en déduit qu’un stable d’ordre maximum est aussi un stable maximal par inclusion, la réciproque n’est pas vrai. L’heuristique classique pour obtenir un stable de grande taille est de chercher un stable maximal par inclusion.

stable2

L’algorithme de Brélaz est un algorithme glouton qui permet de connaître une borne maximale du nombre chromatique d’un graphe. Son principe est simple et procède de façon itérative.

Tant qu’il existe un sommet non colorié, nous choisissons le sommet non colorié ayant le plus grand nombre de voisins coloriés avec des couleurs différentes. Ce sommet est alors colorié avec la plus petite couleur possible (les couleurs sont triées dans un ordre croissant arbitraire). Si toutes les couleurs existantes sont déjà utilisées par un voisin, on ajoute une nouvelle couleur à notre palette (ajout d’une couleur d’une valeur supérieur à toutes les autres existantes).

La notion de stable peut aussi fournir des indications sur la coloration d’un graphe. En effet, nous pouvons supposer que dans un stable, tous les sommets possèdent la même couleur. La coloration en k couleurs revient à trouver une partition de l’ensemble des sommets en k stables.

L’algorithme de Welsh et Powell se base sur cette proposition :

  1. Classer les sommets du graphe dans l’ordre décroissant de leur degré
  2. En parcourant la liste dans l’ordre, attribuer une couleur non utilisée au premier sommet non colorié p, et attribuer cette couleur à chaque sommet suivant non colorié tel qu’il ne soit pas adjacent au sommet p.
  3. Revenir à 2 s’il reste des sommets non coloriés dans la liste. Sinon renvoyer la liste.
Publicités