REPUBLIQUE ALGERIENNE DEMOCRATIQUE ET POPULAIRE

MINISTERE DE L’ENSEIGNEMENT SUPERIEUR ET DE LARECHERCHE SCIENTIFIQUE

ECOLE NATIONALE POLYTECHNIQUE

Théorie des Graphes

Support de cours du module informatique 3- Partie1

2ème année cycle préparatoire

Par :Dr. Esma BENDIAB

Année 2017/2018
[Link] Informatique 3 Théorie des graphes

Préambule

L’histoire de la théorie des graphes débute avec les travaux d’Euler au XVIII siècle ;Elle
e

trouve son origine dans l’étude de certains problèmes, tels que celui des ponts de Königsberg. Les
habitants de Königsberg se demandaient s’il était possible, en partant d’un quartier quelconque de
la ville, de traverser tous les ponts sans passer deux fois par le même et de revenir à leur point de
départ), la marche du cavalier sur l’échiquier ou le problème de coloriage de cartes.

La théorie des graphes s’est alors développée dans diverses disciplines telles que la chimie, la
biologie, les sciences sociales. Depuis le début du XX siècle, elle constitue une branche à part
e

entière des mathématiques.

De manière générale, un graphe permet de représenter la structure, les connexions d’un ensemble
complexe en exprimant les relations entre ses éléments : réseau de communication, réseaux
routiers, interaction de diverses espèces animales, circuits électriques,. . .
Les graphes constituent donc une méthode de pensée qui permet de modéliser une grande variété
de problèmes en se ramenant à l’étude de sommets et d’arcs.
Les derniers travaux en théorie des graphes sont souvent effectués par des informaticiens, du fait
de l’importance qu’y revêt l’aspect algorithmique.

1
[Link] Informatique 3 Théorie des graphes

Chapitre 1

Concepts de base de la théorie des graphes

1. Introduction

Les graphes représentent de manière simple et naturelle des relations entre les objets. Ils
constituent un moyen très pratique pour représenter différents types d’objets et différentes
situations de la vie courante. Ils peuvent aussi représenter la structure d’un ensemble complexe
avec ses éléments et les relations entre eux. Les outils mathématiques et les algorithmes mises au
point en théorie des graphes permettent de résoudre une multitude de problèmes, tels que les
problèmes de cheminement, d’ordonnancement, d’affectation, etc.

Ce chapitre présente les aspects fondamentaux de la théorie des graphes.

2. Définition d’un graphe et ses différentes représentations

Un graphe est une structure comportant un ensemble non vide X d’éléments appelés sommets et
un ensemble A d’éléments appelés arcs.

2.1 Définition d’un graphe

Un graphe G =(X, A) est le couple constitué :

1. Par un ensemble X de sommets X = {x1, x2, …….xn}

2. Par un ensemble d’arêtes A = {a1, a2, …... ap} qui sont les éléments du produit cartésien
X*X = {(x,y)/ x∈ X, y ∈ X}

Exemple :
L’ensemble X des sommets : X={a,b,c,d}
L’ensemble A des arêtes : A = {ab, ad, ac, bd, bc}
Card (X) = 4 et Card (A) = 5

Figure 1.1 Représentation d'un graphe.

2.2 Orientation d’un graphe

Certains graphes possèdent une propriété utile pour la

modélisation de systèmes particuliers, il s’agit de
l’orientation. Le segment qui relie deux sommets peut être
orienté (on parle alors d’arc, A= E, G = (X,E) ) ou non
(on parle alors d’arête, A=U,G =(X,U)). En représentation
graphique, l’orientation est représentée par une flèche.

Figure 1.2 Représentation d'un graphe orienté.

2
[Link] Informatique 3 Théorie des graphes

2.3 Terminologie

La terminologie suivante s’applique à tout graphe G :

- Les deux sommets u et v sont appelés extrémités de l’arête (u,v). S’il s’agit d’un arc, u et v
désignent respectivement l’extrémité initiale et terminale de l’arc. Le sommet u est le prédécesseur
de v et v est le successeur de u.
- Les arcs ayant même extrémités sont appelés arcs parallèles.
- Un arc de la forme (v,v) est une boucle.
- Un graphe est simple s’il n’a ni arcs parallèles ni boucles.
- Un graphe sans arcs est un graphe vide (G = (X, A) /A =∅).
- Un graphe sans sommets est un graphe nul (G = (X, A) /X =∅).
- Un graphe ayant un seul sommet est un graphe trivial (G = (X, A) /Card(X) =1).
- Des arcs sont adjacents s’ils ont un sommet en commun à l’une des extrémités.
- Deux sommets u et v sont voisins ou adjacents s’ils sont connectés par un arc.
Le voisinage d’un sommet désigne l’ensemble de ses sommets voisins.
Soit x ∈ X, un sommet du graphe G, on appelle voisin de x tout sommet y ∈ X
différent de x et qui est adjacent à x. Ainsi, on définit l’ensemble V comme suit :
– V (x) = {y ∈ X − {x}/{x, y} ∈ E} pour les graphes non orientes.
– V (x) = V +(x) ∪ V −(x) où V +(x) = {y ∈ X − {x}/(x, y) ∈ U} et
V −(x) = {y ∈ X−{x}/(y, x) ∈ U}. (graphe orienté)
– V +(x) (resp. V −(x)) est appelé ensemble des voisins externes (resp. internes) de x.
- Un graphe G est dit complet si et seulement si ∀ x, y ∈ X, (x,y) ∉ A ⇒ (y,x) ∈A. c'est-à-dire
que tous les couples de sommets qu’il est possible de choisir (chacun étant pris une seule fois)
sont présents dans A.

