19
Chapitre 2: Paramètres de graphes
I. Introduction
Dans ce chapitre nous allons étudier un ensemble de paramètres qui nous
permettent de résoudre un certain nombre de problèmes.
Définitions :
On appelle clique un sous-graphe complet de G.
On appelle graphe fini un graphe dont le nombre de sommets est fini (|X|<∝).
On appelle un sous-ensemble A absorbant si tous sommet x n’appartient
pas à A possède au moins un successeur dans A.
II. Stabilité
Un sous-ensemble S ⊂ X est un ensemble stable (ou un stable) s’il ne comprend
que des sommets non adjacents deux à deux : ∀ (xi, xj) ∈ S ⇒ (xi, xj) ∉ U.
Nombre de Stabilité : noté α(G) : c’est le cardinal maximal d’un sous-
ensemble stable de G. (Le cardinal du plus grand stable)
Exemple :
G = (X, U) une clique un stable
III. Noyau
Un sous-ensemble N de sommets est appelé noyau du graphe s’il est à la fois
stable et absorbant.
Le noyau d’un graphe :
N’admet pas de boucle,
Il est l’ensemble stable avec le maximum d’éléments donc, les
sommets de N n’ont aucun arc les joignant deux à deux.
A. Merabet – centre universitaire de Mila – 2020
20
Chapitre 2: Paramètres de graphes
Il est l’ensemble absorbant avec le maximum d’éléments donc, chaque
sommet qui n’est pas dans N a un successeur (au moins) dans N.
Exemple :
Un graphe orienté peut n’avoir aucun noyau, ou bien un seul, ou bien plusieurs.
IV. Coloration des sommets d’un graphe
Définition : La coloration des sommets d’un graphe consiste en une affectation de
couleurs à tous les sommets du graphe de telle sorte que deux sommets adjacents ne
soient pas porteurs de la même
couleur.
Exemple : coloration en 3 couleurs
IV.1. K-coloriage
Un coloriage du graphe avec K couleur sera appelé un K-coloriage.
IV.2. Nombre chromatique
Le nombre chromatique d’un graphe est le nombre minimum de couleur
nécessaire à son coloriage.
On note d’habitude 𝛄 (G) le nombre chromatique d’un graphe G.
Remarque :
Si plusieurs sommets d’un graphe sont de la même couleur, aucune arête ne les
joint. Ils forment donc un sous-graphe stable.
Colorier un graphe revient donc à le partitionner en sous-graphes stables
si G est un graphe, alors pour tout sous-graphe H de G on a : γ (H) ≤ γ (G)
A. Merabet – centre universitaire de Mila – 2020
21
Chapitre 2: Paramètres de graphes
le nombre chromatique du graphe complet Kn est n
soit Cn un cycle de longueur n :
si n est pair on alors : γ(Cn)=2, et si n est impair on alors : γ(Cn)=3
Soit D le degré maximal des sommets du graphe G. Alors : γ (G) ≤ 1 + D
IV.3. Algorithme 3
Algorithme 3 : Welsh-Powell pour colorier un graphe
Entrées : G=(X ; U) un graphe non orienté,
Sortie : un graphe coloré
Variables intermédiaires :
L, V : deux listes de sommets, s : un sommet.
Début
L = liste des sommets classés dans l’ordre décroissant de leur degré
couleur courante= 0
Tant que L ≠ ∅ faire
incrémenter la couleur courante
Colorier s le premier sommet de L avec la
couleur courante
Eliminer s de L
V = liste des voisins de s
Pour tout x dans L faire
SI x ∉ V alors
Colorier x avec la couleur courante
ajouter les voisins de x à V
finSi
Fin pour
éliminer les sommets coloriés de L
Fin tant que
Fin
Exemple :
A. Merabet – centre universitaire de Mila – 2020
22
Chapitre 2: Paramètres de graphes
1. On range les nœuds du plus haut degré au plus petit : L = {A, B, F,
C, E, G, D} couleur
bleu 1
Sommets A B F C E G D
noir 2
Degrés 5 3 3 2 2 2 1
… …
2. Prendre la première couleur (par incrémentation) :
Couleur courante 1
On attribue la couleur courante au premier sommet (ici, le nœud A)
LL–A donc, L = {B, F, C, E, G, D}
3. V : liste de voisin de A, donc, V = {B, C, D, E, F}
Pour tout x dans L faire SI x ∉ V alors
C’est-à-dire On colorie de la même couleur tous les sommets non adjacents au
sommet A et qui ne sont pas adjacents entre eux = {G}
1. On réitère ce procédé avec une autre couleur pour le premier sommet non colorié
de la liste : ici, le sommet B : couleur Réf Résultats
L = {B, F, C, E, D} bleu 1 A,G
Couleur courante 2 noir 2 B,D,E
On attribue la couleur courante pour le premier sommet … 3 F,C
(ici, le sommet B)
LL–B donc, L = {F, C, E, D}
2. V : liste de voisin de B, donc, V = {F, C}
Pour tout x dans L faire SI x ∉ V alors
C’est-à-dire On colorie de la même couleur tous les sommets non adjacents au
sommet B et qui ne sont pas adjacents entre eux = {D, E}
1. On recommence jusqu’à l’épuisement des sommets.
…
On obtient un 3-coloriage et donc on
obtient 𝛄(𝑮) =3.
Remarque
Le nombre de couleurs utilisés par cet algorithme n’est pas forcément le
nombre chromatique du graphe.
A. Merabet – centre universitaire de Mila – 2020
