Aller au contenu

Exercice : Coloration d'un graphe⚓︎

Le problème

Vous pouvez voir ci-contre une carte de France représentant les 12 régions métropolitaines (sans la Corse pour des raisons de simplification du problème).

On se demande s'il est possible de colorier la carte en respectant les contraintes suivantes :

  • utiliser un minimum de couleurs ;
  • faire en sorte que deux régions limitrophes (ayant une frontière commune) soient coloriées de deux couleurs différentes.

La figure ci-contre utilise 12 couleurs, une par région ; on peut faire mieux. Il y a des solutions optimales à 4 couleurs, d'autres qui s'en approchent. Nous allons voir plusieurs algorithmes.

Modélisation

Pour tenter de résoudre ce problème, nous n'allons pas travailler directement sur la carte, mais sur un graphe associé à celle-ci.

Chaque région sera un sommet du graphe et, si deux régions sont limitrophes, il existera alors une arête entre ces deux sommets. Pour nommer les sommets nous utiliserons les codes suivants :

Étiquette Identifiant Région
0 BRE Bretagne
1 PLO Pays de Loire
2 NAQ Nouvelle Aquitaine
3 OCC Occitanie
4 PAC Provence-Alpes-Côte d'Azur
5 ARA Auvergne-Rhône-Alpes
6 BFC Bourgogne Franche-Comté
7 CVL Centre-Val de Loire
8 IDF Île de France
9 GES Grand-Est
10 HDF Hauts-de-France
11 NOR Normandie

Partie I : Implémentation du graphe⚓︎

1. Représentez sur votre copie le graphe correspondant à la carte "Régions de France" en utilisant les identifiants pour les sommets.

Réponse 
flowchart TB
    HDF --- NOR
    HDF --- IDF
    HDF --- GES
    NOR --- BRE
    NOR --- PLO
    NOR --- CVL
    NOR --- IDF
    IDF --- CVL
    IDF --- BFC
    GES --- IDF
    GES --- BFC
    BRE --- PLO
    PLO --- NAQ
    PLO --- CVL
    CVL --- NAQ
    CVL --- ARA
    CVL --- BFC
    BFC --- ARA
    NAQ --- OCC
    NAQ --- ARA
    ARA --- OCC
    ARA --- PAC
    PAC --- OCC

2. Une des possibilités pour représenter un graphe \(G\) en machine est d'utiliser ce qu'on appelle une matrice d'adjacence. Dans ce type de représentation, les sommets sont ordonnés et considérés comme étiquetés par des entiers de \(0\) à \(n − 1\), où \(n\) est l'ordre du graphe.

2.a. Quel est l'ordre du graphe « Régions de France » ?

Réponse

Il y a douze régions. L'ordre de ce graphe est donc 12.

2.b. On considère un graphe dont la matrice d'adjacence est modélisée en Python par la liste de listes donnée ci-dessous :

🐍 Script Python
M = [
    [0, 1, 0, 1],
    [1, 0, 1, 0],
    [0, 1, 0, 1],
    [1, 0, 1, 0],
]

Dessiner ce graphe sur votre copie. Les sommets sont étiquetés dans cet ordre par \(0\), \(1\), \(2\), \(3\).

Réponse 
flowchart TB
0 --- 1
0 --- 3
1 --- 2
3 --- 2

2.c. Écrire en python une fonction voisins telle que voisins(M, k) renvoie une liste contenant les voisins du sommet k dans le graphe \(G\) modélisé par la matrice d'adjacence M. Par exemple avec la matrice définie ci-dessus, on a :

🐍 Console Python
>>> voisins(M, 2)
[1, 3]
Réponse
🐍 Script Python
def voisins(M, k):
    voisins_k = []
    for i in range(len(M)):
        if M[k][i] == 1:
        voisins_k.append(i)
    return voisins_k

Variante avec une liste en compréhension :

🐍 Script Python
def voisins(M, k):
    return [i for i in range(len(M)) if M[k][i] == 1]

Variante avec un style un peu plus fonctionnel

🐍 Script Python
def voisins(M, k):
    return [i for i, lien in enumerate(M[k]) if lien == 1]