Figure 1.3 Un exemple de graphe complet.

2.4 Notion d’ordre et de degrés

Les deux nombres d’un graphe sont l’ordre et le degré.

2.4.1 Ordre d’un graphe

Dans la définition ci-dessus d’un graphe, le nombre n représente l’ordre du graphe G. il s’agit du
nombre de ses sommets. Dans l’exemple de la figure 1.1, l’ordre du graphe est 4.

2.4.2 Notion de degré

Définition 01 ( degré) Soit G = (X,E) un graphe non orienté (resp. G = (X, U) un graphe
orienté). A tout sommet x ∈ X, on peut associer une valeur entière positive ou nulle, notée
dG(x), qu’on appelle degré du sommet x. Cette valeur est définie comme suit :
dG(x) = nombre de fois où x est extrémité d’un arc (resp. d’une arête).

3
[Link] Informatique 3 Théorie des graphes

2.4.2 .1 Dans le cas d’un graphe non orienté

Définition 2 Soit G = (X,E) un graphe non orienté.

Le degré d’un sommet x, noté d(x), est le nombre d’arêtes ayant x comme extrémité ou le nombre
d’arêtes incidentes à ce sommet. Par convention, la boucle est comptée deux fois.
d(x) = card{(x,y)/ (x,y) ∈ E} + 2* card{(x,x)/ x,x) ∈ E}

Exemple Dans l’exemple de la figure 1.1 :

- d(a) = d(b)=3
- d(c) = d(d)=2

Formule Cas non orienté :

Pour tout graphe non orienté G = (X,E), on a :

Preuve Chaque arête a exactement deux extrémité ⇒ Elle est comptée deux fois dans le degré de
chaque sommet ⇒ La somme totale des degrés est égale a deux fois le nombre total d’arêtes.

2.4.2 .2 Dans le cas d’un graphe orienté,

Le degré d’un sommet est calculé comme étant la somme des demi-degrés extérieurs et intérieurs
d’un sommet.

Définition 3 Soit G = (X,U) un graphe orienté.

On appelle demi-degré extérieur d’un sommet x ∈ X, la valeur suivante :
d+G(x) = |{u ∈ U/I(u) = x}|
- demi-degré extérieur : d+(i) est le nombre d’arcs dont i est l’extrémité initiale.

On appelle demi-degré intérieur d’un sommet x ∈ X, la valeur suivante :

d− G(x) = |{u ∈ U/T(u) = x}|
- demi-degré intérieur : d -(i) est le nombre d’arcs dont i est l’extrémité terminale.

Le degré d’un sommet x : dG(x) = d + G(x) + d− G(x)

Exemple Dans l’exemple de la figure 1.2 : d+(b) = 0 et d-(b) = 2.

Remarque Pour tout graphe, nous avons : dG(x) > |V (x)|. Si G est un graphe non orienté
simple alors on a : dG(x) = |V (x)|. Tel que V (x) est l’ensemble des voisins.

Formule Cas orienté :

Pour tout graphe oriente G = (X,U), on a :

et d+G(x)= =|U|

Preuve Chaque arc a exactement une extrémité initiale et une extrémité terminale ⇒ Chaque arc
est comptabilise une fois dans d+ pour son extrémité initiale et une autre fois dans d− pour son
extrémité finale. Le nombre total d’arcs ayant une extrémité initiale (resp. terminale) est
exactement la somme des demi-degrés extérieurs (resp. intérieurs).

4
[Link] Informatique 3 Théorie des graphes

Conséquence : De là, on peut déduire que le nombre de sommets de degrés impairs dans un
graphe est toujours pair.

2.4.2 .3 Théorème 1 : (Théorème d’Euler)

La somme des degrés des sommets est égale au double du nombre de ses arcs.

Remarques :
- un sommet pendant est un sommet dont le degré est 1.
Si dG(x) = 1 Alors x est dit sommet pendant.
- Un sommet isolé est un sommet dont le degré est nul.
Si dG(x) = 0 Alors x est dit sommet isolé.
– Un arc (resp. Une arête) incident(e) a un sommet pendant est aussi dit(e) arc (arête) pendant(e).
– On appelle degrés minimal d’un graphe G qu’on note par δ(G), le plus petit degré dans le
graphe G. δ(G) = min{dG(x)}
– On appelle degré maximal d’un graphe G qu’on note par Δ(G), le plus grand degré dans le
graphe G. Δ(G) = max{dG(x)}

3. Représentations machine d’un graphe

Un certain nombre de représentations existent pour décrire un graphe. On distingue

principalement la représentation par matrice d’adjacence, par matrice d’incidence sommets-arcs et
par listes d’adjacence.

3.1 Matrice d’adjacence

A tout graphe simple d’ordre n on associe une matrice M de n lignes et n colonnes dont les
éléments sont notés Mij .

MA=

Pour un graphe non orienté G = (X,E), Mij=Mji représente le nombre d’arêtes ayant
les sommets i et j comme extrémités.

