La coloration des graphes consiste à attribuer des couleurs à certains éléments d'un graphe (sommets ou arêtes) en respectant des contraintes d'adjacence.

Ce problème, bien qu'élégant sur le plan mathématique, trouve des applications concrètes dans de nombreux domaines :

Planification temporelle : élaboration d'emplois du temps (examens, cours) sans chevauchement.
Télécommunications : attribution de fréquences radio sans interférence.
Gestion des ressources : allocation optimale de ressources partagées (processeurs, mémoires).
Cartographie : coloriage de cartes géographiques avec des régions frontalières de couleurs différentes.

Coloration des sommets

Définition - Coloration propre Soit \(G = (S, A)\) un graphe non orienté. Une coloration des sommets est une application \[ c: S \rightarrow \{1, 2, \dots, k\} \] telle que : \[ \forall \{u, v\} \in A, \quad c(u) \ne c(v) \] On parle alors de coloration propre.

Exemple de graphe

Un graphe peut être colorié en attribuant une couleur différente à chacun de ses sommets. Cependant, pour la plupart des graphes, on peut trouver une coloration utilisant un nombre de couleurs inférieur au nombre de sommets du graphe.

Quel est le nombre minimal de couleurs nécessaire ?

Définition - Nombre chromatique Le nombre chromatique de \(G\), noté \(\chi(G)\), est le plus petit entier \(k\) (nombre de couleurs) pour lequel une coloration propre à \(k\) couleurs existe.

Exemples fondamentaux de coloration

Graphe sans arêtes

Définition Un graphe sans arêtes est un graphe \(G=(S, A)\) tel que \(A=\varnothing\).

Proposition \[ \chi(G) = 1 \qquad \forall S \ne \varnothing \]

Preuve Puisqu'aucune paire de sommets n'est adjacente, une unique couleur peut être attribuée à tous les sommets sans violer la condition de coloration propre. Une couleur est nécessaire et suffisante.

Les Arbres

Proposition Tout arbre \(T\) non réduit à un seul sommet est 2-coloriable, donc \[ \chi(T) = 2 \]

Preuve Soit \(r \in S\) un sommet choisi comme racine.

Pour tout \(v \in S\), on note \(d(r,v)\) la distance (longueur du plus court chemin) entre \(r\) et \(v\).

On définit la coloration \(c\) par : \[ c(v) = \begin{cases} 1 & \text{si } d(r,v) \equiv 0 \pmod{2},\\ 2 & \text{si } d(r,v) \equiv 1 \pmod{2}. \end{cases} \] Par définition d'un arbre, deux sommets adjacents \(u\) et \(v\) vérifient nécessairement \(|d(r,u) - d(r,v)| = 1\). Ils sont donc de parités différentes et reçoivent des couleurs distinctes. La coloration est donc propre.

Exemple d'arbre bicolorié

Les cycles (\(C_n\))

Proposition Soit \(C_{2k}\) un cycle de longueur paire. \[ \chi(C_{2k}) = 2 \] La preuve est identique à celle de l'arbre (coloration alternée le long du cycle).

Proposition Soit \(C_{2k+1}\) un cycle de longueur impaire. \[ \chi(C_{2k+1}) = 3 \]

Preuve Supposons qu'il existe une 2-coloration. En parcourant le cycle \(\{v_1, v_2, \dots, v_n\}\), les couleurs doivent alterner \((1,2,1,2\dots)\).

Pour un cycle de longueur impaire, \(v_n\) recevrait la couleur \(1\), mais comme \(v_n\) est adjacent à \(v_1\) (déjà de couleur 1), la coloration n'est pas propre. Donc \(\chi(G) > 2\).

Ainsi, deux couleurs sont insuffisantes, mais trois suffisent (il suffit de colorer \(v_n\) avec une troisième couleur pour lever le conflit).

Graphes complets

Proposition Le graphe complet \(K_n\) possède \(n\) sommets, tous adjacents deux à deux. \[ \chi(K_n) = n \]

Preuve Par définition de \(K_n\), tout sommet est adjacent à tous les autres. L'ensemble des sommets forme une clique. Si deux sommets \(u\) et \(v\) recevaient la même couleur, la coloration ne serait pas propre car \((u,v) \in A\).

Il faut donc au moins autant de couleurs que de sommets. En attribuant une couleur différente à chaque sommet, on obtient une coloration propre.

Exemple de graphe complet \(K_4\)

Remarque Le graphe complet représente la "densité maximale" ; c'est le pire cas pour un algorithme de coloration.

Graphes bipartis

ThéorèmePour un graphe G non vide, les assertions suivantes sont équivalentes :

G est biparti.
G est 2-coloriable (\(\chi(G) \le 2\)).
G ne contient aucun cycle impair.

Preuve