2.d. Combien d'éléments (0 ou 1) y a-t-il dans la matrice d'adjacence d'un graphe qui comporte \(1~000\) sommets ?

Réponse

Il y a \(1~000\) lignes de \(1~000\) éléments ; il y a donc un million d'éléments.

3. On peut également modéliser, en Python, un graphe grâce à un dictionnaire contenant pour chaque clé (un sommet) la valeur associée : une liste de ses voisins, sans se soucier de l'ordre.

3.a. En considérant le graphe représenté ci-dessous, donner un dictionnaire G Python modélisant ce graphe avec un dictionnaire de listes de voisins.

Graphe 1

flowchart LR
    A(A)
    B(B)
    C(C)
    D(D)
    E(E)
    F(F)
    A --- D
    A --- C
    C --- D
    D --- B
    C --- E
    B --- E
    E --- F

On pourra écrire, par exemple, que les voisins de 'A' sont 'C' et 'D'.

Réponse
🐍 Script Python
G = {
    "A": ["C", "D"],
    "B": ["D", "E"],
    "C": ["A", "D", "E"],
    "D": ["A", "B", "C"],
    "E": ["B", "C", "F"],
    "F": ["E"],
}

3.b. Écrire en python une fonction voisins telle que voisins(G, k) renvoie une liste contenant les voisins du sommet k dans le graphe qui est modélisé par le dictionnaire G de listes de voisins. On aura, avec l'exemple précédent, et sans tenir compte de l'ordre :

🐍 Console Python
>>> voisins(G, 'C')
['A', 'D', 'E']
Réponse
🐍 Script Python
def voisins(G, k):
    return G[k]

3.c. Combien d'éléments y a-t-il dans ce dictionnaire si le graphe comporte \(1~000\) sommets ?

Réponse

Il y aura \(1~000\) clés, et chacune est associée à une liste qui contient de \(0\) à \(999\) éléments.

  • Pour un graphe creux (peu dense), c'est très avantageux.
  • Pour un graphe dense, ce n'est pas avantageux.

Partie II : Coloration séquentielle ; un premier algorithme⚓︎

Une première approche pour colorer le graphe est de prendre ses sommets les uns après les autres afin de leur affecter une couleur, tout en veillant à ce que deux sommets adjacents n'aient jamais la même couleur : c'est l'algorithme de coloration séquentielle. Nous modéliserons le graphe avec un dictionnaire Python en listes de voisins. On propose le code ci-dessous qui utilise la fonction voisins programmée à la question précédente :

Code 1
def coloration(G) :
    """Renvoie une coloration du graphe G"""
    # version séquentielle, limitée à 6 couleurs

    couleur = ['Rouge', 'Bleu', 'Vert', 'Jaune', 'Noir', 'Blanc']
    coloration_sommets = {s_i: None for s_i in G}
    for s_i in G:
        couleurs_voisins_s_i = [coloration_sommets[s_j] for s_j in voisins(G, s_i)]
        k = 0
        while couleur[k] in couleurs_voisins_s_i:
            k = k + 1
        coloration_sommets[s_i] = couleur[k]
    return coloration_sommets

1. À Quelle famille d'algorithme appartient le Code 1 ci-dessus ?

Réponse

Il s'agit d'un algorithme glouton, il choisit la première couleur disponible et ne remet pas en cause son choix ensuite, même s'il n'est pas optimal.

2. Donner les couleurs que va attribuer ce code à chaque sommet si l'on considère le Graphe 1 ci-dessus. On considère que la boucle principale va envisager les sommets dans l'ordre lexicographique : tout d'abord A, puis B, puis C ...

Réponse

Pour les sommets :

  • A, le choix est rapide : Rouge ;
  • B, le choix est également rapide : Rouge ;
  • C, le Rouge est indisponible, le choix est Bleu ;
  • D, Rouge et Bleu sont indisponibles, le choix suivant est Vert ;
  • E, Rouge et Bleu sont indisponibles, le choix suivant est Vert ;
  • F, Vert est indisponible, le premier choix Rouge est validé.