Remarques 01
- La matrice d’adjacence MA d’un graphe non orienté est toujours symétrique.
- La somme d’une ligne k = la somme d’une colonne k = dG(k).

Pour un graphe orienté G=(X, U), Mij représente le nombre d’arcs ayant i comme
extrémité initiale et j comme extrémité terminale.

Remarques 02:

- Dans le cas d’un graphe valué (dont les arcs ont des valeurs), le « 1 » est remplacé par la valeur
de l’arc.
– La somme d’une ligne i = d+G(i).
- La somme d’une colonne j = d− G(j).

5
[Link] Informatique 3 Théorie des graphes

Exemple : Si l’on considère le graphe de la figure 1.2, sa représentation par matrice

d’adjacence est comme suit :

1
0

Remarques 03
– Les coefficients de MA pour un graphe simple est binaire avec la diagonale complètement à 0.
– Les éléments de MA pour un multi graphe (graphe contenant des arcs (resp. arêtes) parallèles)
sont le nombre d’arcs (arêtes) de chaque sommets.

3.2 Matrice d’incidence sommets-arcs

A tout graphe non oriente G = (X,E), on peut associer une matrice M de n lignes et m colonnes.
Où n est le nombre de sommets dans G et m est le nombre d’arêtes dans G.
Mij représente le nombre de fois où le sommet i est incident à l’arête j. Les éléments de M sont
dans {0, 1, 2}

A tout graphe orienté G = (X,U), on peut associer une matrice M de n lignes et m colonnes. Où
n est le nombre de sommets dans G et m est le nombre d’arcs dans G.

Chaque élément MI(i,j) de la matrice a pour valeur :

Si aj non incident à i
Si aj sortant de i
MI
Si aj rentrant dans i
Si aj est une boucle

Exemple : en considérant toujours le graphe de la figure 1.2, sa représentation par matrice

d’incidence sommets-arcs est comme suit :

Remarques :

- Si deux colonnes j1 et j2 sont identiques alors les arêtes j1 et j2 sont parallèles.

- Si un élément Mij = 2 alors l’arête j est une boucle.
- Pour toute colonne correspondant à un arc (excepté pour les boucles), la somme est nulle.

3.3 Liste d’adjacence

Pour un graphe G=(X,A), la liste d’adjacence associée à ce graphe permet de représenter pour
chaque sommet, l’ensemble de ses successeurs.

6
[Link] Informatique 3 Théorie des graphes

Tous les arcs émanant d’un même sommet, sont liés entre eux dans une liste. A chaque arc sont
donc associés l’extrémité terminale et le pointeur au prochain sommet de la liste.

On crée un tableau LP, de dimension n, qui est destiné à contenir les têtes de liste. Dans ce
tableau, pour tout sommet i, on trouve un pointeur vers la liste de ses successeurs. La figure 1.4
illustre un graphe et la liste d’adjacence qui lui est associée.

Figure 1.4 Un graphe avec sa liste d'adjacence.

La liste d'adjacence d'un graphe non orienté, est la liste des voisins de chaque sommet.

4 . Graphes particuliers

Il arrive parfois que seul un sous-ensemble de sommets ou d’arcs soit pertinent à la résolution
d’un problème. Pour cette raison, nous poserons les définitions de quelques graphes particuliers.

Soit G = (X,U) un graphe orienté (resp. G = (X,E) un graphe non oriente). Soit A ∈ X un sous
ensemble de sommets et V ∈ U (resp. V ∈ E).

4.1 Sous graphe

Le sous-graphe de G = (X,A) induit par l’ensemble Xs ⊆ X est un graphe G1 = (Xs, As)
consistant en un sous ensemble de l’ensemble des sommets de X et en tous les arcs reliant les
sommets de ce sous ensemble.

Un sous graphe de G engendré par l’ensemble de sommets A est le graphe :

Gs = (Xs,Us)ou Us = {u ∈ U/I(u) ∈ A et T(u) ∈ A} dans le cas oriente.
Gs = (Xs,Es)ou Es = {e = {x, y} ∈ E/x ∈ A et y ∈ A} dans le cas non oriente

La figure 1.5 présente un graphe G et deux de ses sous-graphes. Le premier est induit par
l’ensemble Xs= {a, b}, le second est induit par Xs’= {b, c, d}.

Figure 1.5 Un graphe et quelques uns de ses sous-graphes.

Si le sous-graphe d’un graphe est complet, on dit qu’il forme une clique. Dans la figure 1.5, le
sous-graphe induit par Xss est une clique car il est complet.

7
[Link] Informatique 3 Théorie des graphes

4.2 Graphe partiel

Le graphe partiel de G = (X,A) induit par l’ensemble Ap ⊆ A est le graphe Gp = (X, Ap)
comportant tous les sommets de G et un sous ensemble d’arcs (arêtes) Ap de A.

La partie (a) de la figure 1.6 illustre un graphe partiel Gp du graphe G de la figure1.5. Gp est
induit par l’ensemble Ap= {(a,b), (b,c), (d,d)}.

Figure 1.6 Un graphe partiel et un sous-graphe partiel.

4.3 Sous-graphe partiel

Le sous-graphe partiel de G = (X,A) est le graphe Gsp = (Xs , Ap) induit par un sous ensemble
Xs de sommets de X et par un sous ensemble d’arcs (arêtes )Ap de A. on peut le considérer
comme le sous-graphe d’un graphe partiel.

