Aller au contenu

Autours de la coloration de graphes⚓︎

L'épreuve n°2 du sujet 0 de la future Agrégation externe d'Informatique (2022) dont vous pouvez télécharger le sujet au format PDF est une étude du problème de coloration de graphes, appliqué à l'ordonnancement de tâches.

Des graphes, de la manipulation, de la visualisation, tous les ingrédients pour utiliser pygraph.

Nous vous proposons d'explorer le 56 questions de ce sujet. Pour certaines questions concernant la NP-complétude aucune garantie sur l'exactitude des réponses données : mes souvenirs de DEA sont loin.

Le notebook de cet article est disponible ici au téléchargement (pensez à télécharger pygraph aussi)

1 Ordonnancement de tâches⚓︎

1.1 Représentations des ensembles de tâches⚓︎

Ci-dessous deux exemples du sujet de représentations graphiques d'ensembles de tâches :

ensembles de tâches

Liste d'intervalles de l'exemple \(T_1\) :

T1 = [(9, 11), (0, 4), (1, 7), (14, 19), (3, 12), (13, 15), (8, 17)]
Q1

La liste de l'exemple \(T_2\)

T2 = [(5, 12), (13, 15), (0, 2), (1, 4), (3, 7), (10, 14), (8, 11), (6, 9)]
Q2
  • Pour les tâches de \(T_1\), on peut constater 3 groupes de tâches 2 à 2 disjointes : \((t_2, t_6)\), \((t_4, t_5)\) et \((t_1, t_0, t_3)\) on ne peut pas faire mieux puisque par exemple pour \(x = 10\) on a : \(x\in t_0\) et \(x\in t_4\) et \(x\in t_6\) ; il nous faut donc 3 machines a minima
  • Pour les tâches de \(T_2\), le minimum est également 3 et le groupement suivant fonctionne : \((t_2, t_4, t_6)\), \((t_3, t_5, t_7)\) et \((t_0, t_1)\).

Le sujet introduit la notion d'événement : (date, indice, debut-ou-fin) Les événements pour \(T_1\) sont donnés :

Ev1  =  [(0, 1, 0), (1, 2, 0), (3, 4, 0), (4, 1, 1), (7, 2, 1), (8, 6, 0), 
        (9, 0, 0), (11, 0, 1), (12, 4, 1), (13, 5, 0), (14, 3, 0), (15, 5, 1), 
        (17, 6, 1), (19, 3, 1)]
Q3

Les 7 premiers événements pour \(T_2\) :

REP3 = [(0, 2, 0), (1, 3, 0), (2, 2, 1), (3, 4, 0), (4, 3, 1), (5, 0, 0), (6, 7, 0)]
Q4

La fonction formate qui, à partir d'une liste d'intervalles retourne la liste triée par ordre croissant des événements :

Code
def inserer(liste, i, elt):
    while i >= 0 and liste[i] > elt:
        liste[i+1] = liste[i]
        i -= 1
    liste[i+1] = elt

def formate(intervalles):
    evenements = [None] * 2*len(intervalles)
    i = -1
    for indice, (debut, fin) in enumerate(intervalles):
        inserer(evenements, i, (debut, indice, 0))
        i += 1
        inserer(evenements, i, (fin, indice, 1))
        i += 1
    return evenements

Exemples

>>> formate(T1)
[(0, 1, 0), (1, 2, 0), (3, 4, 0), (4, 1, 1), (7, 2, 1), (8, 6, 0), 
(9, 0, 0), (11, 0, 1), (12, 4, 1), (13, 5, 0), (14, 3, 0), (15, 5, 1), 
(17, 6, 1), (19, 3, 1)]

On peut vérifier notre réponse à la question 3 :

>>> Ev2 = formate(T2)
>>> Ev2[:7] == REP3
True
Q5

La fonction formate est un tri par sélection : on crée une liste pour accueillir les \(2n\) événements correspondants aux \(n\) intervalles. Puis, pour chaque intervalle \(I\) on insère deux événements dans la liste triée des \(k\) premiers événements déjà placés. A partir du \(n^e\) événement, dans le pire des cas, la fonction insere sera amenée à tout décaler vers la droite, effectuant donc de l'ordre de \(n^2\) opérations élémentaires. \(\square\)

1.2 Calcul du nombre maximum de tâches simultanées⚓︎

On appelle \(\cal{K}(T)\) le ombre maximum de tâches simultanément en cours d'exécution. Par exemple \(\cal{K}(T_1) = 3\).

Q6

On a \(\cal{K}(T_2) = 3\)

Q7

Il s'agit d'écrire une fonction qui calcule \(\cal{K}(T)\).

def nb_simultanees(evts):
    max_simul = 0
    nb_simul = 0
    for date, indice, debut_fin in evts:
        if debut_fin == 0:
            nb_simul += 1
            if nb_simul > max_simul:
                max_simul = nb_simul
        else:
            nb_simul -= 1
    return max_simul
Q8

L'invariant est : à chaque début de boucle for la variable max_simul représente le nombre maximum de tâches qui on été exécutées simultanément à la date date.

L'invariant est vrai en entrant dans la boucle : aucune tâche n'a commencé, et donc on a bien 0 tâche en simultanée.

Supposons qu'on soit à un tour quelconque de boucle, la date est date et max_simul représente le maximum de tâches qui ont été exécutées simultanément à une date inférieure à date. Si l'événement qu'on explore est un début de tâche (debut_fin vaut 0) alors on va incrémenter nb_simul qui représente le nombre de tâches en cours simultanément. Et si ce nombre dépasse max_simul on met à jour max_simul ; si on explore un événement de fin de tâche, alors on décrémente nb_simul qui ne peut donc pas dépasser max_simul et effectivement une tâche se terminant, on en a une de moins en cours d'exécution.

Dans tous les cas, à l'amorce du prochain passage, max_simul représente toujours le nombre maximum de tâches qui ont été exécutées simultanément. \(\square\)

Exemple

>>> nb_simultanees(Ev1)
3

1.3 Calcul d'un ordonnancement optimal⚓︎

On s'intéresse à l'algorithme suivant :

En s'inspirant du calcul du nombre maximum de tâches simultanées, on peut écrire un algorithme glouton qui calcule un ordonnancement pour un ensemble \(T\) de tâches donné.

Pour cela, on parcourt la liste triée des événements : à chaque fois que l'on rencontre un début de tâche, on lui attribue la machine disponible de plus petit indice et cette machine ne sera à nouveau disponible qu'au moment de la date de fin de cette tâche.

Q9

Ordonnancement obtenu pour \(T_2\) :