Conclusion

Sommet Couleur
A Rouge
B Rouge
C Bleu
D Vert
E Vert
F Rouge 
flowchart LR
    A(A)
    B(B)
    C(C)
    D(D)
    E(E)
    F(F)
    A --- D
    A --- C
    C --- D
    D --- B
    C --- E
    B --- E
    E --- F
    style A fill:#f00,stroke:#000,stroke-width:2px,color:#000
    style B fill:#f00,stroke:#000,stroke-width:2px,color:#000
    style F fill:#f00,stroke:#000,stroke-width:2px,color:#000
    style C fill:#00f,stroke:#000,stroke-width:2px,color:#000
    style D fill:#0f0,stroke:#000,stroke-width:2px,color:#000
    style E fill:#0f0,stroke:#000,stroke-width:2px,color:#000

On suppose que la version de Python est au moins 3.7 ce qui permet d'avoir l'assurance que le dictionnaire est parcouru dans l'ordre de création des clés.

truc

TODO : image vide !!!

3. On modélise maintenant un nouveau graphe avec le dictionnaire G_2 ci-dessous, et on appelle la fonction coloration avec ce graphe en paramètre. Représentez ce graphe sur votre copie et montrez qu'il existe une solution avec moins de couleurs.

🐍 Console Python
>>> G_2 = {"A": ["C"], "B": ["D"], "C": ["A", "D"], "D": ["B", "C"]}
>>> coloration(G_2)
{'A': 'Rouge', 'B': 'Rouge', 'C': 'Bleu', 'D': 'Vert'}
Réponse 
flowchart LR
A(A)
B(B)
C(C)
D(D)
A --- C
D --- B
C --- D
style A fill:#f00,stroke:#000,stroke-width:2px,color:#000
style B fill:#f00,stroke:#000,stroke-width:2px,color:#000
style C fill:#00f,stroke:#000,stroke-width:2px,color:#000
style D fill:#0f0,stroke:#000,stroke-width:2px,color:#000

On peut proposer une coloration avec seulement deux couleurs :

Sommet Couleur
A Rouge
B Bleu
C Bleu
D Rouge 
flowchart LR
A(A)
B(B)
C(C)
D(D)
A --- C
D --- B
C --- D
style A fill:#f00,stroke:#000,stroke-width:2px,color:#000
style D fill:#f00,stroke:#000,stroke-width:2px,color:#000
style B fill:#00f,stroke:#000,stroke-width:2px,color:#000
style C fill:#00f,stroke:#000,stroke-width:2px,color:#000

Partie III : L'algorithme de Welsh et Powell⚓︎

Il s'agit maintenant d'utiliser l'algorithme de coloration séquentiel avec un ordre judicieux, en vue d'obtenir une coloration valide la plus « acceptable » possible. L'algorithme de Welsh et Powell consiste ainsi à colorer séquentiellement le graphe en visitant les sommets par ordre de degré décroissant. L'idée est que les sommets ayant beaucoup de voisins sont plus difficiles à colorer : il faut les colorier en premier.

On rappelle que le degré d'un sommet est le nombre d'arêtes issues de ce sommet, c'est-à-dire son nombre de voisins.

1. On souhaite implémenter en Python une fonction tri_sommets telle que tri_sommets(G) renvoie la liste des étiquettes des sommets du graphe G passé en paramètre triés par degrés décroissants.

Recopiez les lignes incomplètes de code en les complétant.

Code 2
def tri_sommets(G) :
    """Renvoie la liste des sommets, triée par degré décroissant"""
    sommets = [sommet for sommet in G]
    for i in range(...):
        i_sommet_max = i
        degre_sommet_max = len(G[sommets[i]])
        for j in range(..., len(sommets)):
            if len(G[sommets[j]]) > degre_sommet_max:
                i_sommet_max = ...
                degre_sommet_max = ...
        tmp = sommets[i]
        sommets[i] = sommets[i_sommet_max]
        sommets[i_sommet_max] = ...
    return sommets