La partie (b) de la figure 1.6 illustre un sous-graphe partiel Gsp du graphe G de la figure 1.5. Gsp
est induit par l’ensemble Xs= {a, b} et l’ensemble Ap= {(b,c), (d,d)}.
La figure 1.7 illustre un graphe G, un graphe partiel de G ainsi qu’un sous graphe.

Figure 1.7 illustre un graphe G, un graphe partiel de G ainsi qu’un sous graphe.

4 .4 Complément d’un graphe

Le graphe complémentaire de G est note G = (X, ) (resp. = (X, )) où :

= {(x, y) ∈ X2/(x, y) U}(resp. = {{x, y} ∈ X2/{x, y} E}

5 . Propriétés des graphes

5.1 Graphe Simple

Un graphe est dit simple s’il ne contient ni boucles ni arcs parallèles. Si G est simple, on a
dG(x) = |V (x)|.

8
[Link] Informatique 3 Théorie des graphes

5.2 Graphe Complet

Dans le cas orienté :

G est complet ssi ∀x, y ∈ X, (x, y) U ⇒ (y, x) ∈ U
Dans le cas non orienté :
G est complet ssi ∀x y X, {x, y} ∈ E. Figure 1.8 Un graphe complet
Un graphe simple complet d’ordre n est note Kn.

5.3 Graphe Régulier

Un graphe G est dit k-regulier
si ∀x sommet de G, on a dG(x) = k.
En d’autres termes, δ(G) = Δ(G) = k.
Figure 1.9 Un graphe régulier
5.4 Graphe Symétrique
Cette notion est spécifique aux graphes orientés. G est symétrique
ssi ∀x, y ∈ X, (x, y) ∈ U ⇒ (y, x) ∈ U

5.5 Graphe Antisymétrique

Cette notion est spécifique aux graphes orientés. Figure 1.10 Un graphe symétrique

G est antisymétrique
ssi ∀x, y ∈X, (x, y) ∈ U ⇒ (y, x) U

5.6 Graphe Transitif

Cette notion est spécifique aux graphes orientés. G est transitif
ssi ∀x, y, z ∈ X, (x, y) ∈U et (y, z) ∈ U ⇒ (x, z) ∈ U

Figure 1.11 Un graphe transitif

5.7 Graphe Biparti (bipartite)

G est dit biparti ssi l’ensemble de ses sommets X admet

une partition en deux sous ensembles X1 et X2
avec X1 ∩ X2 = ∅ et X1 ∪ X2 = X.

Dans le cas oriente : ∀(x, y) ∈ U ⇒ x ∈ X1 et y ∈ X2

Figure 1.12 – Un graphe biparti

Dans le cas non oriente : ∀x, y ∈ E(x ∈ X1 et y ∈ X2)ou(x ∈ X2ety ∈ X1).

G est dit biparti complet ssi G est dit biparti et ∀x ∈ X1 et ∀y ∈ X2 ⇒ (x, y) ∈ U.

Un graphe biparti complet et simple G = (X1 ∪X2,U) (resp. G = (X1 ∪X2,E)) avec
|X1| = p et |X2| = q est note Kp,q.

Théorème
Un graphe est biparti si et seulement s’il ne contient aucun cycle de longueur impaire.

9
[Link] Informatique 3 Théorie des graphes

5.8 Graphe Multiparti

G est dit multiparti ssi l’ensemble de ses sommets X admet une partition en p sous ensembles
X1,X2, . . .Xp (p 3). Avec Xi ∩ Xj = φ (i j) et X1 ∪ X2 . . . ∪ Xp = X.

Dans le cas oriente : ∀(x, y) ∈ U ⇒ x ∈ Xk et y ∈ Xk+1(avec 1 k p − 1).

Dans le cas non oriente : ∀x, y ∈ E(x ∈ Xk et y ∈ Xk + 1) ou (y ∈ Xk et x ∈ Xk+1)
avec 1 k p − 1

6 .Cheminements dans un graphe

Plusieurs problématiques peuvent être

considérées lorsque l'on s'intéresse au
cheminement entre deux points d'un graphe.
Cette section a pour objectif de définir les
concepts de cheminement dans un graphe.
Figure 1.13 Graphe G1.

6.1 Chaines et cycles

Les concepts de chaine et cycle peuvent aussi bien s’appliquer à un graphe orienté qu’à un graphe
non orienté.

6.1 Chaîne

On appelle chaine dans un graphe non orienté (resp. orienté) G = (X,E) (resp. G = (X,U)), une
séquence finie de la forme (x0, x1, …..xm). Le sommet x0 est le sommet initial et xm est le
sommet final. Cette séquence est une suite alternée de sommets et d’arêtes (resp. d’arcs),
μ = x0x1 . . . xk−1xk (resp. μ = x0x1 . . . xk−1xk) Tel que pour tout 1 i k, xi et xi+1 sont extrémités
de l’arête i (resp. de l’arc i).
Dans cette séquence, tout arc (arêtes) (xi-1, xi) a une extrémité en commun avec l’arc (arête)
suivant (xi, xi+1). On dit que μ est une chaine joignant les sommets x0 et xk de longueur k.

6.2 Chaine élémentaire

Une chaine élémentaire est une chaine qui passe par un sommet au maximum une fois, (si tous
les sommets les composants sont distincts).

6.3 Chaîne simple

On dit qu’une chaine est simple si tous les arcs ou les arêtes les composants sont distincts.

Sur la figure 1.13, la séquence (x6, x3, x2, x1,) représente une chaine élémentaire, alors que la
séquence (x3, x4, x2, x4,) n’est pas une chaine élémentaire.

6.4 Cycle

On appelle cycle dans un graphe non orienté (resp. orienté) G = (X,E) (resp. G = (X,U) ), toute
chaine fermée simple : μ = x0x1 . . . xk−1xk (resp. μ = x0x1 . . . xk−1xk) Tel que k 0, et x0 = xk.

10
[Link] Informatique 3 Théorie des graphes

(l’extrémité initiale est à la fois extrémité finale )La séquence de sommets pour un cycle est donc
(x0, x1, …..xm, x0). On dit que μ est un cycle longueur k.
Sur la figure 1.13, la séquence (x3, x2, x4, x3) représente un cycle.

Remarque :
- Notons qu’un même arc ne peut figurer deux fois dans la séquence.

Proposition Soit G = (X,E) un graphe

si le degré minimum δ(G) ≥ 2 alors G contient un cycle.
Si G est simple et δ(G) ≥ k ≥ 2 alors G comporte un cycle de longueur k.

6.2 Chemins et circuits

Les concepts de chemin et circuit sont relatifs aux graphes orientés puisque le sens d’orientation
des arcs est essentiel pour ces définitions.

6.2.1 Chemin

Dans un graphe G = (X,A), un chemin allant de x0 à

xm est
une séquence finie de la forme (x0, x1, …..xm) tel que
tout couple (xi-1, xi) forme un arc orienté dans la même
direction, la direction de parcours. Le sommet x0 est le
sommet initial et xm est le sommet final. Dans cette
séquence, pour tout arc (resp. arête )ai = (xi-1, xi),
l’extrémité terminale xi coïncide avec l’extrémité initiale
de l’arc ai+1. "m" est la longueur du chemin.
Sur la figure 1.13, la séquence (x2, x4, x3, x6) représente
un chemin allant de x2 à x6.

6.2.2 Chemin élémentaire

Un chemin élémentaire est un chemin qui passe par un sommet au maximum une fois.

6.2.3 Chemin simple

On dit qu’un chemin ou une chaine est simple si tous les arcs les composants sont distincts.

6.2.4 Circuit
Un circuit est défini comme un chemin fermé simple, tel que l’extrémité initiale est à la fois
extrémité finale. La séquence de sommets pour un circuit est donc (x0, x1, …..xm, x0).
Sur la figure 1.13, la séquence (x3, x6, x5, x4, x3) représente un circuit.

Remarques
- On dit qu’un cycle ou circuit est élémentaire si tous les sommets qui les composent sont
distincts.
- La longueur d’un cycle ou d’un circuit est aussi égale au nombre de sommets formant ce cycle
ou circuit.
- Dans un graphe simple, un cycle ou un circuit peuvent être déterminés juste en énumérant la
suite des sommets qui les composent.
- Une boucle est un cycle (circuit) élémentaire de longueur 1.
- Toute chaine (ou chemin) élémentaire est aussi simple. L’inverse n’est pas toujours vrai.

11
[Link] Informatique 3 Théorie des graphes

7 . Connexité

La connexité est une propriété essentielle des graphes surtout pour les problèmes relatifs aux
réseaux. Dans ce qui suit, sont étudiées les notions de connexité simple et forte.

Un graphe est connexe s’il est possible, à partir de n’importe quel sommet, de rejoindre tous les
autres en suivant les arêtes. Un graphe non connexe se décompose en composantes connexes.
Il existe une chaine joignant chaque paire de sommets x et y (x y).

Il est possible de distinguer deux types de connexité :

 la connexité qui concerne à la fois les graphes orientés et non orientés,
 la forte connexité qui ne concerne que les graphes orientés.

7.1 Connexité simple

Définition 1: Un graphe est dit connexe si et seulement si :

En d’autres termes, il doit être possible entre tout couple de sommets de trouver une chaine
reliant ces deux sommets.
Si un graphe n’est pas connexe, alors il admet au moins deux composantes connexes.
Le graphe G1 de la figure 1.14 est un graphe connexe alors que le graphe G2 n’est pas connexe
car il admet deux composantes connexes.

Figure 1.14 G1 un graphe connexe, G2 un graphe comportant deux composantes connexes.

7.2 Composante connexe

La composante connexe d’un sommet s, notée CC(s), est le sous-ensemble de sommets tels
qu’il existe une chaîne entre deux sommets quelconques de CC(s).
Si un sommet s’ appartient à la composante connexe d’un sommet s, alors la composante connexe
de s’ est égale à celle de s.

Définition 2
Soit un graphe G = (X,E) (resp. G = (X,U)) :
Une composante connexe CC(s) est un sous-graphe induit maximal connexe. Maximal signifie
qu’il n’y a pas de sous-graphe induit connexe plus grand contenant les sommets de CC(s).
Ou encore, Si le sous graphe engendré par un ensemble de sommets S ⊆ X (GS) est connexe et le
sous graphe engendré par S ∪ x et x S n’est pas connexe Alors GS est une composante
connexe de G.
12
[Link] Informatique 3 Théorie des graphes

Le sous graphe engendré par un sommet isolé est considéré comme une composante connexe de
G.

Exemples
Cet exemple présente les composantes connexes d'un graphe non orienté :

CC(s1) = {s1, s2, s3, s4, s5}

CC(s6) = {s6}

CC(s7) = {s7 , s8 , s9 , s10}

 Cet exemple présente un graphe orienté connexe :

Remarques 1
- Un graphe ne possédant qu'une seule composante connexe est simplement un graphe connexe.
-Un sommet isolé (de degré 0) constitue toujours une composante connexe à lui seul.

Proposition 1 Soit G Un graphe, l’ajout d’une arête a pour conséquence :

– soit diminuer le nombre de composantes connexes.
– soit créer un nouveau cycle dans le graphe

Proposition 2 Un graphe G d’ordre n connexe comporte au moins (n – 1) arêtes.

7.3 Graphe k-connexe

Un graphe G est dit k-connexe si et seulement si G est connexe d’ordre n k + 1 et il n’existe

pas d’ensemble S ⊂ X de cardinal k − 1 tel que le sous graphe engendré par X − S n’est pas
connexe. En d’autres termes, en supprimant moins de k sommets, le graphe sera toujours
connexe.

Exemple
Ce graphe orienté complet à 3 sommets est 2-sommet-connexe
G est k-sommet-connexe si et seulement si le graphe reste
fortement connexe, c'est-à-dire 1-arc-connexe, quand on lui ôte k −
1 sommets.

Remarque
On définit la connectivité d’un graphe comme étant le plus grand k tel que G est k-connexe.

13
[Link] Informatique 3 Théorie des graphes

7.4 Forte Connexité

Définition 3 Un graphe orienté G=(X, U) est fortement connexe (f.c.) s’il existe entre chaque
paire de sommets x et y X (x y) un chemin de x à y et un chemin de y à x .

7.5 Composantes fortement connexes (C.F.C.)

Soit G=(X, U) un graphe orienté :

Si le sous graphe engendré par un ensemble de sommets S ⊂ X (GS) est fortement connexe et le
sous graphe engendré par S ∪ x et x S n’est pas fortement connexe Alors GS est une
composante fortement connexe de G.

Exemples :

Ce graphe a deux composantes fortement connexes {a,b} et {c}

Ce graphe a trois composantes fortement connexes {1,7}, {2 ,3,5,6} et

{4}

7.5 .1 Algorithmes de calcul des composantes fortement connexes

Soit G = (X,U) un graphe orienté, On définit pour chaque sommet x X deux ensembles :

– L’ensemble des descendants de x : D(x) = {y X/x σ y}

– L’ensemble des ascendants de x : A(x) = {y X/y σx}

Principe : A partir d’un sommet r, on calcule la c.f.c. à laquelle appartient r.

– On calcule l’ensemble des descendants de r (noté D).

– On calcule l’ensemble des ascendants de r (noté A).
– c.f.c. est {r} ∪ A ∩ D.

Données :
En entrée :
– X : ensemble de n éléments représentant les identificateurs des sommets.
– U : ensemble de m éléments sous forme (i, j) représentant les arcs où i, j X
– r : identificateur d’un sommet de X qu’on appelle racine.

En sortie :
– CFC : sous-ensemble de X. Le sous graphe engendré par cet ensemble représente une composante
fortement connexe.

14
[Link] Informatique 3 Théorie des graphes

Autres :
– i, j : variables sommets.
– Marque : vecteur de n éléments booléens.
– A, D : sous-ensembles de X. Ils représentent l’ensemble des ascendants et l’ensemble des
descendants de la racine.

L’algorithme :
(* Initialisation *)
D ← {r} ;
Pour tout i X Marque[i] ← faux ;
(* Recherche des descendants de r *)
Tant que (∃ i D) et (Marque[i] = faux)
Marque[i] ← vrai ;
Pour tout (i, j) U D ← D ∪ {j} ;
(* Reinitialisation *)
A ← {r} ;
Pour tout i X Marque[i] à faux ;
(* Recherche des ascendants de r *)
Tant que (∃ i A) et (Marque[i] = faux)
Marque[i] ← vrai
Pour tout (j, i) U A ← A ∪ {j} ;
(* Calcul de la C.F.C. *)
CFC ← D ∩ A;

7.6 Graphe réduit

A tout graphe orienté G = (X,U) on associe le graphe simple GR = (XR,UR) appelé graphe réduit de
G défini comme suit :

XR = {A chaque c.f.c. Ci de G correspond un sommet Ci}

UR = {(Ci,Cj)/i j et ∃ x Ci et ∃ y Cj et (x, y) U}

Exemple

Ce graphe G n’est pas fortement connexe, car on ne

peut pas trouver de chemin de A à D par exemple. Par
contre, on identifie deux composantes fortement
connexes A’ = {A,B,C}et B’ = {D,E}.

Le graphe réduit GR du graphe G est:

Remarque 6
- Un graphe fortement connexe possède une seule C.F.C.
- Le graphe réduit d’un graphe ne possède pas de circuits.

15
[Link] Informatique 3 Théorie des graphes

8. Parcours Eulériens

La ville de Koenigsberg possède deux iles (représentées par les régions A et B dans la figure
1.15(a)) et sept ponts. Le problème revient à trouver un cycle qui passe une seule fois par chacun
de ses ponts et revient à son point de départ. Euler prouva que ce problème n’avait pas de
solution et trouva une généralisation du problème.

Figure 1.15 Les ponts de Koenigsberg (a) et le graphe correspondant.

Définition 1
Un parcours Eulérien passe une fois et une seule fois par chaque arête (resp. arc) du graphe. Le
parcours peut être une chaine, un chemin, un cycle ou un circuit. Soit G un graphe contenant m
arêtes (resp. m arcs) : Une chaine simple, un chemin simple, un cycle simple ou un circuit simple
de longueur m est appelé Eulérien.

8.1 Chaine Eulérienne

Une chaine Eulérienne est une chaine qui passe par toutes les arêtes du graphe exactement une
fois. Si la chaine est fermée, il s’agit d’un cycle Eulérien.
8.2 Chemin Eulérien
Un chemin Eulérien est un chemin qui passe par tous les arcs du graphe exactement une fois. Si
le chemin est fermé, il s’agit d’un circuit Eulérien.
8.3 Graphe Eulérien
Un graphe connexe est dit graphe Eulérien si et seulement si il admet un cycle eulérien.

Exemple
Il s’agit d’une généralisation du jeu bien connu consistant à dessiner toutes les arêtes d’un graphe
avec un crayon sans jamais le soulever, ni passer deux fois sur la même arête. Ce graphe admet
une chaine eulérienne mais il est non eulérien car il n’admet pas un cycle eulérien.

………………..

Théorème 1 Euler 1766

Un multigraphe G admet une chaine Eulérienne si et seulement si il est connexe (à des
points isoles près) et le nombre de sommets de degré impair est 0 ou 2.

Théorème 2:
Un graphe connexe est eulérien si et seulement si tous ses sommets ont un degré pair.

Le graphe de la figure 1.15(b) n’est pas eulérien car les sommets A,B,C et D ont un degré impair.

16
[Link] Informatique 3 Théorie des graphes

Conséquences
- Un graphe G admet une chaine Eulérienne d’un sommet x a un sommet y (x y) si et
seulement si dG(x) et dG(y) sont impairs et ∀z sommet de G (z x et z y), on a dG(z) pair.

- Un graphe G admet un cycle Eulerien si et seulement ∀x sommet de G, on a dG(x) pair.

Proposition 1
Un graphe G = (X,U) admet un circuit Eulérien si et seulement si pour tout sommet x, on a
d+G(x) = d− G(x).

9. Parcours Hamiltoniens

Le problème Hamiltonien, inventé par W. Hamilton, revient à déterminer pour un ensemble de

villes un itinéraire permettant de passer une et une seule fois par chaque ville et revenir au point
de départ. La figure 1.16 illustre ce type de problème.

Figure 1.16 Représentation du problème Hamiltonien. Figure 1.17 Graphe G1.

Définition 1
Un parcours Hamiltonien passe une fois et une seule fois par chaque sommet du graphe. Le
parcours peut être une chaine, un chemin, un cycle ou un circuit. Soit G un graphe d’ordre n
(contenant n sommets) : Une chaine (resp. un chemin) elementaire de longueur n − 1 est appelé
chaine Hamiltonienne (resp. chemin Hamiltonien). Un cycle (resp. circuit) elementaire de
longueur n est appele cycle (resp. circuit) Hamiltonien.

9.1 Chaine Hamiltonienne

Une chaine Hamiltonienne est une chaine qui visite chaque sommet du graphe exactement une
fois. Un cycle Hamiltonien est donc une chaine Hamiltonienne fermée.
Si on considère le graphe G1 de la figure 1.17, on peut voir que la séquence (x4, x5, x6, x3, x2,
x1) représente une chaine Hamiltonienne.

9.2 Chemin Hamiltonien

Un chemin Hamiltonien est un chemin qui visite chaque sommet du graphe exactement une fois.
Un circuit Hamiltonien est donc un chemin Hamiltonien fermé.
Si on considère le graphe G1 de la figure 1.17, on peut voir que la séquence (x3, x6, x5, x4, x2,
x1) représente un chemin Hamiltonien.

9.3 Graphe Hamiltonien

Un graphe Hamiltonien est un graphe qui admet un cycle Hamiltonien. Le graphe G1 de la figure
1.17 ne comporte pas de cycle Hamiltonien car il est impossible de x1 de revenir à x4. Par
conséquent, ce graphe n’est pas Hamiltonien.

17
[Link] Informatique 3 Théorie des graphes

Remarques :
Contrairement aux graphes eulériens, il n’existe pas de caractérisation simple des graphes
hamiltoniens. On peut cependant énoncer quelques propriétés et conditions suffisantes.

1. Un graphe possédant un sommet de degré 1 ne peut être hamiltonien.

2. Si un sommet dans un graphe est de degré 2, alors les deux arêtes incidentes à ce sommet
doivent faire partie du cycle hamiltonien.
3. Les graphes Kn sont hamiltoniens. (Kn étant un graphe complet de n sommets)

Théorème 1 (Ore) Soit G = (X,A) un graphe simple d’ordre n ≥ 3 . Si pour toute paire de
sommets {x, y} non adjacents, on a d(x) + d(y) > |X | alors G est hamiltonien.

Corollaire (Dirac) Soit G = (X,A) un graphe simple d’ordre n ≥3 Si pour tout sommet x de G
on a d(x ) ≥ n/2 alors G est hamiltonien.

Condition nécessaire
La contraposée du théorème suivant fournit une condition nécessaire pour avoir un graphe
hamiltonien.

Théorème 1
Le théorème ci-dessous est utilisé pour démontrer qu’un graphe n’est pas Hamiltonien (ne
contient pas de cycle Hamiltonien). Si G = (X,E) est un graphe Hamiltonien, alors pour tout
ensemble de sommets S ⊂ X, on a : p(GX−S) |S| ou p(GX−S) est le nombre de composantes
connexes du sous graphe de G induit par l’ensemble X − S.

En d’autres termes, si on retire k nœuds

quelconques d’un graphe hamiltonien, on
obtient au plus k composantes connexes.
Voir figure (1.18).

Figure 1.18 Graphe Hamiltonien ses composantes

connexes après avoir retirer k sommets.
Exemple:
Le graphe suivant n’est pas hamiltonien car en enlevant les 3 nœuds noirs, on obtient 4
composantes connexes.

18
[Link] Informatique 3 Théorie des graphes

10. Coloration des Graphes

10.1 Coloration des sommets

La coloration des graphes (sommets) consiste à associer à chaque sommet une couleur de telle
façon que chaque sommet adjacent n’est pas la même couleur

10.1 .1. Définition du nombre chromatique

Le nombre chromatique d'un graphe G est le nombre minimum de couleurs nécessaires à sa

coloration, c’est-à-dire le plus petit nombre de couleurs permettant de colorier tous les sommets
du graphe sans que deux sommets adjacents soient de la même couleur. On le note c.

Propriété 1
c <= d+1 où d : est le plus grand degré des sommets du graphe
Propriété 2
n<= c où n : est l’ordre du sous graphe complet d’ordre le plus élevé. (la Clique
maximale)
Propriété 3 Le nombre chromatique d’un graphe complet est égal à son ordre.

10.1.2. Algorithme de coloration

Un algorithme couramment utilisé est celui de Welsh & Powell. Il permet d'obtenir une assez
bonne coloration d'un graphe, c'est-à-dire une coloration n'utilisant pas un trop grand nombre de
couleurs. Cependant il n'assure pas que le nombre de couleurs utilisé soit minimum (et donc égal
au nombre chromatique du graphe).