>>> ORD2 = [1, 0, 0, 1, 0, 2, 0, 2]
Q10
Code
def plus_petite_machine(utilisees):
    for i in range(len(utilisees)):
        if utilisees[i] == 0:
            return i

def ordo_glouton(evts):
    n = len(evts) // 2
    machines_utilisees = [0] * n
    ordo = [-1] * n
    for date, i_tache, debut_fin in evts:
        if debut_fin == 0:
            i_machine = plus_petite_machine(machines_utilisees)
            ordo[i_tache] = i_machine
            machines_utilisees[i_machine] = 1
        else:
            i_machine = ordo[i_tache]
            machines_utilisees[i_machine] = 0
    return ordo

Exemples

>>> ordo_glouton(Ev1)
[1, 0, 1, 2, 2, 1, 0]
>>> ordo_glouton(Ev2) == ORD2
True
Q11

Nous devons prouver que :

  1. une machine attribuée est libre et que c'était la plus petite possible
  2. une tâche qui se termine libère sa machine

Le point 1 est garanti par construction du tableau des machines et la fonction plus_petite_machine qui parcourt les indices de machines en commençant par 0 et qui retourne cet indice dès que la valeur du tableau vaut 0 (signifiant que la machine est libre). Le point 2 est vérifié par le else de la boucle principale de ordo_glouton : dès qu'on croise une date de fin, on libère la machine qui lui était affectée. \(\square\)

Q12

Si l'algorithme n'était pas optimal, cela voudrait dire qu'à un moment, pour un intervalle de tâches \(T\), une \(k+1\)-ième machine a été affectée à une tâche \(t\) alors que \(\cal{K}(T) = k\). Cela signifie qu'une tâche parmi celles qui utilisaient les machines \(0, 1,\ldots k-1\) s'est terminée au moment où \(t\) se lance. Mais alors, d'après le point 2 de la question précédente, la machine \(j < k\) ainsi libérée aurait dûe être affectée à la tâche \(t\) (point 1 de la question précédente). Il y a contradiction, l'hypothèse de départ est donc fausse : l'algorithme est optimal. \(\square\)

Q13