Réponse
Code 2
def tri_sommets(G) :
    """Renvoie la liste des sommets, triée par degrés décroissants"""
    sommets = [sommet for sommet in G]
    for i in range(len(sommets)):
        i_sommet_max = i
        degre_sommet_max = len(G[sommets[i]])
        for j in range(i + 1, len(sommets)):
            if len(G[sommets[j]]) > degre_sommet_max:
                i_sommet_max = j
                degre_sommet_max = len(G[sommets[j]])
        tmp = sommets[i]
        sommets[i] = sommets[i_sommet_max]
        sommets[i_sommet_max] = tmp
    return sommets

2. Quel type de tri est implémenté dans la fonction tri_sommets dans le Code 2 ci-dessus ?

Réponse

Il s'agit d'un tri par sélection : on cherche le plus grand élément dans le tableau qui reste à trier et on le sélectionne pour être échangé au début de la section à trier, on poursuit avec le reste du tableau.

3. Citer un exemple de tri plus efficace en temps que celui du Code 2.

Réponse

Parmi les tris efficaces dans le pire des cas, il y a le tri fusion, ou le tri par tas.

⚠ le tri rapide est rapide en moyenne, mais pas dans le pire des cas.

4. Quelle sera la liste renvoyée par l'appel de fonction tri_sommets(R) où on passe en paramètre le dictionnaire R : pour chaque région, la liste des régions voisines, réalisé à la question 1 de la partie I (cf. code ci-dessous) ?

🐍 Script Python
R = {}
R["BRE"] = ["PLO", "NOR"]
R["PLO"] = ["BRE", "NAQ", "CVL", "NOR"]
R["NAQ"] = ["PLO", "OCC", "ARA", "CVL"]
R["OCC"] = ["NAQ", "PAC", "ARA"]
R["PAC"] = ["OCC", "ARA"]
R["ARA"] = ["NAQ", "OCC", "PAC", "BFC", "CVL"]
R["BFC"] = ["ARA", "CVL", "IDF", "GES"]
R["CVL"] = ["PLO", "NAQ", "ARA", "BFC", "IDF", "NOR"]
R["IDF"] = ["BFC", "CVL", "GES", "HDF", "NOR"]
R["GES"] = ["BFC", "IDF", "HDF"]
R["HDF"] = ["IDF", "GES", "NOR"]
R["NOR"] = ["BRE", "PLO", "CVL", "IDF", "HDF"]

Remarque

À partir de Python 3.7, lorsque l'on itère sur les clés d'un dictionnaire, l'itération se fait dans l'ordre de création des clés. On se placera dans ce cadre de travail.

Réponse
🐍 Console Python
>>> tri_sommets(R)
['CVL', 'ARA', 'IDF', 'NOR', 'PLO', 'BFC', 'NAQ', 'GES', 'HDF', 'OCC', 'PAC', 'BRE']

5. Quelles modifications doit-on apporter à l'algorithme séquentiel (Code 1) pour implémenter l'algorithme de Welsh-Powell ? Vous ne recopierez pas toute la fonction, mais vous signalerez les lignes que vous insérez et celles que vous modifiez.

Réponse
🐍 Script Python
def coloration(G) :
    """Renvoie une coloration du graphe G"""
    # Algorithme de Welsh-Powell, limité à 6 couleurs

    couleur = ['Rouge', 'Bleu', 'Vert', 'Jaune', 'Noir', 'Blanc']
    coloration_sommets = {s_i: None for s_i in G}
    for s_i in tri_sommets(G):
        couleurs_voisins_s_i = [coloration[s_j] for s_j in voisins(G, s_i)]
        k = 0
        while couleur[k] in couleurs_voisins_s_i:
            k = k + 1
        coloration_sommets[s_i] = couleur[k]
    return coloration_sommets

6. Donnez alors la couleur attribuée à chaque région par votre fonction.

Réponse

Dans l'ordre d'attribution finale, on a :

id Région Couleur
CVL Rouge
ARA Bleu
IDF Bleu
NOR Vert
PLO Bleu
BFC Vert
NAQ Vert
GES Rouge
HDF Jaune
OCC Rouge
PAC Vert
BRE Rouge