Algorithme de Welsh Pawell

Étape 1 Classer les sommets du graphe dans l'ordre décroissant de leur degré, et attribuer à
chacun des sommets son numéro d'ordre dans la liste obtenue.

Étape 2 En parcourant la liste dans l'ordre, attribuer une couleur non encore utilisée au premier
sommet non encore coloré, et attribuer cette même couleur à chaque sommet non encore coloré
et non adjacent à un sommet de cette couleur.

Étape 3 S'il reste des sommets non colorés dans le graphe, revenir à l'étape 2. Sinon, la
coloration est terminée.

10.1 .3. Notion de clique/stable

- Un stable est un sous-graphe sans arête.

Déf : On appelle stable dans un graphe G un sous-ensemble de sommets S ⊆ X et le sous

graphe engendre par S est forme de sommets isoles (ne contient aucun arc ou arête).

19
[Link] Informatique 3 Théorie des graphes

Dans le graphe de la figure 1.19 ci contre :

L’ensemble de sommet s = {x1, x3} est un stable.

L’ensemble de sommet s′ = {x2, x4} est un autre
stable.
Figure 1.19 Exemple de graphe

- Une clique est un sous-graphe complet.

Déf : On appelle clique dans un graphe G un sous-ensemble de sommets C ⊆ X ou le sous
graphe engendre par C est un graphe complet.
L’ensemble de sommet {x1, x4, x5} est une clique.