(1) ⇔ (2) : Immédiat par définition. Les classes de couleurs \(X\) et \(Y\) d'une 2-coloration forment les deux ensembles de la partition.
(2) ⇒ (3) : Par contraposée. Si G contient un cycle impair, nous avons vu que ce cycle nécessite au moins 3 couleurs. Donc G ne peut être 2-coloriable.
(3) ⇒ (2) : En supposant G connexe sans perte de généralité. On fixe un sommet \(r\) et on colorie par distance par rapport à \(r\) (parité). L'absence de cycle impair garantit qu'aucune arête ne relie deux sommets à la même distance (ce qui créerait un cycle de longueur \(2d+1\)).

Coloration gloutonne

Algorithme glouton simple

Comme trouver le nombre chromatique exact est un problème NP-complet (très difficile pour de grands graphes), on utilise souvent une approche gloutonne :

On choisit un ordre des sommets \(v_1, v_2, \dots, v_n\).
On parcourt les sommets dans cet ordre.
Pour chaque sommet \(v_i\), on lui attribue la plus petite couleur possible qui n'est pas déjà utilisée par ses voisins déjà colorés.

Remarque Le résultat dépend fortement de l'ordre des sommets. Un mauvais ordre peut conduire à un nombre de couleurs bien supérieur à \(\chi(G)\).

Exemple de coloration gloutonne

On considère le graphe \(G\) suivant et on applique l'algorithme glouton simple afin de déterminer une coloration propre, en suivant l'ordre des sommets \((A, D, B, E, C, F)\).

Application pas à pas

Nous utilisons les couleurs : 1 (bleu), 2 (vert), 3 (orange), 4 (jaune), etc.

Sommet A : Aucun voisin n'est encore coloré. On lui attribue la couleur 1.
Sommet D : Aucun voisin n'est encore coloré. On lui attribue également la couleur 1.
Sommet B : Il est adjacent à \(D\) (couleur 1) mais pas à \(A\). On lui attribue la couleur 2.
Sommet E : Il est adjacent à \(A\) (couleur 1), mais pas à \(B\) ni à \(D\). La plus petite couleur disponible est donc la 2.
Sommet C : Il est adjacent à \(D\) (couleur 1) et à \(E\) (couleur 2). La plus petite couleur disponible est la 3.
Sommet F : Il est adjacent à \(A\) (couleur 1) et à \(B\) (couleur 2). La plus petite couleur disponible est la 3.

Cependant, \(\chi(G) = 2\) car il s'agit d'un graphe biparti.

Implémentation

Coloration gloutonne Python

def coloration_gloutonne(M, ordre=None):
    n = len(M)
    
    # Si aucun ordre n'est spécifié, on utilise l'ordre naturel (0, 1, 2...)
    if ordre is None:
        ordre = list(range(n))

    # Initialisation : tous les sommets ont la couleur 0 (aucune couleur)
    couleurs = [0] * n

    # On traite chaque sommet un par un selon l'ordre défini
    for v in ordre:
        # 1. Identifier les couleurs déjà utilisées par les voisins de v
        interdites = set()
        for u in range(n):
            # Si u est voisin de v ET que u a déjà une couleur
            if M[v][u] != 0 and couleurs[u] != 0:
                interdites.add(couleurs[u])

        # 2. Chercher la plus petite couleur (1, 2, 3...) non interdite
        c = 1
        while c in interdites:
            c += 1
        
        # 3. Assigner la couleur trouvée au sommet v
        couleurs[v] = c

    # On retourne le dictionnaire des couleurs et le nombre maximum de couleurs utilisées
    return couleurs, max(couleurs) if couleurs else 0

Test Python

M = [
    [0,0,0,0,1,1],  # A (0)
    [0,0,0,1,0,1],  # B (1)
    [0,0,0,1,1,0],  # C (2)
    [0,1,1,0,0,0],  # D (3)
    [1,0,1,0,0,0],  # E (4)
    [1,1,0,0,0,0],  # F (5)
]

col_g, k_g = coloration_gloutonne(M, [0, 3, 1, 4, 2, 5])
print(f"Couleurs : {col_g}")
print(f"nb couleurs = {k_g}")

Sortie

Couleurs : [1, 2, 3, 1, 2, 3]
nb couleurs = 3

Algorithme de Welsh-Powell

L'algorithme de Welsh-Powell améliore l'approche gloutonne classique de coloration des graphes en adoptant une stratégie de tri des sommets par degré décroissant.

L'idée est de colorer en priorité les sommets de plus haut degré, car ce sont les plus contraignants : leurs nombreuses adjacences réduisent fortement le choix des couleurs disponibles. En les traitant en premier, on limite les conflits ultérieurs et on obtient généralement une coloration utilisant moins de couleurs.

Étapes principales :

