Institut international 2I

Niveau : Licence RT, DI, GL

Département Génie Informatique
Module : Mathématiques Discrètes

Conçu et Présenté par : MAMPEME SITA

Année Universitaire : 2025/2026

Chapitre 1. Les notions de base

Bref historique de la théorie des graphes

La théorie des graphes constitue un domaine des mathématiques qui, historiquement, s’est
aussi développée au sein de diverses disciplines telles que la chimie (modélisation de
structures), la biologie (génome), les sciences sociales (modélisation des relations) ou en vue
d’applications industrielles (problème du voyageur de commerce), etc. Elle constitue l’un des
instruments les plus courants et les plus efficaces pour résoudre des problèmes discrets posés
en recherche opérationnelle.

La théorie des graphes est née en 1736 quand le mathématicien suisse Leonhard Euler
démontra qu’il était impossible de traverser chacun des sept ponts de la ville russe de
Königsberg (aujourd’hui Kaliningrad) une fois exactement et de revenir au point de départ. A
l’époque, la ville de Königsberg était une ville constituée de 4 régions reliées entre elles par 7
ponts. Le problème que se posaient les habitants de Königsberg « Est-il possible de prendre
une marche dans la ville qui nous fasse passer par chaque pont exactement une fois chacun ».

Figure 1. Schéma des 7 ponts de Königsberg.

Les points A, B, C, D sont des rives.

Leonhard Euler résolve le problème dans un article publié en 1736, où il démontra que le
problème en question n’a pas de solution. Sa démonstration est basée sur un schéma simplifié
du problème posé. L’article est considéré comme l’élément fondateur de la théorie des
graphes. Jusqu’en 1946, la théorie des graphes resta du domaine des mathématiques.

Depuis, l’avènement de plusieurs domaines a provoqué un développement intense de la

théorie des graphes sous l’impulsion de chercheurs motivés par la résolution de problèmes
concrets. La recherche opérationnelle née des recherches militaires durant la période de la
seconde guerre mondiale 1939-1945 fut la première à avoir considéré la théorie des graphes
comme modèles des problèmes concrets. Cet aspect fut renforcé dans les années qui suivent
par le développement des Sciences économiques et de gestion, et l’arrivée des Sciences de
l’Information et de la communication dans les années 60. De grands spécialistes de cette
nouvelle orientation comme Khun, Ford, Fulkerson, Danzing, Bellman, Roy Dyjskra, Knuth,
Kruskal, Prim, Hasse, etc. ont participé d’une part au développement de l’aspect Modélisation
des problèmes concrets et d’autre part à l’Algorithmique des graphes.

La théorie des graphes constitue actuellement un corpus de connaissances très important et

un outil puissant de modélisation et de résolution de problèmes concrets. La représentation
d’un problème par un graphe contribue souvent à sa compréhension. Les problèmes de graphe
se rattachent à la grande classe des problèmes d’optimisation combinatoire. Tous ces

1
Chapitre 1. Les notions de base

problèmes se répartissent en deux catégories, ceux qui sont résolus d’une manière optimale
par des algorithmes efficaces (rapides) et ceux dont la résolution peut prendre un temps
exponentiel sur les grands cas. On parle respectivement d’algorithmes polynomiaux et
exponentiels.

2
Chapitre 1. Les notions de base

1. Définitions de base
1.1. Notion de Graphe
(a) Un graphe orienté G est la donnée d’un ensemble X dont les éléments sont appelés
« sommets » et d’un ensemble U un sous ensemble de X2 dont les éléments sont appelés
« arcs ». Le nombre de sommets de G est appelé ordre du graphe. On note G=(X, U).

Exemple

(b) G est dit un p-graphe si le nombre maximal d’arcs de même type est égal à p. Un 1-
graphe est dit simplement un graphe.

Exemple

2-graphe

(c) Un graphe non orienté est un couple formé de 2 ensembles, un ensemble de sommets X
et un ensemble d’arêtes ̅ , une partie P(X) de l’ensemble des paires à 2 éléments de X.

Exemple

(d) Un multigraphe est un p-graphe non orienté, c’est à dire, un graphe qui contient des
arêtes multiples entre deux sommets ainsi que des boucles multiples en un sommet.