Remarques
- Chaque partition d’un graphe biparti est un stable.
- Si S est le plus grand stable dans G Alors |S|<= nombre de cliques dans G et
|S| =nombre minimal de cliques dans G.
- Une coloration avec k couleurs est donc une partition de l'ensemble des sommets en k
stables.
- Le nombre chromatique du graphe G, est le plus petit entier k pour lequel il existe une
partition des sommets en k sous-ensembles stables.

10.2. La coloration des arêtes

La coloration des arêtes d'un graphe consiste à affecter à toutes les arêtes de ce graphe une
couleur de telle sorte que deux arêtes adjacentes ne portent pas la même couleur.
L'indice chromatique du graphe G est le plus petit entier k pour lequel il existe une coloration des
arêtes.
Pour colorer les arêtes d'un graphe, on peut se ramener au problème de la coloration des
sommets. Il suffit pour cela de travailler non pas sur le graphe lui-même, mais sur le graphe
adjoint, noté G', et que l'on définit ainsi :
 à chaque arête de G = (V, E) correspond un sommet de G' = (E, F)
 deux sommets de G' sont reliés par une arête si les deux arêtes correspondantes de G
sont adjacentes.
On peut ensuite appliquer par exemple l'algorithme de Welsh et Powell sur le graphe G' pour
colorer ses sommets. Une fois cela fait, on colorera les arêtes de G de la même couleur que les
sommets correspondants de G'. Exemple de coloration d'arêtes.

Son graphe Coloration des Coloration des

Un graphe G
adjoint G’ sommets de G' arêtes de G

20