Pour chaque événement, on va parcourir la liste des machines (et il peut y en avoir autant que d'intervalles dans le pire des cas) donc la complexité est quadratique en fonction du nombre d'intervalles. \(\square\)

2 Lien avec les graphes⚓︎

On va utiliser le module pygraph pour continuer à jouer avec ce sujet.

>>> import pygraph

On représente les ensembles d'intervalles par des graphes ; par exemple pour \(T_1\) :

Le graphe pour \(T_1\)
>>> GT1 = pygraph.Graph(7)
>>> GT1.add_edges_from([(0, 4), (0, 6), (1, 4), (1, 2), (5, 6), (5, 3), (3, 6), (2, 4), (4, 6)])
>>> GT1.position([(2, -0.5, 0), (5, 0.5, 0), (1, -2.5, 0), (3, 2.5, 0), (4, -1.5, 1.5), (6, 1.5, 1.5), (0, 0, 3)], 0.5)
>>> GT1.view

GT1

Q14

Le graphe de \(T_2\) :

>>> GT2 = pygraph.Graph(8)
>>> GT2.add_edges_from([(0, 4), (0, 7), (0, 6), (0, 5), (4, 7), (4, 3), (5, 6), (5, 1), (6, 7), (3, 2)])
>>> GT2.position([(0, 0, 0), (4, 1, 0), (3, 2, 0), (2, 3, 0), (5, -1, 0), (1, -2, 0), (7, 0.5, 0.75), (6, -0.5, 0.75)], 0.7)
>>> GT2.view

GT2

Q15

Il s'agit d'écrire une fonction qui, à partir d'une liste d'intervalles construit le graphe associé :

def inter(t1, t2):
    a1, b1 = t1
    a2, b2 = t2
    return a1 < a2 < b1 or a2 < a1 < b2

def liste_vers_graphe(T):
    n = len(T)
    graph = [[] for _ in range(n)]
    for i in range(n):
        for j in range(i+1, n):
            if inter(T[i], T[j]):
                    graph[i].append(j)
                    graph[j].append(i)
    return graph

Exemple

>>> A2 = liste_vers_graphe(T2)
>>> A2
[[4, 5, 6, 7], [5], [3], [2, 4], [0, 3, 7], [0, 1, 6], [0, 5, 7], [0, 4, 6]]
Bonus

Il manque des fonctionnalités à pygraph (une nouvelle version est prévue). Par exemple, le lien avec les listes d'adjacences.

Voici une fonction que nous allons utiliser ; créer un pygraph.Graph depuis une liste de listes d'adjacences :

def liste_adjacence_pygraph(adj):
    n = len(adj)
    g = pygraph.Graph(n)
    for i in range(n):
        for j in adj[i]:
            if j > i:
                g.add_edge(i, j)
    return g

On peut alors retrouver le graphe de \(T_2\) :

>>> G2 = liste_adjacence_pygraph(A2)
>>> G2.same_position_as(GT2)
>>> G2.scale(0.7)
>>> G2.view

GT2

Q16

On considère le graphe suivant :

>>> G3 = pygraph.Graph(5)
>>> G3.add_edges_from([(0, 1), (0, 2), (0, 3), (1, 2), (2, 3), (3, 4)])
>>> G3.position([(0, 0, 0.75), (1, -1, 0), (2, 0, -0.75), (3, 1, 0), (4, 2, 0)], 0.6)
>>> G3.view

G3

Voici une réalisation possible de ce graphe d'intervalles :

    |---t2---|
|---t1---|  |----t3-----|
    |-----t0-------|  |-t4--| 
|--|--|--|--|--|--|--|--|--|--->
0  1  2  3  4  5  6  7  8  9

On considère les graphes cycliques.

Bonus

Une fonction pour créer un pygraph.Graph cyclique d'ordre \(n\) :

def cyclique(n):
g = pygraph.Graph(n)
    for i in range(n):
        g.add_edge(i, (i+1)%n)
    return g
C4

Voici \(C_4\) le graphe cyclique d'ordre 4 :

>>> C4 = cyclique(4)
>>> C4.view

C4

Q17

Soit \(t_0\) et \(t_1\) deux intervalles de temps, avec une intersection non vide. Puisque \(t_2\) doit chevaucher \(t_1\) sans toucher à \(t_0\) alors \(t_1\) doit donc déborder de \(t_0\), disons par la droite (par la gauche le raisonnement reste le même), comme ceci :

    |---t1---|
|---t0---|

Dès lors \(t_2\) vient chevaucher la partie de \(t_1\) qui n'est pas en contact avec \(t_0\) :

        |---t2---|
    |---t1---|
|---t0---|

De même, \(t_3\) doit chevaucher \(t_2\) sans toucher à \(t_1\)... mais en touchant \(t_0\) ce qui n'est pas possible. On pourrait formaliser un peu plus en introduisant les bornes des intervalles : \([d_0, f_0]\), ... \([d_3, f_3]\). On a alors une contradiction sur les inégalités :

\[d_0\lt d_1\lt f_0\lt d_2\lt f_1\lt d_3\lt f_2\]

et

\[d_2\lt f_0\]

\(\square\)

Q18

Le raisonnement de Q17 se généralise pour un cycle d'intervalles \(t_0, t_1\ldots t_{n-1}\) : chaque intervalle \(t_i\) pour \(2\gt i\lt n-1\) chevauche l'intervalle \(t_{i-1}\) mais en ne touchant pas à \(t_{i-2}\) mais \(t_{n-1}\) doit chevaucher \(t_{n-2}\) sans toucher \(t_{n-3}\) qui se trouve plus à gauche, mais en chevauchant \(t_0\) qui lui est complètement à gauche, ce qui est impossible. \(\square\)

Q19

Soit \(G = (S, A)\) un graphe d'intervalles et soit \((S', A')\) un sous graphe induit de \(G\). Soit \(t_i\) et \(t_j\) deux intervalles.

  • Si \(t_i\cap t_j = \emptyset\) alors \((i, j)\notin A\) et donc \((i, j)\notin A'\)
  • Si \(t_i\cap t_j \neq \emptyset\), on considère les deux cas suivants :
    • \(i\notin S'\) ou \(j\notin S'\) alors par construction du graphe induit \((i, j)\notin A'\) et il suffit de ne pas considérer \(t_i\) ou \(t_j\) parmi les intervalles associés au graphe induit pour ne pas avoir d'incohérence ;
    • \(i\in S'\) et \(j\in S'\) et donc \(i\in S\) et \(j\in S\) ; comme \(G\) est un graphe d'intervalles, on a \((i, j)\in A\) et par construction du graphe induit \((i, j)\in A'\)

Réciproquement, si on considère deux sommets \(i\) et \(j\) du graphe induit tel que \((i, j)\in A'\subset S\) alors \((i, j)\in A\) et comme \(G\) est un graphe d'intervalles on a \(t_i\cap t_j \neq \emptyset\). \(\square\)

Q20

Un graphe contenant un cycle de longueur supérieure ou égale à 4 sans corde ne peut pas être un graphe d'intervalles. En effet, car sinon, par le résultat de Q19, le sous graphe induit réduit au graphe cyclique serait un graphe d'intervalles ce qui contredit Q18. \(\square\)

3 Coloration de graphes⚓︎

3.1 Préliminaires⚓︎

\(k\)-coloration

Une \(k\)-coloration d'un graphe \(G = (S, A)\) est une fonction \(c\) de \(S \rightarrow \{0,\ldots k-1\}\) telle que pour toute arète \((s, t)\in A\), \(c(s)\neq c(t)\).

Exemples

Créons le graphe \(G_0\) de l'exemple permettant de montrer un exemple de non coloration et un exemple de coloration.

>>> G0 = pygraph.Graph(6)
>>> G0.add_edges_from([(0, 1), (1, 2), (1, 4), (1, 3), (2, 3), (3, 5), (4, 5)])
>>> G0.position([(1, 0, 0), (0, 0, 1), (2, -1, 0), (4, 1, 0), (3, 0, -1), (5, 1, -1)], 0.6)
>>> G0.view

G0

On peut remplacer les étiquettes des sommets par un numéro de couleur et mettre en avant les deux sommets qui font que ce choix n'est pas une coloration :

>>> G0.set_labels('021113')
>>> G0.label_on()
>>> G0.color_on(2, 'lightblue')
>>> G0.color_on(3, 'lightblue')
>>> G0.view

pas une coloration

On reprend \(G_0\) pour montrer une 4-coloration :

>>> G0b = G0.copy()
>>> G0b.same_position_as(G0)
>>> G0b.scale(0.6)
>>> G0b.set_labels('021013')
>>> G0b.label_on()
>>> G0b.view
4-coloration

\(k\)-colorabilité

Un graphe \(G\) est \(k\)-colorable s'il possède une \(k\)-coloration. \(\chi(G)\) est le nombre chromatique de \(G\) ie le plus petit entier \(k\) tel que \(G\) est \(k\)-colorable.

Q21

\(\chi(G_0) = 3\). Et voici une 3-coloration possible (avec de vraies couleurs) :

>>> G0c = G0.copy()
>>> G0c.same_position_as(G0)
>>> G0c.scale(0.6)
>>> G0c.colorise()
3

Et voici le graphe coloré, avec le numéro des sommets en étiquettes pour pouvoir les nommer :

true-coloration

Dans cette 3-coloration, le sous graphe constitué des sommets 1, 2 et 3 forment un graphe complet. Utiliser 2 couleurs pour ces sommets est impossible. 3 est donc bien le plus petit entier possible pour une coloration. \(\square\)

Q22

On considère la graphe \(G_1\) suivant :

>>> G1 = pygraph.Graph(7)
>>> G1.add_edges_from([(0, 1), (0, 2), (0, 3), (1, 2), (2, 3), (3, 4), (4, 5), (4, 6), (3, 5), (5, 6), (1, 6)])
>>> G1.position([(0, -1, 0.5), (4, 1, 0.5), (3, 0, 0), (2, -2, 0), (5, 2, 0), (1, -1, 1.5), (6, 1, 1.5)], 0.6)
>>> G1.view
G1

Ci-dessous une 4-coloration obtenue via l'algorithme D-Satur. On ne peut pas faire mieux : 2 doit être de couleur différente de 0, 1 et 3... seuls 1 et 3 peuvent être de la même couleur. Cela nous donne 3 couleurs. 4 et 5 ne peuvent avoir la même couleur que 3. Ainsi 1, 4, et 5 couvrent les 3 couleurs, obligeant 6 à une 4e. \(\square\)

G1 coloré

Q23

Déterminer les nombres chromatiques de \(C_n\) et d'un graphe complet.

(a) Soit \(s_1 \rightarrow s_2\rightarrow\ldots \rightarrow s_n\rightarrow s_1\) le graphe \(\cal{C}_n\). Si \(n\) est pair, le graphe est bi-parti : chaque sommet pair est relié à 2 sommets impairs et vice-versa ; 2 couleurs sont alors suffisante. Sinon, le dernier sommet \(n\) impair est lié à un sommet pair (\(n-1\)) et un sommet impair (1). Il faudra donc une 3e couleur. Conclusion \(\chi(\cal{C}_n) = 2 + n\,\mathtt{mod}\,2\). \(\square\)

(b) On appelle \(P(n)\) la propriété suivante : si \(G\) est un graphe complet à \(n\) sommets alors \(\chi(G) = n\). \(P(1)\) est vraie. Montrons que pour tout \(n\), \(P(n) \Rightarrow P(n+1)\). Soit \(G\) le graphe complet à \(n\) sommets, \(n\)-coloré. Ajoutons un \(n+1\)-ième sommet et relions le aux autres pour obtenir un graphe \(G'\) complet à \(n+1\) sommets. Pour colorer ce nouveau sommet je ne peux utiliser une des \(n\) couleurs déjà utilisées par les voisins du noeud, il me faut donc une \(n+1\)-ième couleur. Ainsi \(\chi(G') = n+1\). \(\square\)

Définitions

  • Le degré d'un sommet est le nombre de sommet qui lui sont adjacents.
  • Une clique est un ensemble de sommets 2 à 2 adjacents.
  • Le nombre clique est la taille d'une clique maximale et est notée \(\omega(G)\).
Q24

\({\cal K(T)} = \omega(G_{\cal T})\) (puisque le nombre maximum de machines en marchent simultanément est égal à la taille du plus grand sous graphe complet induit du graphe d'intervalles \(G_{\cal T}\) qui est par définition le nombre clique de \(G_{\cal T}\)). \(\square\)

Q25

Soit \(G\) un graphe connexe. Si on extrait une clique maximale \(G'\) alors \(G'\) est un graphe complet à \(\omega(G)\) sommets et son nombre chromatique \(\chi(G')\) vaut \(\omega(G)\) (Q23b). Puisque \(G'\) est un sous graphe de \(G\), \(\chi(G) \geq \chi(G')\). On a donc :

\[\chi(G) \geq \omega(G)\]

\(\square\)

\(G_1\) est un exemple de graphe pour lequel l'inégalité est stricte : \(\omega(G_1) = 3\) et \(\chi(G_1) = 4\). Si on retire l'arête entre les 2 sommets du haut (1 et 6), on obtient une égalité :

>>> G1b = G1.copy()
>>> G1b.remove_edge(1, 6)
>>> G1b.same_position_as(G1)
>>> G1b.scale(0.6)
>>> G1b.label_off()
>>> G1b.resize(0.12)
>>> G1b.colorise()
>>> G1b.color_on()
>>> G1b.view

G1b coloré

On note \(\Delta(G)\) le degré maximal d'un sommet de \(G\).

Q26

On a \(\chi(G) \leq \Delta(G) + 1\).

Pour \(G_1\) il y a égalité (le degré max est 3 et on a bien 4 couleurs) et pour le graphe \(G_{1b}\) l'inégalité est stricte.

3.2 Calcul du nombre chromatique⚓︎

Q27

Pour un graphe \(G\) à \(n\) sommets, la valeur maximale possible pour \(\chi(G)\) est \(n\). Parce qu'au pire \(G\) est le graphe complet et on a montré qu'alors \(\chi(G) = n\). \(\square\)

Q28

Pour vérifier qu'une coloration en est effectivement une, on parcourt chaque sommet \(s\) de \(G\), puis on vérifie qu'un voisin \(v\) de \(s\) n'a pas la même couleur. Si on tombe sur deux voisins de même couleur on peut arrêter le parcours et renvoyer False. Si on va au bout du parcours on renvoie True.

def est_coloration(G, c):
    n = len(G)
    for s in range(n):
        for v in G[s]:
            if c[s] == c[v]:
                return False
    return True
def est_coloration(G, c):
    n = len(G)
    return all(c[s] != c[v] for s in range(n) for v in G[s])

Exemples

On se donne la liste d'adjacences de \(G_0\) (définit au début des préliminaires) :

>>> AG0 = [[1], [0, 2, 3, 4], [1, 3], [1, 2, 5], [1, 5], [3, 4]]

On peut alors vérifier que la coloration 0, 2, 1, 1, 1, 3 donnée dans les préliminaires n'en est effectivement pas une :

>>> est_coloration(AG0, [0, 2, 1, 1, 1, 3])
False

Mais la 2e si :

>>> est_coloration(AG0, [0, 2, 1, 0, 1, 3])
True
Q29

On incrémente de 1 les valeurs de la liste, en commençant par la dernière et en passant à la précédente si l'incrémentation à fait atteindre la valeur de \(k\), auquel cas on remet cette valeur à 0. On stoppe si la valeur incrémentée est inféieure à \(k\) où s'il s'agit de la première. En renvoie True si on est sur la première valeur et qu'elle a été incrémentée à \(k\) (et donc 0).

def incrementer(c, k):
    for i in range(len(c)-1, -1, -1):
        c[i] += 1
        if c[i] == k:
            c[i] = 0
            if i == 0:
                return True
        else:
            return False
>>> l1 = [2, 1, 0, 2, 2]
>>> incrementer(l1, 3)
False
>>> l1
[2, 1, 1, 0, 0]
>>> l2 = [2, 2, 2, 2, 2]
>>> incrementer(l2, 3)
True
>>> l2
[0, 0, 0, 0, 0]

On peut alors écrire une fonction pour tester de la \(k\)-colorabilité :

Q30
def k_colorable(G, k):
    coloration = [0] * len(G)
    est_k_colorable = est_coloration(G, coloration)
    while not est_k_colorable and not incrementer(coloration, k):
        est_k_colorable = est_coloration(G, coloration)
    return est_k_colorable

Et calculer la nombre chromatique d'un graphe (version naïve) :

Q31
def chi(G):
    for k in range(2, len(G)):
        if k_colorable(G, k):
            return k
>>> chi(AG0)
3
Q32

Comme il a été dit dans l'énoncé, pour un graphe à \(n\) sommets, il y a \(k^n\) colorations possibles des sommets par \(k\) couleurs. Ainsi la fonction k_colorable à une complexité temporelle dans le pire des cas en \({\cal O}(k^n)\). Cette fonction est appelée avec \(k = 2\), puis 3, ... jusqu'à \(n\). Soit une complexité finale en \({\cal O}(n^n)\). \(\square\)

Donc non, en pratique cette fonction n'est pas utilisable :

>>> 20**20
104857600000000000000000000
>>> 50**50
8881784197001252323389053344726562500000000000000000000000000000000000000000000000000

3.3 Problème de décision et NP-complétude⚓︎

Définitions de problèmes

  • Entrée : un graphe \(G\)
  • Question : le graphe \(G\) est-il \(k\)-colorable ?
  • Entrée : un graphe \(G\) et un entier \(k\)
  • Question : le graphe \(G\) est-il \(k\)-colorable ?
Q33
Q34

Réduction de \(h\)-coloration en \(k\)-coloration

Soit deux entiers \(h\leq k\). Soit \(G = (S, A)\) un graphe. On va construire un graphe \(G'\) copie de \(G\) à laquelle au rajoute un graphe complet à \(k - h\) sommets et chacun de ces nouveaux sommets est relié à chacun des sommets de G. Cette construction se fait en temps polynomiale.

  • Si \(G\) est \(h\)-colorable, soit \(C\) une telle coloration. On construit alors la coloration \(C'\) de \(G'\) suivante : pour les sommets de \(G'\) qui sont aussi des sommets de \(G\) on utilise \(C\) (\(h\) couleurs), pour l'extension clique de \(k - h\) sommets on utilise les couleurs \(h + 1, \ldots k\). \(G'\) est donc \(k\)-colorable.

  • Si \(G'\) est \(k\)-colorable. Soit \(C\) une telle coloration. Pour la clique, \(C\) utilise \(k - h\) couleurs et aucune n'est utilisée sur les sommets de \(G\) (puisque par construction ils sont reliés à chacun des sommets utilisant ces \(k - h\) couleurs). Il reste donc \(h\) couleurs pour les sommets de \(G\) qui est donc \(h\)-colorable. \(\square\)

Q35

Un parcours en profondeur, en \({\cal O}(n + m)\)\(n\) est le nombre de sommets et \(m\) le nombre d'arêtes permet de construire une 2-coloration si possible :

def deux_colorable(G):
    a_traiter = [0]
    coloration = [-1] * len(G)
    coloration[0] = 0
    while a_traiter:
        s = a_traiter.pop()
        for v in G[s]:
            if coloration[v] == coloration[s]:
                return False
            elif coloration[v] == -1:
                coloration[v] = 1 - coloration[s]
                a_traiter.append(v)
    return True

Exemple

Le graphe \(C_6\) est 2-colorable :

>>> AC6 = [[4, 5], [3, 5], [3, 4], [1, 2], [0, 2], [0, 1]]
>>> deux_colorable(AC6)
True
>>> C6 = liste_adjacence_pygraph(AC6)
>>> C6.colorise()
>>> C6.view

C6 coloré

Q36

Soit \(G\) un graphe et \(C\) une coloration de \(k\) couleurs, un parcours de \(G\) similaire à celui de la fonction deux_colorable permet de dire si oui ou non \(C\) est une \(k\)-coloration de \(G\). La vérification est polynomiale en \({\cal O}(n + m)\) prouvant que Coloration est bien dans NP. \(\square\)

Définitions

  • un littéral est une variable ou sa négation
  • une clause est une disjonction de littéraux
  • une forme normale conjonctive (FNC) est une conjonction de clauses ; et dans une 3-FNC chaque clause contient exactement 3 littéraux.

Exemple de 3-FNC

\[\varphi_0 = (a \vee b \vee c) \wedge (\bar{a} \vee c \vee \bar{d}) \wedge (b \vee \bar{c} \vee d)\]

Problème 3-SAT

  • Entrée : une formule booléenne \(\varphi\) en 3-FNC
  • Sortie : la formule \(\varphi\) est-elle satisfiable ?

Voici le graphe d'une clause :

>>> GC = pygraph.Graph(9)
>>> GC.add_edges_from([(0,3), (1,4), (2,7), (3,4), (3,5), (4,5), (5,6), (7,6), (6,8), (7,8)])
>>> GC.position([(2, 0, 0), (1, 0, 1), (0, 0, 2), (3, 1.5, 2), (4, 1.5, 1), (5, 2.5, 1.5), (6, 3.5, 1.5), (7, 3.5, 0), (8, 5, 0.75)], 0.6)
>>> GC.view

GC

Le graphe d'une formule \(\varphi\) est le graphe \(G_\varphi\) construit sur le principe ci-dessus, pour chaque clause.

Q37

On considère \(\varphi_1 = (\bar{a} \vee b \vee \bar{c}) \wedge (a \vee b \vee \bar{c}) \wedge (a \vee \bar{b} \vee c)\). Voici \(G_{\varphi_1}\).

On peut construire le graphe avec pygraph... le placement devient un peu délicat :

Graphe de \(\varphi_1\)
>>> PHI1 = pygraph.Graph(24)
>>> PHI1.add_edges_from([(0,1), (0,2), (0,3), (0,4), (0,5), (0,6), (0,7), (0,23),
            (2,3), (4,5), (6,7),
            (2,8), (2,22), (3,10), (4,9), (4,11), (5,12), (6,13), (7,18), (7,20),
            (8,9), (8,14), (9,14), (10,11), (10,15), (11,15), (12,13), (12,16), (13,16),
            (14,17), (15,19), (16,21),
            (17,18), (19,20), (21,22),
            (17,23), (18,23), (19,23), (20,23), (21,23), (22,23),
            (1,23)])
>>> PHI1.position([(23, 0, 0),
      (17,-3,1), (18,-2.5,1), (19,-0.5,1), (20,0.5,1), (21,2,1), (22,3,1),
      (14,-3,1.5), (15,-0.5,1.5), (16,2,1.5),
      (8,-3.5,2), (9,-2.5,2), (10,-1,2), (11,0,2), (12,1.5,2), (13,2.5,2),
      (2,-4,3), (3,-3.5,3), (4,-1.5,3), (5,-1,3), (6,1,3), (7,1.5,3),
      (0,-3,4.5), (1,0.5,4.5)])
>>> PHI1.set_labels('KFaȧbḃcċ               T')
>>> PHI1.label_on()
>>> for s in range(8, 23):
        PHI1.resize(0.12, node_id=s)
>>> PHI1.scale(0.7)
>>> PHI1.view

PHI1

Q38

Soit \(n\) la taille de la 3-FNC \(\varphi\). Alors \(\varphi\) possèdent \(m\) littéral positif avec \(m\lt 3n\). Le nombre de sommets de \(G_\varphi\) sera (par construction) : \(8 + 2m\). Quand au nombre d'arêtes il est de \(3 + 3m + 10n\). Au total on a donc \(11 + 5m + 10n\) éléments de construction quantité inférieure à \(11 + 25n\) justifiant ainsi une construction en temps polynomial. \(\square\)

Q39

On considère la graphe suivant :

>>> G39 = pygraph.Graph(10)
>>> G39.add_edges_from([(0,1), (0,2), (0,3), (0,9), (1,4), (2,5), (4,6), 
                        (5,6), (6,7), (3,8), (7,8), (7,9), (8,9), (4,5)])
>>> G39.position([(0,0,-0.25), (3,1,0.25), (2,1,1), (1,1,2), (4,2,2), (5,2,1), 
                    (6,3,1.5), (7,4,1.5), (8,4,0.25), (9,5,-0.25)], 0.6)
>>> G39.set_labels('Kxyz45678T')
>>> G39.label_on()
>>> G39.view

G39

Ci-dessous une 3-coloration qui prouve que ce graphe est 3-colorable :

>>> G39.colorise()
>>> G39.color_on()
>>> G39.view

G39 coloré

Le sommet \(T\) est toujours de la même couleur que l'un des littéraux \(x, y, z\).

On suppose \(T\) de couleur 0. \(T\) forme un triangle avec les sommets 7 et 8, on a donc les 3 couleurs. Supposons que 8 soit de couleur 2. Dès lors \(z\) est de couleur 0 ou 1. Si c'est 0 c'est comme \(T\). Sinon, \(z\) est de couleur 1. Ce qui impose la couleur 2 à \(K\) (qui est relié à \(z\) et à \(T\)). Dès lors \(x\) et \(y\) ne peuvent pas être de couleur 2. Il reste la couleur 1 ou 0. Montrons que 1 n'est pas possible. En effet, si \(x\) et \(y\) sont tous les deux 1 alors les noeuds 4 et 5 ne peuvent pas être 1 et donc se partagent les couleurs 0 et 2 laissant 1 pour le noeud 6 (4, 5, 6 forment un triangle). Mais alors le noeud 7 est de couleur 2 et 8 de couleur 1 ce qui n'est pas possible puisque relié à \(z\). \(\square\)

Q40

Il faut montrer que \(\varphi\) est satisfiable si et seulement si \(G_\varphi\) est 3-colorable.

  • Soit une 3-coloration de \(G_\varphi\). Pour chaque clause \(C_i\) de \(\varphi\), il existe un littéral \(x_i\) dont le sommet associé est de même couleur que le noeud \(T\). On affecte à Vrai chacun de ces \(x_i\).

  • Soit une affectation des variables de \(\varphi\) qui satisfait la formule. On construit alors la 3-coloration suivante : chaque litteral à vrai prend la couleur 0, ainsi que le sommet \(T\). Les négations des littéraux prennent la couleur 1 ainsi que le noeud \(F\). Les deux noeuds entre les littéraux et \(T\) se partagent les 2 couleurs 1 et 2. Les triangles entre les littéraux et le triangle de \(T\) prend les 3 couleurs. Quand au noeud \(K\) il prend la couleur 2.

Q41

Puisqu'on a 3-SAT \(\leq_P\) 3_coloration et que 3-SAT est NP-complet alors 3-coloration est au moins NP-difficile. \(\square\)

3.4 Algorithmes gloutons⚓︎

Dans cette section, on étudie les algorithmes suivants :

Début algorithme
    Entréee : graphe G = (S, A)
    Pour chaque sommet s in S non coloré Faire
        Colorer s avec la plus petite couleur possible
Q42

Ma version était fausse... merci à Romain pour la correction :

def plus_petit_absent(L):
    vus = [0] * len(L)
    for v in L:
        if v < len(L):
            vus[v] = 1
    i = 0
    while i < len(vus) and vus[i] == 1:
        i += 1
    return i

Test :

>>> plus_petit_absent([1, 0])
2
>>> plus_petit_absent([1, 2])
0
>>> plus_petit_absent([2, 0])
1
Q43
def colo_glouton(G):
    n = len(G)
    color = [-1] * n
    for i in range(n):
        if color[i] == -1:
            color[i] = plus_petit_absent([color[j] for j in G[i] if color[j] != -1])
    return color
Q44

plus_petit_absent est linéaire en la longueur de la liste. Cette liste ici dans le pire des cas est la totalité des arêtes. On a donc un complexité totale en \({\cal O}(n\times m)\). \(\square\)

Q45

On considère le graphe \(G_2\) suivant :

>>> G2 = pygraph.Graph(5)
>>> G2.add_edges_from([(0, 1), (0, 4), (1, 4), (3, 4), (1, 3), (2, 3)])
>>> G2.position([(0, 0, 0), (1, 1, -0.75), (4, 1, 0.75), (3, 2, 0), (2, 3, 0)], 0.7)
>>> G2.view
G2

Les listes d'adjacences de \(G_2\) :

>>> AG2 = [[1, 4], [0, 3, 4], [3], [1, 2, 4], [0, 1, 3]]

Et notre algo glouton de coloration va se fourvoyer en état obligé d'attribuer une quatrième couleur au noeud 4 :

>>> colo_glouton(AG2)
[1, 0, 1, 2, 3]
Q46

Soit \(G\) un graphe tel que \(\chi(G) = k\). Soit \(C\) la \(k\)-coloration : \(0, 1,\ldots k-1\), alors si on considère l'indexation des sommets qui suit la coloration : on commence par numéroter \(0, 1,\ldots n_0\) tous les sommets avec la couleur 0, on continue \(n_0+1,\ldots n_1\) tous ceux colorés avec 1 etc. L'algorithme glouton donnera alors la coloration \(C\). \(\square\)

Q47

Dans \(G_2\), c'est le fait de traiter le sommet 4 en dernier qui fait rater la coloration optimale. Avec l'algorithme de Walsh-Powell on a la garantie de traiter les sommets 1, 3, et 4 avant les 2 autres. Ainsi le triangle sera coloré 0, 1, 2 et le sommet 2 peut avoir une des couleurs du sommet 1 ou du sommet 4. Le noeud 0 aura la couleur du sommet 3. On garantit donc la 3-coloration. \(\square\)

On considère les graphes couronnes \(J_n\) à \(2n\) sommets. Ces graphes sont dit bi-partie ie qu'ils admettent une 2-coloration.

Les codes
def jn(n):
    couronne = pygraph.Graph(2*n)
    for i in range(n):
        for j in range(n, 2*n):
            if i%n != j%n:
                couronne.add_edge(i, j)
    return couronne
def jn_en_ligne(jn):
    pos = []
    n = len(jn.node_ids()) // 2
    for i in range(n):
        pos.append((i, 0, -i))
    for j in range(n, 2*n):
        pos.append((j, 1.5, -(j%n)))
    jn.position(pos, 0.7)
from math import cos, sin, pi

def jn_en_couronne(jn, rayon=1):
    n = len(jn.node_ids()) // 2
    pos = []
    a = 0
    for i in range(n):
        pos.append((i, rayon*cos(a), rayon*sin(a)))
        a += 2*pi/n
    a = (((n - 1)//2)*2+1) * pi/n
    for i in range(n, 2*n):
        pos.append((i, rayon*cos(a), rayon*sin(a)))
        a += 2*pi/n
    jn.position(pos)
Les exemples
>>> J3 = jn(3)
>>> jn_en_ligne(J3)
>>> J3.view

J3 en ligne

>>> jn_en_couronne(J3)
>>> J3.view

J3 en couronne

>>> J4 = jn(4)
>>> jn_en_ligne(J4)
>>> J4.view

J4 en ligne

>>> jn_en_couronne(J4)
>>> J4.view

J4 en couronne

>>> J5 = jn(5)
>>> jn_en_ligne(J5)
>>> J5.view

J5 en ligne

>>> jn_en_couronne(J5)
>>> J5.view

J5 en couronne

Q48

Soit \(J_n = (\{x_1,\ldots x_n\}\cup \{y_1,\ldots y_n\}, S)\) un graphe couronne avec \(n\geq 3\). Notons que tout sommet de \(J_n\) est de degré \(n - 1\) c'est donc l'indexation qui détermine l'ordre suivant lequel les sommets sont colorés.

Une 2-coloration⚓︎

La coloration \(C\) obtenue en suivant l'indexation suivante est une 2-coloration : \(\forall 1\leq i\leq n, I(x_i) = i\) et \(\forall 1\leq i\leq n, I(y_i) = n + i\). En effet tous les \(x_i\) n'étant pas liés entre eux, à chaque \(x_i\) choisit, la plus petite couleur est 0. Puis, pour chaque \(y_j\) il sera relié à des \(x_i\) et uniquement des \(x_i\), la plus petite couleur sera donc 1.

Une \(n\)-coloration⚓︎

On considère maintenant l'indexation suivante : \(\forall 1\leq i\leq n, I(x_i) = 2i - 2\) et \(\forall 1\leq i\leq n, I(y_i) = 2i - 1\). Montrons que pour tout \(1\leq i\leq n\), on a \(x_i\) et \(y_i\) qui sont de couleur \(i - 1\) (propriété que nous nommons \(P(i)\)).

  • \(P(1)\) est vraie : en effet les premier sommet choisi sera \(x_1\) et donc avec la couleur 0. Puis le deuxième numéro est 2 et c'est le sommet \(y_1\) qui, n'étant pas lié à \(x_1\) peut avoir aussi la couleur 0.
  • Supposons \(P(i-1)\). Le prochain sommet à colorier est \(x_i\) lié à chacun des \(y_1,\ldots y_{i-1}\). D'après \(P(i-1)\) ces sommets \(y_j\) occupent les couleurs de 0 à \(i-2\) et la plus petite couleur non utilisée est donc \(i - 1\). Le sommet suivant est \(y_i\), lié à \(x_1,\ldots x_{i-1}\), mais pas à \(x_i\). Les \(x_j\) occupent les couleurs \(0,\ldots i-2\) et la plus petite couleur utilisable est \(i-1\).

En conséquence, \(P(n)\) est vraie et prouve que l'indexation \(I\) conduit l'algorithme à une \(n\)-coloration. \(\square\)

En images...

Ordre de traitement : \(0, 1,\ldots 8\)

J5 2-coloré

Ordre de traitement : \(0, 4, 1, 5, 2, 6, 3, 7\)

J4 4-coloré

Q49

On considère le graphe suivant :

>>> G3 = pygraph.Graph(11)
>>> G3.add_edges_from([(0, 1), (1, 2), (1, 3), (1, 4), (4, 5), (5, 6), (5, 7), (7, 8), (7, 9), (7, 10)])
>>> G3.position([(0, 0, 0), (1, 1, 0), (2, 1, 1), (3, 1, -1), (4, 2, 0), (5, 3, 0), (6, 3, 1), (7, 4, 0), (8, 4, 1), (9, 4, -1), (10, 5, 0)], 0.8)
>>> G3.view

G3

Quelle que soit l'indexation choisie, l'algorithme va prendre l'ordre suivant :

  1. les deux sommets d'ordre 4 (1 et 7 dans notre exemple)
  2. le sommet d'ordre 3 (sommet 5)
  3. le sommet d'ordre 2 (sommet 4)
  4. enfin les sommets d'odre 1, dans un ordre qui va dépendre de l'indexation choisie

Construisons la coloration :

  1. les sommets d'ordre 4 ne sont pas reliés entre eux, ils seront choisis les premiers et auront la couleur 0, peu importe l'ordre
  2. est ensuite choisi le sommet d'ordre 3 qui est lié à un des sommets d'ordre 4 : sa couleur sera donc 1
  3. le sommet d'ordre 2 étant lié aux sommets d'ordre 4 et 3, les couleurs 0 et 1 lui sont interdites, la plus petite possible est donc 2

On obtient donc une \(k\)-coloration avec \(k\geq 3\) alors que la coloration suivante est une 2-coloration :

  • On colorie en 0 : 0, 2, 3, 4, 6, 7
  • On colorie en 1 : 1, 5, 8, 9, 10

\(\square\)

Cette coloration est d'ailleurs obtenue par l'algorithme D-SATUR

>>> G3.colorise()
>>> G3.color_on()
>>> G3.view

G3 2-coloration

4 Coloration de graphes d'intervalles⚓︎

Q50

Soit \(G = (S, A)\) un graphe d'intervalles et \(r\) une réalisation de \(G\).

  • Soit ordo un ordonnancement cohérent de \(r\). Montrons que ordo est une coloration de \(G\). Soit \((i, j)\in A\) alors cela signifie que les tâches associés \(t_i\) et \(t_j\) sont telles que \(t_i\cap t_j\ne \emptyset\). Comme ordo est cohérent on a ordo[i] != ordo[j].

  • Soit \(c\) une coloration de \(G\). Montrons que c est un ordonnancement cohérent des tâches de \(r\). Soit \(t_i\) et \(t_j\) deux tâches telles que \(i\ne j\). Si les sommets \(i\) et \(j\) associés sont tels que \(c(i) \ne c(j)\) alors l'ordonnancement ne prévoit pas les mêmes machines pour les deux tâches et il n'y a pas d'incohérence. Si au contraire \(c(i) = c(j)\) alors puisque \(c\) est une coloration, cela signifie que \((i, j)\notin A\) et par conséquent \(t_i\cap t_j = \emptyset\) prouvant la cohérence. \(\square\)

Q51

Soit \(G = (S, A)\) un graphe d'intervalles et \(r\) une réalisation de \(G\). On traite les sommets du graphe dans l'ordre croissant des dates de début des intervalles correspondant dans la réalisation \(r\).

4.1 Parcours en largeur lexicographique⚓︎

On considère le graphe \(G_4\) suivant. Il s'agit du graphe d'intervalles de l'ensemble de tâches \(T_2\) du début de ce sujet ; c'est donc le même graphe que GT2 mais présenté autrement :

>>> G4 = pygraph.Graph(8)
>>> G4.add_edges_from([(0,4), (0,7), (0,6), (0,5), (5,1), (5,6), (6,7), (7,4), (4,3), (3,2)])
>>> G4.position([(7, -0.5, 0), (6, 0.5, 0), (0, 0, 1), (4, -1.5, 0), (5, 1.5, 0), (1, 1.5, -1), (2, 0, -1), (3, -1.5, -1)], 0.6)
>>> G4.view

G4

La vue GT2 :

GT2

Q52

On va appliquer le parcours lexicographique sur \(G_4\). Ci-dessous une fonction pour modifier un pygraph.Graph et faire avancer l'algorithme :

Code
etiquettes = [''] * 8
selected = set()

def select(g, s, i):
    g.color_on(s, 0)
    selected.add(s)
    g.node_view(s).label = str(s)
    i -= 1
    for v in g.neighbors(s):
        # on ne prend que les sommets non sélectionnés
        if v not in selected: 
            etiquettes[v] += str(i)
            g.node_view(v).label = f'{v}-{etiquettes[v]}'
    g.label_on()
    return i

On fixe l'étiquette du sommet 0 à 8 :

>>> i = 8
>>> etiquettes[0] = str(i)
>>> G4.node_view(0).label = f'0-{etiquettes[0]}'
>>> G4.label_on()
>>> G4.view

G4 Etape 1

On sélectionne le sommet 0 et on concatène 7 à l'étiquette des voisins :

>>> i = select(G4, 0, i)
>>> G4.view

G4 Etape 2

On sélectionne le sommet 4 (le plus petit indice avec l'étiquette maximale 7) et on concatène 6 à l'étiquette des voisins (désolé pour le souci d'affichage, un des points d'amélioration de pygraph) :

>>> i = select(G4, 4, i)
>>> G4.view

G4 Etape 3

On sélectionne le sommet 7 et on rajoute 5 à l'étiquette des voisins (non déjà sélectionnés) :

>>> i = select(G4, 7, i)
>>> G4.view

G4 Etape 4

On sélectionne le sommet 6 et on rajoute 4 à l'étiquette des voisins (non déjà sélectionnés) :

>>> i = select(G4, 6, i)
>>> G4.view

G4 Etape 5

On sélectionne le sommet 5 et on rajoute 3 à l'étiquette des voisins :

>>> i = select(G4, 5, i)
>>> G4.view

G4 Etape 6

On sélectionne le sommet 3 et on rajoute 2 à l'étiquette des voisins :

>>> i = select(G4, 3, i)
>>> G4.view

G4 Etape 7

On termine avec les sommets 1 et 2 donnant l'ordre suivant : \(\sigma = (0, 4, 7, 6, 5, 3, 1, 2)\).

Q53

L'algorithme glouton en suivant l'ordre LexBFS (donc avec le \(\sigma\) précédent) donne :

  • premier sommet 0 : couleur 0
  • puis 4 coloré en 1
  • puis 7 couleur 2
  • puis 6 couleur 1
  • puis 5 couleur 2
  • puis 3 couleur 0
  • puis 1 couleur 0
  • enfin 2 couleur 1

On a bien une 3-coloration

Par un parcours classique via indices croissants on aurait eu : 0 en couleur 0, 4 en couleur 1, 5 en 1, 6 en 2, 7 en 3 (puisque 0, 1 et 2 sont déjà pris par les voisins), 3 en 0, 1 en 0 et enfin 2 en 1. On n'obtient donc qu'une 4-coloration.

4.2 Application à la coloration de graphes d'intervalles⚓︎

Parcours simplicial

Un parcours \(\sigma\) est simplicial, si pour chaque sommet, ses voisins qui le précèdent forment une clique.

Q54

en cours

Q55

en cours

4.3 Implémentation⚓︎

Q56

L'algorithme reprend donc l'algorithme glouton mais au lieu de juste parcourir les noeuds suivant les indices, ici on doit sélectionner suivant l'ordre BFS-lexicographique.

On a besoin des 3 structures suivantes :

  • un tableau pour la coloration
  • un tableau pour les étiquettes
  • un ensemble pour les sommets à traiter (retrait et test d'appartenance en temps constant)
Le code
def lexBFS(G):
    """Réalise une coloration glouton en suivant l'ordre lexBFS"""
    n = len(G)
    coloration = [-1] * n
    etiquettes = [''] * n
    etiquette = n
    noeuds_a_traiter = set(range(n))
    while noeuds_a_traiter:
        s = select(G, noeuds_a_traiter, etiquettes, coloration)
        print(s) # rajouté pour vérifier l'ordre des noeuds
        noeuds_a_traiter.remove(s)
        couleur = plus_petit_absent([coloration[j] for j in G[s] if coloration[j] != -1])
        coloration[s] = couleur
        # mise à jour des étiquettes
        etiquette -= 1
        for v in G[s]:
            if v in noeuds_a_traiter:
                etiquettes[v] += str(etiquette)
    return coloration
def select(g, noeuds, etiquettes, coloration):
    """retourne le noeud de g non coloré qui maximise
    le degré et l'étiquette (ordre lexico)"""
    s = None
    for v in noeuds:
        if s is None:
            s = v
        elif coloration[v] == -1:
            if len(g[v]) > len(g[s]) or len(g[v]) == len(g[s]) and etiquettes[v] > etiquettes[s]:
                s = v
    return s

plus pythonique :

def select(g, noeuds, etiquettes, coloration):
    return max([v for v in noeuds if coloration[v] == -1], key=lambda s: (len(g[s]), etiquettes[s]))

Exécuté sur le graphe \(G_4\), on obtient l'odre de parcours des sommets suivant : \((0, 4, 7, 6, 5, 3, 1, 2)\) et la coloration optimale suivante :

G4 LexBFS