Exemple
Chapitre 1. Les notions de base

1.2. Arc
(a) Un arc relie deux nœuds entre eux, il sera donc représenté par un couple (x, y) où x et y
sont des nœuds.
𝑥 𝑦
Pour un arc u = (x, y), on dit que :
 x est le prédécesseur de y.
 y est le successeur de x.
 x est l’origine (ou extrémité initiale) de u.
 y est l’extrémité (ou extrémité finale) de u.

Pour un sommet x, l’ensemble de ses successeurs est noté +(x) et l’ensemble de ses
prédécesseurs est noté -(x). L’ensemble des voisins de x (successeurs et prédécesseurs) est
noté (x). + et - sont respectivement les applications successeur et prédécesseur définies de
X vers une partie de X.  est l’application qui fait correspondre à tout élément de X une partie
de X.  est appelée application multivoque.

+(x)= {y  X / (x, y)  U}
-(x)= {z  X / (z, x)  U}
(x) = +(x)  - (x)

(b) Un arc peut ne pas être orienté et dans ce cas il est appelé arête. L’ordre de x et de y
n’a pas d’importance dans le couple (x, y). Une arête est notée {x, y}.
𝑥 𝑦

Pour une arête u = {x, y}, on dit que :

 x est adjacent à y.
 y est adjacent à x.
 x et y sont adjacents à u.
 u est adjacent à x et y.

Une arête {x, y} peut toujours être transformée en une situation où l’on n’a que des arcs (x,
y) et (y, x).
𝑥 𝑦
𝑥 𝑦
𝑥 𝑦

1.3. Boucle
On appelle boucle un arc dont l’extrémité initiale coïncide avec son extrémité finale. Par
exemple, (x, x) est une boucle.

x
Un 1-graphe ne possédant pas de boucle est dit graphe simple.
Un 1-graphe possédant une boucle en chaque sommet est dit graphe réflexif.

8
Chapitre 1. Les notions de base

1.4. Degré d’un sommet : demi-degré interne et demi-degré externe

Dans un graphe orienté G=(X,U)

- Le demi-degré externe d'un nœud x est le nombre d'arcs adjacents qui en partent. On le
note d+(x) :
d+(x) = {u  U / u = (x, y) où y  X}.
=  + (x).
- Le demi-degré interne d'un nœud x est le nombre d'arcs adjacents qui y arrivent. On le
note d-(x) :
d-(x) =  {u  U / u = (y, x) où y  X} .
=  - (x).
- Le degré d'un nœud x est le nombre d'arcs qui lui sont adjacents. On le note d(x) :
d(x) = d+(x) + d-(x).

Exemple
Dans le graphe suivant, d+(b) = 2, d-(b) = 2, et d(b) = 4.
a
b

c
d

Remarque
- Dans un graphe non orienté, le degré d’un nœud x est le nombre d’arêtes incidentes à x.
- Si d(x) = 0, x est un sommet isolé.
- Si d(x) = 1, x est dit sommet pendant.
- Si d(x) = |X|-1, x est dit sommet dominant.

Propriétés
- La somme des demi-degrés internes (ou externes) de tous les sommets d’un graphe
correspond au nombre total d’arcs du graphe :

∑ ( ) ∑ ( ) | | d’où ∑ ( ) | |

- Un graphe est dit régulier si tous ses sommets ont le même degré.

1.5. Sous graphe - Graphe partiel

Soit un graphe G = (X, U), soit X’ un sous ensemble de X, et U’ un sous ensemble de U.