Trier les sommets par ordre de degré décroissant.
Pour une couleur donnée \(k\) :
1. Choisir le premier sommet non coloré de la liste et lui attribuer la couleur \(k\).
2. Parcourir ensuite la liste et attribuer la même couleur \(k\) à tous les sommets :
  - non encore colorés,
  - non adjacents à un sommet déjà coloré en \(k\).
3. Lorsqu'aucun autre sommet ne peut recevoir la couleur \(k\), passer à la couleur \(k+1\).

Exemple avec Welsh-Powell

Reprenons le graphe \(G\) précédent. Tous les sommets ayant le même degré (2), l'algorithme de Welsh-Powell les traite simplement dans l'ordre décroissant des étiquettes.

L'ordre des sommets est donc \((F, E, D, C, B, A)\).

Application pas à pas

Couleur 1 (bleu):
- Premier sommet non coloré : \(F \implies c(F) = 1\).
- On parcourt la liste et on attribue la couleur 1aux sommets non adjacents à \(F\) :
  - E : non adjacent à \(F \implies c(E) = 1\).
  - D : non adjacent à \(F \implies c(D) = 1\).
  - C : adjacent à \(D\) et \(E\) (déjà couleur 1) → interdit.
  - B : adjacent à \(D\) et \(F\) (couleur 1) → interdit.
  - A : adjacent à \(E\) et \(F\) (couleur 1) → interdit.
- \(\{D, E, F\}\) → Couleur 1
Couleur 2 (vert):
- Premier sommet non coloré : \(C \implies c(C) = 2\).
- On attribue la couleur 2aux sommets non adjacents à \(C\) :
  - B : non adjacent à \(C \implies c(B) = 2\).
  - A : non adjacent à \(C \implies c(A) = 2\).
- \(\{A, B, C\}\) → Couleur 2

Cette coloration utilise exactement \(\chi(G) = 2\) couleurs : il s'agit donc de la solution optimale.

Implémentation

Algorithme de Welsh-Powell Python

def welsh_powell(M):
    n = len(M)

    # 1. Calcul du degré de chaque sommet
    # On compte le nombre de voisins (entrées non nulles dans la matrice d'adjacence)
    deg = [sum(1 for j in range(n) if M[i][j] != 0) for i in range(n)]

    # 2. Détermination de l'ordre de traitement
    # On trie les indices des sommets par degré décroissant (-deg[v]).
    # En cas d'égalité, on utilise l'indice (v) pour garantir un tri stable.
    ordre = sorted(range(n), key=lambda v: (-deg[v], v))

    # Initialisation des couleurs (0 = non coloré) et du compteur de couleurs (k)
    couleurs = [0] * n
    k = 0

    # 3. Processus de coloration par "vagues"
    for v in ordre:
        # Si le sommet est déjà coloré, on passe au suivant
        if couleurs[v] != 0:
            continue

        # Sinon, on commence une nouvelle "vague" avec une nouvelle couleur
        k += 1
        couleurs[v] = k

        # On parcourt les sommets restants pour voir s'ils peuvent aussi porter la couleur k
        for u in ordre:
            if couleurs[u] == 0:
                # Un sommet u est compatible si aucun de ses voisins ne porte déjà la couleur k
                compatible = True
                for w in range(n):
                    if M[u][w] != 0 and couleurs[w] == k:
                        compatible = False
                        break
                
                if compatible:
                    couleurs[u] = k

    return couleurs, k, ordre

Test Python

col_g, k_g, ordre = welsh_powell(M)
print(f"Couleurs : {col_g}")
print(f"nb couleurs = {k_g}")
print(f"Ordre de traitement : {ordre}")

Sortie

Couleurs : [1, 1, 1, 2, 2, 2]
nb couleurs = 2
Ordre de traitement : [0, 1, 2, 3, 4, 5]

Analyse de complexité

Algorithme glouton simple : \(O(n^2)\) où \(n\) est le nombre de sommets.
Algorithme de Welsh-Powell : \(O(n^2 \log n)\) dû au tri initial.
Problème général : La détermination exacte du nombre chromatique est NP-complet.

Récapitulatif des nombres chromatiques

Type de graphe	Nombre chromatique \(\chi(G)\)
Graphe sans arêtes	1
Arbre	2
Cycle pair (\(C_{2k}\))	2
Cycle impair (\(C_{2k+1}\))	3
Graphe biparti	2
Graphe complet (\(K_n\))	\(n\)

Sortie

// La sortie apparaîtra ici…

Prêt · Ctrl+Entrée pour exécuter

Discussion (0)

Soyez le premier à laisser un commentaire !

Laisser un commentaire

Votre commentaire sera visible après modération.

Structures de données

Algorithmes

Programmation

Bases de données

CPGE

Modules informatique

Coloration des graphes