Soit U" = {(x, y)  U  x  X' et y  X'} :

 Le graphe (X', U") est appelé "sous-graphe" de G engendré par X’: c’est le graphe
obtenu par suppression de tous les sommets de X-X' (la suppression d’un sommet x
engendre la suppression de son cocycle W(x)).
 Le graphe (X, U') est appelé "graphe partiel" de G : c’est un graphe obtenu par
suppression des arcs de U-U' (la suppression d’un arc n’engendre pas la suppression
de ses sommets).
 Le graphe (X', U'-U") est appelé "sous-graphe partiel" de G : c’est un graphe partiel
d’un sous graphe.

9
Chapitre 1. Les notions de base

Exemple

B D B D B D
A B D A A

C C C C E
E E E

F F F

Un graphe de G Un sous-graphe de G Un graphe partiel de G Un sous-graphe

partiel de G
1.6. Graphe complémentaire

Un graphe complémentaire ̅ ( ̅ ) d’un graphe G = (X, U) est tel que :

x, y  X, (x, y) U (x, y)  ̅
Exemple
B
A

Son graphe complémentaire est :

A
B

1.7. Cocycle

Soit G = (X, U) un graphe donné, et soit A un sous ensemble de X.

- Un cocyle externe de A est l’ensemble d’arcs qui en partent, on le note W+(A):
W+(A) = {(x, y)  U x  A et y A}
- Un cocyle interne de A est l’ensemble d’arcs qui y arrivent, on le note W-(A).
W-(A) = {(x, y)  U x A et y  A}
- Un Cocycle de A est l’ensemble d’arcs qui en partent et qui y arrivent, on le note W(A).
W (A) = W+ (A)  W-(A)
Exemple
a
b

c
d

A= {b, d}; W+ (A) = {(d, c)}, W-(A) = {(a, b), (c, d)} et W (A) = {(a, b), (c, d), (d, c)}

10
Chapitre 1. Les notions de base

2. Représentation d’un graphe

Soit G = (X, U) un graphe donné, où X est l’ensemble des nœuds et U l’ensemble des arcs.
La représentation de G existe sous plusieurs formes : Sagittale, chaînée, matricielle ou latine.

2.1. Représentation sagittale

Dans cette représentation, les sommets sont représentés par des points «.» ou des croix
« x » et les arcs sont représentés par des flèches, ou des traits ou autres joignant les sommets
dans les cas des arêtes.

Exemple
a
a b
b
x

Boucle c c
d
d
1-graphe 2-graphe
y x
z
x

y
z
Graphe non orienté Multigraphe

Un graphe planaire est un graphe non orienté pouvant être représenté de telle sorte que
les sommets soient des points distincts, et que les arêtes ne se rencontrent pas en dehors de
leurs extrémités (les arêtes pouvant être représentées par des courbes). Un même graphe peut
être dessiné de différentes façons. Certaines de ces représentations peuvent ne pas être
planaires, alors que d’autres peuvent l’être. Il suffit de trouver une représentation planaire
pour en conclure que le graphe est planaire.

Les régions d’un graphe planaire sont appelées faces limitées par des arêtes.

Les deux graphes suivants possèdent respectivement 5 faces notées (A, B, C, D, E) et 4

faces (A’, B’, C’, D’) :

b d
a 1 2
A
D D’
A’
B E 5 C’
c e
B’
C 7
6
4
f 3

11
Chapitre 1. Les notions de base

2.2. Représentation chaînée

Soit G=(X, U), tel que X = n et |U| = m, la représentation chaînée consiste à utiliser deux
tableaux (.) et (.) tels que :

- (.) est de dimension n+1 et représente pour chaque sommet i de X l’adresse de ses
successeurs contenus dans (.),
- (.) est de dimension m (cas d’un graphe orienté) ou 2m (cas d’un graphe non orienté).

Pour chaque sommet i de X, la liste de ses successeurs est contenue dans le tableau  à
partir du contenu de la case (i). Ainsi l’ensemble des informations relatives au sommet i est
contenu entre les cases (i) et (i+1)-1.

Exemple

2.3. Représentation matricielle

Soit G = (X, U) un graphe d’ordre n. La représentation matricielle de G existe sous
plusieurs types.

2.3.1. Matrice incidence sommet-sommet

Soit M =( ) la matrice incidence sommet-sommet de G. M est une matrice est carrée
d’ordre n à valeur 0 ou 1 :

( )
( ) {

Exemple

c
a

a b c
a 1 1
b 1 1
b
c 1 1

2.3.2. Matrice incidence Sommet-arc

Soit M =( ) la matrice incidence sommet-arc. Cette matrice est d’ordre (n x m) ou
(n x 2 m) (dans le cas où G n’est pas orienté) à valeur 0, 1 ou -1.

12
Chapitre 1. Les notions de base

( )
( ) { ( )

Exemple
Pour le graphe précédent, on a la matrice suivante :

(a,a) (a,a) (a,b) (b,a) (b,c) (c,a) (c,b)

a 1 -1 -1 1 0 1 0
b 0 0 1 -1 -1 0 +1
c 0 0 0 0 1 -1 -1

2.3.3. Matrice latine

Soit M =( ) la matrice latine. Cette matrice est carrée d’ordre n (où n = |X|).
( )
( ) {
Exemple

a b c
a aa ab
b ba bc
c ca cb

13
Chapitre 1. Les notions de base

3. Nature d’un graphe

3.1. Graphe complet
Un graphe G = (X, U) est dit complet si tous les nœuds de X sont adjacents deux à deux.
Autrement dit x, y  X, xy : si (x, y) U alors (y, x)  U.
Avec la notation matricielle incidence sommet-sommet de G, G est dit complet si pour tout
sommet x, y de X, si mxy = 0 alors myx = 1 (xy).

Un graphe simple complet d’ordre n est appelée clique à n sommets notée Kn.

Exemple

Graphe complet Graphe non complet

B B
A A

C C

Clique d’ordre 4 (K4)

A B

C D

3.2. Graphe symétrique

Un graphe G=(X, U) est dit symétrique si  x, y  X, si (x, y)  U => (y, x)  U. La
matrice incidence sommet-sommet d’un graphe symétrique est symétrique, c’est à dire pour
tout sommet x et y de X, mxy = myx.

Exemple
Graphe symétrique
Graphe non symétrique
B
A
B
A

C C

14
Chapitre 1. Les notions de base

3.3. Graphe antisymétrique

Le graphe G est dit antisymétrique si  x, y  X, si (x, y)  U => (y, x) U. La matrice

incidence sommet-sommet correspondante est antisymétrique, c’est à dire pour tout sommet x
et y, mxy + myx ≤ 1 (si mxy = 1 alors myx = 0).

Exemple
Graphe antisymétrique
B
A

Graphe non antisymétrique

B
A

16
Chapitre 1. Les notions de base

3.4. Graphe biparti

Un graphe G=(X, U) est dit biparti si :

a. L’ensemble de ses sommets X est partitionné en deux sous ensembles disjoints :

X1 et X2 : X = X1 X2 et X1  X2 =.
b. Les sommets de X1 (respectivement X2) ne sont pas adjacents entre eux :
 x, y  X1, (x, y) et (y, x) U et  x, y  X2, (x, y) et (y, x) U.

Exemple
A C

B D
E
F

G
X1 X2

16
Chapitre 1 : Notion de Graphe / Cours No 2

4. Chemins, chaînes, circuits, cycles

4.1. Chemin
Un chemin de x à y est une chaîne dans laquelle les arcs sont orientés tels que:
 x est l'extrémité initiale du premier arc,
 y est l'extrémité terminale du dernier arc,
 l'extrémité terminale d'un arc est l'extrémité initiale de l'arc qui le suit dans la
séquence.

On le note  x, y  .

Exemple

ch1= ((A, C),(C ,E)) est un chemin de A à E.

B D
A ch2 = ((A, C),(C, F),(F, A),(A, C),(C, E)) est un
chemin de A à E.
C
E
ch3 = ((A, C),(C, F),(F, D),(D, C),(C, E)) est un
chemin de A à E.
ch4 = ((F,A) ,(A, C),(C, E)) est un chemin de F à
F E.
ch5= ((F,D), (D,E)) est un chemin de F à E.

Définitions
1-Un chemin est dit simple s’il ne contient pas plusieurs fois le même arc.
ch1 et ch3 sont des chemins simples, ch2 n’est pas un chemin simple.
2-Un chemin est dit élémentaire s’il ne passe pas plus d'une fois par le même nœud.
ch1 est un chemin élémentaire, ch2 et ch3 ne le sont pas.
3-Un chemin hamiltonien est un chemin élémentaire qui passe par tous les sommets du
graphe.

4.2. Chaîne
Une chaîne de x à y, notée  x, y  , est une suite d’arêtes telle que :
 x est l'extrémité initiale de la première arête,
 y est l'extrémité terminale de la dernière arête,
 l'extrémité terminale d'une arête est l'extrémité initiale de l'arête qui la suit dans la
séquence.
Exemple
B D ch4 = ((A,B),(B,D),(D,E)) est une chaîne de A à E.
A
ch5 = ((A,B),(B,D),(D,C),(C,A),(A,B),(B,D),(D,E)) est
une chaîne de A à E.
C E ch6 = ((A,B),(B,D),(D,C),(C,F),(F,D),(D,E)) est une
chaîne de A à E.
ch7=((A,F),(F,D),(D,E),(E,C),(C,D),(D,B),(B,A),(A,C),(
F
C,F)) est une chaîne de A à F.

2
Chapitre 1 : Notion de Graphe / Cours No 2

Définitions
1-Une chaîne est dite simple si elle ne contient pas plusieurs fois la même arête.
ch4, ch6 et ch7 sont des chaînes simples, ch5 ne l’est pas.
2-Une chaîne est dite élémentaire si elle ne contient pas plusieurs fois le même nœud.
ch4 est une chaîne élémentaire, ch5, ch6, ch7 ne le sont pas.
3-Une chaîne eulérienne est une chaîne simple qui contient toutes les arêtes du graphe.
Ch7 est une chaîne eulérienne.

4.3. Circuit
Un circuit est une séquence circulaire d'arcs, c’est à dire un chemin fermé de x à x. Donc,
contrairement au chemin, son début et sa fin coïncident.

Exemple
ch8 = ((A, C), (C, F), (F, A)) est un circuit de A à A.
A B D
ch9= ((C, F), (F, D), (D, C)) est un circuit de C à C.
ch10= ((C, E), (E, D) (D, C)) est un circuit de C à C.
C E ch11 = ((C, E), (E, D), (D, E), (E, C)) est un circuit de C à C.
ch12 = ((C, E), (E, D), (D, E), (E, D), (D, C)) est un circuit de
C à C.
F

Définitions
1-Un circuit est dit simple s’il ne contient pas plusieurs fois le même arc.
Ch8 et ch9 sont des circuits simples et ch12 n’est pas un circuit simple.
2-Un circuit est dit élémentaire s’il ne passe pas plus d'une fois par le même nœud.
Ch8, ch9 et ch10 sont des circuits élémentaires et le ch10 n’est pas élémentaire.
3-Un circuit hamiltonien est un circuit élémentaire qui passe par tous les sommets du
graphe.

4.4. Cycle
Un cycle est une séquence circulaire d'arêtes, c'est-à-dire, une chaîne de x à x.
Donc, contrairement à la chaîne son début et sa fin coïncident.
A B D ch7 = ((A, C), (C, F), (F, A)) est un cycle de A à A;
ch8 = ((C, F), (F, D), (D, C)) est un cycle de C à C.

C E

Définitions
1-Un cycle est dit simple s’il ne contient pas plusieurs fois la même arête.
ch7 et ch8 sont des cycles simples.
2-Un cycle est dit élémentaire s’il ne passe pas plus d'une fois par le même nœud.
ch7 et ch8 sont des cycles élémentaires.
3-Un cycle eulérien est une chaîne eulérienne dont les extrémités coïncident.
4-Un graphe eulérien est un graphe qui contient un cycle eulérien.

3
Chapitre 1 : Notion de Graphe / Cours No 2

Exemple
Dans le graphe suivant la chaîne (AB, BI, IC, CJ, JI, IG, GE, ED, DF, FH, HK, KJ) est une
chaîne eulérienne :

A B C

D E G I J

F H K

5. Détection de circuits

Dans un graphe orienté sans circuit, il existe au moins un sommet sans prédécesseurs ou
sans successeurs. Ceci constitue une condition nécessaire et suffisante pour vérifier l’absence
de circuit dans un graphe.

Algorithme 1
Soit G = (X, U) orienté
Tant qu’il existe x ∈ X tel que d− (x)=0,
G =G – {x} ;
Si G=∅ Alors " G est sans circuits"
sinon "G possède un circuit".

Algorithme 2
Soit un graphe G = (X, U).
1- Enumérer pour chaque sommet ses successeurs (prédécesseurs)

Sommet x Successeurs de x

2-Chercher un sommet sans successeurs (prédécesseurs) et barrer le sommet partout où il

apparaît
3- itérer la procédure jusqu’à ce qu’il n’y ait plus de sommet
4- Si à la fin de la procédure, tous les sommets sont barrés, le graphe est sans circuits,
sinon il en possède au moins un.

Exemple 1

Sommet x Successeurs de x
B D A B, C
A
B
C E, F
C E D B, C, E
E
F A, D
F

Les sommets A, C, D et F ne sont pas barrés, le graphe possède au moins un circuit.

4
Chapitre 1 : Notion de Graphe / Cours No 2

Exemple 2
Sommet x Prédécesseurs de x
B D A C, F
A
B A, D
C
C D, F
E D F
E C, D
F
F

Tous les sommets sont barrés, le graphe est donc sans circuits.

5. Graphe ordinal
Un graphe ordinal est un graphe simple sans circuits. La fonction ordinale est la fonction f
qui associe à chaque sommet x d’un graphe ordinal une valeur f(x).

Soit G =(X, U) un graphe ordinal. L’ensemble de ses sommets X peut être partitionné en k
sous ensembles appelés niveaux No, N1, N2, … Nk -1 de la manière suivante :

No = {x  X / -(x) =}
N1 = {x  X - No / -(x)  No}
N2 = {x  X - No  N1 / -(x)  No  N1} …
 k 1 k 1

N k   x  X   N i /  ( x)   

i 0 i 0
 
∈ ( )

Remarque
- Les sommets d’un même niveau ne sont pas liés entre eux.
- Le 1èr niveau correspond à tous les sommets sans prédécesseurs
- Le dernier niveau peut ne pas correspondre à tous les sommets sans successeurs.

Algorithme
1- Former la matrice incidence sommet-sommet du graphe ;
2- Former une ligne Lo où chaque case i est la somme de la Ième colonne de la matrice ;
3- Les zéros de Lo correspondent à tous les sommets de niveau No ;
4- Enlever à la ligne Lo, la somme des lignes correspondant aux sommets de No, on
obtient la ligne L1. Les zéros de la ligne L1 représentent les sommets de niveau N1 ;
5- Réitérer le processus jusqu’à épuisement de tous les sommets.

Exemple
B
C K
E
A
G

J
D
F A
H I

5
Chapitre 1 : Notion de Graphe / Cours No 2

A B C D E F G H I J K
A 1 1 1
B 1 1 1
C 1 1
D 1 1
E
F
G 1 1
H
I
J 1 1
K 1 1 1
L0 0 0 1 2 2 3 2 2 3 1 1
L1 - - 0 0 2 2 1 2 3 1 0
L2 - - - - 1 0 0 1 2 0 -
L3 - - - - 0 - - 0 0 - -

Le graphe possède 4 niveaux :

No = {A, B} N1 = {C, D, K} N2 = {F, G, J} N3 = {E, H, I}

Le graphe donné est représenté en 4 niveaux de la manière suivante :

A
A F E
C

D G H

B
J
K I

6
Chapitre 2 : Connexité d’un graphe

1. Fermeture transitive directe d’un sommet

Soit G= (X,U), un graphe donné, on appelle fermeture transitive directe d’un sommet x,
l’ensemble des sommets y liés à x par un chemin de longueur quelconque de x vers y. On
note :

̂ { }y X/ ⃗


x, y  est un chemin de longueur quelconque, autrement dit, c’est l’ensemble des
Successeurs de degré quelconque :
 +1 +2 +3 +i
̂ { }   ix= {x}   {x}   {x}   {x}  ...  {x} ...
i 0


 x  .


Exemple
a b

e
c d

0 {a} = {a} ; + {a} = {b,c,d}

+2 {a} = +{b,c,d} = + {a} + {b}+{c}+{d}
= {b,c,d}  {b,e ,f}  {d,a}  {e,f} = {b,c,d,e,f}
+3 {a} = +{b,c,d,e,f} = + {a}  + {b}  +{c}  +{d}}  +{e}  +{f}
= {b,c,d,e,f}
̂ { } = {a,b,c,d,e,f}
Ou bien directement
̂ { } = {a}  {b,c,d}  {f,e}  
= {a,b,c,d,e,f}
 Chapitre 2 : Connexité d’un graphe

2. Fermeture transitive inverse d’un sommet

On appelle fermeture transitive inverse d’un sommet x, l’ensemble des sommets y liés
à x par un chemin de longueur quelconque de y vers x. On note :
̂ { ⃗⃗ }

⃗ (y, x) de longueur quelconque, autrement dit, c’est l’ensemble des successeurs de degré
quelconque : ̂ -{ } ⋃
- -
x = {x} - { } -
{ }
i 0
-
{ }
̂ - { } 


Exemple
-0 {a} = {a}, - {a} =  et donc ̂ -{ } {a}


 e

= {e}  - {e}  -2 {e}  -3{e}-4{e} …

= {e}  {b,d}  {a}  

= {a,b,d,e}

3. Classe d’un sommet

Une classe de x, notée C(x), désigne l’ensemble des sommets y liés à x par des chemins
de x vers y et de y vers x, de longueur quelconque. C(x) est donc l’intersection entre la
fermeture transitive directe et inverse de x :
 

  x   x
 
C(x) =
Exemple





f
c

 

 a   a = {a,b,c,d,e,f}  {a} = {a}

 
C(a) =

Remarque
 

 x   xest appelée une composante fortement connexe de x.

 
C(x) =

4. Graphe fortement connexe

Soit G= (X, U) un graphe orienté et soit R une relation définie par :

⃗⃗ ⃗⃗
 x, y  X, x R y { 
 Chapitre 2 : Connexité d’un graphe

Définition
G est dit fortement connexe, si tous ses sommets ont deux à deux la relation de forte
connexité. Autrement dit, G est fortement connexe si et seulement si :


 x  X  x  X


 ou
 

x  X
 x  X


Exemple
Graphe fortement connexe

Remarque
G n’est pas fortement connexe, si et seulement si :


 x  X  x  X


 ou
 

x  X
 x  X


Exemple
Graphe non fortement connexe:



 A  A B C  A, B,C  X



Le graphe possède 3 classes :

C1 = {A,B,C} C2= {D} C3={E }
 Chapitre 2 : Connexité d’un graphe

5. Graphe connexe

Pour un graphe non orienté, la relation de connexité est définie par l’existence de chaînes
entre deux nœuds quelconques du graphe.

Définition
G’ est dit connexe, si tous ses sommets ont deux à deux la relation de connexité.
Autrement dit G’ est connexe si et seulement si :

x  X ̂ { } = X

Le graphe suivant n’est pas connexe.

B

E
C

Il est composé de deux composantes connexes : C1= {A, B, C} et C2 = {D, E}.

Remarque :
Le nombre cyclomatique d’un graphe est le nombre de cycles : m – n + p, où m est le nombre
d’arêtes, n est le nombre de sommets et p le nombre de connexité.

6. Graphe réduit

On appelle graphe réduit d’un graphe G (X, U), le graphe G' (X’, U’) pour lequel
chaque nœud est associé à une composante fortement connexe de G. De plus, un arc relie un
nœud x' à un nœud y' dans le graphe G' si il existe un arc qui relie x à y dans G où x appartient
à la composante fortement connexe de G associée à x' et où y appartient à la composante
fortement connexe de G associée à y'.

G’ (X’, U’)/ X’ Ci/ Ci est une composante fortement connexe de G}

U’ (x,y), x,y  X’ /  x  Ci et y  Cj /(x, y)  U}

Chapitre 2 : Connexité d’un graphe

Exemple
Le graphe réduit du graphe précédent :
C1

C2 C3

7. Point d’articulation

Un sommet x est dit point d’articulation de G si en le supprimant le nombre de connexité

de G augmente.

Exemple
B

E
C

B est un point d’articulation : en supprimant B, on obtient 3 composantes fortement

connexes : C 1 = { A}, C 2 = {C}, C 3 = {D, E}.
E n’est pas un point d’articulation : en supprimant E du graphe, le nombre de
connexité ne change pas, bien que les composantes changent de sommet :
C1 = {A, B, C} et C2 = {D}.

Remarque
Un isthme est une arête dont la suppression augmente le nombre de connexité.