Chapitre : Théorie de graphes

Définitions et représentations des graphes

Pr. Aissam Hadri

2023-2024
 Plan

✓ Définitions des concepts utilisés dans toute la

suite du cours
✓ Définition d’un graphe
✓ Diverses représentations d’un graphe soient
graphiques, matricielles ou par listes.
✓ le concept de degré d'un sommet.
✓ Une étude des différents types de parcours que
l'on peut emprunter dans un graphe
 Graphes non orientés
■ La définition d'un graphe non orienté correspond tout
à fait à l'idée que l'on s'en fait intuitivement : un
ensemble de points, dont certains sont reliés par des
lignes parcourables dans les deux sens.

Définition
Un graphe non orienté G=(V,E) est la donnée :
1- D’un ensemble V dont les éléments sont appelés
les sommets du graphe.
2- D’un ensemble E dont les éléments sont des
parties à un ou deux éléments de V, et sont appelés
les arêtes du graphe.
 Exemple : Un graphe non orienté
■ Pour définir un graphe non orienté, il faut donc
commencer par décrire l'ensemble de ses sommets :
✓ V={A,B,C,D,E}
✓ On peut alors donner l'ensemble de ses arêtes
E={{A,B},{B},{B,C},{B,D},{C,D},{E,C}}

■ Remarques :
✓ L’ordre des éléments n’a pas d’importance. Ainsi
{A,B}={B,A}. On définit donc bien un graphe non
orienté, dans la mesure où les arêtes n'ont pas de
sens de parcours.
Représentation graphique : Représentation sagittale

Deux représentations équivalentes

 vocabulaire complémentaire

Définitions:
■ Deux sommets reliés par une arête sont dits
adjacents.
■ L’ordre d’un graphe est le nombre de ses sommets.
■ Une boucle est une arête ne possédante qu'un seul
élément.
■ Un graphe ne comportant pas de boucles est un
graphe simple.
 Exemple: soit G le graphe suivant

■ Les sommets D et C sont adjacents car le graphe G

comporte l'arête {C,D}.
■ L'ordre du graphe G est égal à 5.
■ Le graphe G n'est pas un graphe simple car il comporte une
boucle, l'arête {B}.
 Graphes orientés

■ Ce qui va différer avec les graphes orientés est que l'on va

imposer une direction sur les liaisons entre sommets.

Définition :
Un graphe orienté G=(V,E) est la donnée :
1- D’un ensemble V dont les éléments sont appelés
les sommets du graphe.
2- D’un ensemble E dont les éléments sont des
couples d'éléments de V, et sont appelés les arcs
du graphe.
 Exemple : Un graphe orienté
■ Pour définir un graphe orienté, il faut donc commencer par
décrire l'ensemble de ses sommets :
V={A,B,C,D,E}
■ On peut alors donner l'ensemble de ses arcs :
E={(A,A),(A,B),(B,D),(C,B),(C,D),(D,C),(E,A)}
Remarque:
✓ l'ordre des éléments importe dans un couple.
Ainsi (A,B)≠(B,A).
✓ On définit ainsi une orientation dans le graphe,
puisque les arcs possèdent un sens de parcours.
Représentation graphique permettra une meilleure
appréhension.
• On définit les notions de boucle, de graphe simple et
d’ordre comme dans le cas des graphes non orientés.
• Par contre la notion de sommets adjacents n'a plus
lieu d'être, il faut la substituer par un concept prenant
en compte l'orientation.

Définition:
En présence d'un arc de la forme (x,y)
- On dit que y est un successeur de x et que x est un
prédécesseur de y.
- On dit également que x est l’origine de l’arc (x,y) et
que y est son extrémité.
 Soit G le graphe orienté suivant :

■ Le graphe G possède l'arc (B,D) donc B est un

prédécesseur de D et D un successeur de B.
■ Le sommet E est l'origine de l'arc (E,A) et A son
extrémité.
■ L'ordre du graphe G est égal à 5.
■ Le graphe G n'est pas un graphe simple car il comporte
une boucle, l'arc (A,A).
 Graphes complets
■ Dans un graphe complet tous les sommets sont reliés entre
eux.
Définition
✓ Un graphe non orienté est complet s’il est simple et
si deux sommets quelconques sont reliés par une
arête.
✓ Un graphe orienté est complet s’il est simple et si
pour toute paire de sommets {x,y}, il existe au moins
un des deux arcs (x,y) ou (y,x).

■ La notion de graphe complet ne fait donc pas intervenir

l’éventuelle orientation du graphe, même si usuellement elle
est utilisée pour des graphes non orientés.
Graphe complet orienté et non orienté
Multigraphes
sous-parties d'un graphe existant
Définitions
Soit G=(V,E) un graphe orienté ou non.
✓ Un graphe G′=(V′,E′) est un sous-graphe de G si
V′⊆V et E′⊆E.
✓ Un sous-graphe recouvrant de G est un sous-
graphe de la forme G′=(V,E′), i.e. un sous-graphe
de G possédant tous les sommets de G.
✓ Un sous-graphe induit de G est un sous graphe
G′=(V′,E′) dont les arêtes ou arcs sont toutes celles
de G ayant leurs extrémités dans V′.
 Soit G le graphe suivant

un sous-graphe de G, constitué donc de certains

sommets et arcs de G
sous-graphe, suivant, de G ne comporte que trois
sommets B,C,D. Il est induit, car il contient tous les arcs
de G ayant B,C ou D pour extrémités :

Le sous-graphe, ci-dessous, de G est recouvrant car il

possède tous les sommets de G
 Graphes planaires

Définition :
Soit G un graphe orienté ou non.
On dira que G est planaire s’il admet une
représentation sagittale où ses arêtes (ou arcs) ne se
coupent pas.
Remarque :
■ « ne se coupent pas » on sous-entend bien sûr en
dehors des sommets
■ On n’étudiera pas de façon exhaustive les graphes
planaires dans ce cours. C’est une question assez
difficile. On se contentera donc principalement
d'exemples.
Ce graphe est planaire
Un petit casse-tête très célèbre, proposé par l'américain Henry
Dudeney en 1917 dans son livre Amusements in mathematics.
■ La question peut alors se reformuler comme suit
: le graphe précédent est-il planaire ?
■ Non

■ Dans le même genre d'idées, se demander si

un graphe est planaire ou non est un problème
intéressant lors de la conception de circuits
imprimés.
Le graphe suivant est-il planaire ?

non
 Autres représentations
■ La seule représentation d'un graphe que nous
connaissons pour le moment est sa
représentation sagittale.
■ Elle est certes intéressante pour l'humain mais
bien sûr inexploitable par un ordinateur.
■ L'enjeu de cette seconde partie va donc être de
proposer des modélisations utilisables lors du
développement d'algorithmes.
 Listes d’adjacence
■ Définition
Considérons un graphe orienté ou non.
■ On peut le représenter par ses listes
d'adjacences.
■ Il s'agit pour chacun des sommets du graphe
de donner la liste de ses sommets adjacents
(cas non orienté) ou la liste de ses sommets
successeurs (cas orienté).
Listes d’adjacences d’un graphe non orienté

Sa représentation par listes

d'adjacences

A:[B]
B:[A,B,C,D]
C:[B,D,E]
D:[B,C]
E:[C]
Listes d’adjacences d’un graphe orienté

sa représentation par listes d'adjacences

A:[A,B]
B:[D]
C:[B,D]
D:[C]
E:[A]
 Matrice d’adjacence

■ Considérons un graphe orienté ou non d’ordre

n dont on a numéroté les n sommets.

■ On peut le représenter par sa matrice

d’adjacence, qui est une matrice carrée
d'ordre n , i.e. une matrice comportant n lignes
et n colonnes.
 Matrice d’adjacence
■ Cas non orienté
■ le coefficient de cette matrice situé à
l'intersection de la i -ème ligne et de la j-ème
colonne vaut

{0
1
, =
𝑠
𝑖
𝑛
𝑜
𝑛
𝑖
𝑗
𝑎
𝑠
𝑖
𝑙
𝑒
𝑠
𝑖
𝑒
𝑚
𝑒
𝑒
𝑡
𝑗
𝑒
𝑚
𝑒
𝑠
𝑜
𝑚
𝑚
𝑒
𝑡
𝑠
𝑠
𝑜
 Matrice d’adjacence d’un graphe non orienté

Sa matrice adjacence

01000
11110
= 01011
01100
00100
𝐴
■ Ici les sommets ne sont pas numérotés mais
classés par ordre alphabétique, ce qui est la
même chose.
■ Par exemple, la valeur 1, située à l’intersection
de la quatrième ligne et de la troisième colonne
signifie que les sommets D et C sont adjacents.

■ On remarquera que la matrice d’adjacence d’un

graphe non orienté est nécessairement
symétrique.
 Matrice d’adjacence
■ Cas orienté
■ le coefficient de cette matrice situé à l'intersection
de la i -ème ligne et de la j-ème colonne vaut

1 ′ ′
, = ′ é
0
𝑠
𝑖
𝑛
𝑜
𝑛
𝑖
𝑗
𝑒
𝑡
𝑙
𝑒
𝑗
𝑖
𝑒
𝑚
𝑒
𝑠
𝑜
𝑚
𝑚
𝑒
𝑡
𝑒
𝑠
𝑡
𝑙
𝑒

𝑥
𝑡
𝑟
𝑒
𝑚
𝑖
𝑡
𝑎
𝑠
𝑖

𝑙
𝑒
𝑥
𝑖
𝑠
𝑡
𝑒
𝑢
𝑛
𝑎
𝑟
𝑐
𝑑
𝑜
𝑛
𝑡
𝑙
𝑒
𝑖
𝑒
𝑚
𝑒
𝑠
𝑜
𝑚
𝑚
𝑒
𝑡
 Matrice d’adjacence d’un graphe orienté

sa matrice d'adjacence

11000
00010
= 01010
00100
10000
𝐴
■ Là encore les sommets sont classés par
ordre alphabétique.
■ Par exemple la valeur 1, située à
l’intersection de la cinquième ligne et de la
première colonne signifie qu'il existe un arc
d'origine E et d'extrémité A.
■ Dans le cas d'un graphe orienté, la matrice
d'adjacence n'a bien sûr plus de raison
d'être symétrique.
 Matrice d’incidence

■ Définition
■ Considérons un graphe non orienté (resp. orienté) d’ordre n
possédant m arêtes (resp. arcs), dont on a numéroté les n sommets
et les m arêtes (resp. arcs).
■ On peut le représenter par sa matrice d’incidence, qui est une
matrice comportant n lignes et m colonnes.
■ Dans le cas non orienté, le coefficient de cette matrice situé à
l'intersection de la i-ème ligne et de la j-ème colonne vaut

{0
1 é ê
, =
𝑠
𝑖
𝑛
𝑜
𝑛
𝑖
𝑗
𝑎
𝑠
𝑖
𝑙
𝑒
𝑖
𝑒
𝑚
𝑒
𝑠
𝑜
𝑚
𝑚
𝑒
𝑡
𝑒
𝑠
𝑡
𝑢
𝑛
𝑒
𝑒
𝑥
𝑡
𝑟
𝑒
𝑚
𝑖
𝑡
𝑑
𝑒
𝑙
𝑎
𝑗
𝑒
𝑚
𝑒
𝑎
𝑟
𝑡
𝑒
 Remarques
■ Dans une matrice d'incidence, le rôle des
lignes et des colonnes n’est donc pas similaire,
une ligne y représente un sommet et une
colonne une arête ou arc.
■ Cette définition s'applique tout à fait aux
multigraphes.
 Matrice d’incidence d’un graphe non orienté

sa matrice d'incidence

100000
111100
= 000111
001010
000001
𝑀
■ les sommets ne sont pas numérotés mais
classés par ordre alphabétique, ce qui est la
même chose.
■ Par exemple, la valeur 1, située à
l’intersection de la quatrième ligne et de la
cinquième colonne signifie que le sommet D
est une des extrémités de la cinquième arête,
notée e5.
 Matrice d’incidence
■ Définition
■ Considérons un graphe non orienté (resp. orienté) d’ordre n
possédant m arêtes (resp. arcs), dont on a numéroté les n
sommets et les m arêtes (resp. arcs).
■ On peut le représenter par sa matrice d’incidence, qui est
une matrice comportant n lignes et m colonnes.
■ Dans le cas orienté, le coefficient de cette matrice situé à
l'intersection de la i -ème ligne et de la j-ème colonne vaut

1 ′
,= −1 ′ é
0
𝑠
𝑖
𝑛
𝑜
𝑛
𝑖
𝑗
𝑠
𝑖
𝑙
𝑒
𝑖
𝑒
𝑚
𝑒
𝑠
𝑜
𝑚
𝑚
𝑒
𝑡
𝑒
𝑠
𝑡
𝑙
𝑒
𝑥
𝑡
𝑟
𝑒
𝑚
𝑖
𝑡
𝑑
𝑢
𝑗
𝑒
𝑚
𝑒
𝑎
𝑟
𝑐
𝑎
𝑠
𝑖
𝑙
𝑒
𝑖
𝑒
𝑚
𝑒
𝑠
𝑜
𝑚
𝑚
𝑒
𝑡
𝑒
𝑠
𝑡
𝑙
𝑜
𝑟
𝑖
𝑔
𝑖
𝑛
𝑒
𝑑
𝑢
𝑗
𝑒
𝑚
𝑒
𝑎
𝑟
𝑐
 Matrice d’incidence d’un graphe orienté

sa matrice d'incidence

1 0 0 0 0 −1
−1 1 −1 0 0 0
= 0 0 1 1 −1 0
0 −1 0 −1 1 0
0 0 0 0 0 1
𝑀
■ encore les sommets sont classés par ordre
alphabétique.
■ Par exemple, la valeur 1, située à
l’intersection de la cinquième ligne et de la
sixième colonne signifie que le sommet E
est l'origine du sixième arc, noté e6.
On ne pourra par contre pas représenter par une
matrice d'incidence un graphe orienté possédant une
boucle

En effet, le sommet A est ici origine et extrémité de l'arc e7, on devrait donc
affecter au coefficient situé sur la première ligne et la septième colonne à la
fois les valeurs 1 et −1, ce qui est bien sûr impossible
 Degré d'un sommet

■ Cas des graphes non orientés

■ Définition
■ Soit G=(V,E) un graphe non orienté et
x∈V l'un de ses sommets.
■ On appelle degré de x, noté d(x), le
nombre d’arêtes ayant x pour extrémité,
une boucle étant comptée deux fois.
Calculs de degrés dans un graphe non orienté

d(A)=1, d(B)=5, d(C)=3, d(D)=2, d(E)=1

 ■ On retrouve également très facilement les valeurs de ces
degrés grâce à la matrice d'adjacence du graphe

01000
11110
= 01011
01100
00100
■ Pour calculer le degré du i-ème sommet, il suffit de faire la
somme des coefficients de la i-ème ligne (ou i-ème colonne
puisque la matrice est symétrique), en doublant les
𝐴
coefficients diagonaux puisqu'ils correspondent aux boucles.
 Cas des graphes orientés
■ Définition
■ Soit G=(V,E) un graphe orienté et x∈V l'un de ses
sommets.
■ On appelle degré sortant de x, noté +( )
■ le nombre d’arcs ayant x pour origine.
■ On appelle degré entrant de x, noté −( ), le
nombre d’arcs ayant x pour extrémité.
■ On appelle degré de x, noté ( ), le nombre d’arcs
ayant x pour origine ou extrémité. On a naturellement
+ −
( )= ( )+ ( )
𝑑
𝑑
𝑑
𝑑
𝑥
𝑥
𝑥
𝑥
𝑑
𝑥
𝑑
𝑥
 Calculs de degrés dans un graphe orienté

+
(A)=2, +(B)=1, +(C)=2, +(D)=1, +(E)=1
−
(A)=2, −(B)=2, −(C)=1, −(D)=2, −(E)=0
On retrouve très facilement les valeurs de ces degrés grâce à la matrice d'adjacence
du graphe
11000 Pour calculer le degré sortant (resp. entrant)
00010 du i-ème sommet, il suffit de faire la somme
= 01010 des coefficients de la i-ème ligne (resp. i-ème
00100 colonne).
10000
𝐴
𝑑
𝑑
𝑑
𝑑
𝑑
𝑑
𝑑
𝑑
𝑑
𝑑
 Lemme des poignées de main
■ Les résultats suivants sont assez intuitifs, ils relient le
nombre d'arêtes ou arcs d'un graphe avec les degrés de
ses sommets. Là aussi, distinguons les cas.
■ Cas des graphes non orientés
■ Propriété
Soit G=(V,E) un graphe non orienté.

∑
On a ( )=2∗
∈
La notation désigne le cardinal de , c’est-à-dire son nombre
d’éléments.
■ Autrement dit, la somme des degrés des sommets
est égale au double du nombre d’arêtes.
𝑥
𝑉
𝑑
𝑥
𝐸
𝐸
𝐸
 Cas des graphes orientés
■Propriété
Soit G=(V,E) un graphe orienté.
+ −
∑ ∑
On a ( )= ( )=
∈ ∈
■ Cela signifie que le nombre d’arcs est à la fois
égal à la somme des degrés entrants des
sommets et à la somme des degrés sortants.
■ A noter que dans le cas des graphes orientés,
on a toujours l’égalité
∑
( )=2∗
∈
𝑥
𝑉
𝑥
𝑉
Applications : voir TD
𝑥
𝑉
𝑑
𝑥
𝑑
𝑥
𝐸
𝑑
𝑥
𝐸
 Chaînes - Cycles
■ Les notions de chaînes et cycles ne tiennent pas compte de
l'orientation des graphes
■ Définitions
Soit G=(V,E) un graphe non orienté.
■ Une chaîne de G est une suite ( 0, 1, …, ) de sommets de
G, où deux sommets consécutifs quelconques sont adjacents.
Autrement dit : ∀ , 0 ≤ ≤ − 1 , ( , +1) ∈
■ Les sommets 0 et sont respectivement l’origine et
l’extrémité de la chaîne.
■ On appelle longueur de la chaîne le nombre d’arêtes la
constituant, c'est-à-dire n dans la description précédente.
■ Un cycle est une chaîne de longueur non nulle dont l’origine et
l’extrémité coïncident.
𝑛
𝑛
𝑖
𝑖
𝑥
𝑥
𝑥
𝑖
𝑥
𝑖
𝑥
𝑛
𝑥
𝑥
𝐸
 Chaînes et cycles dans un graphe non orienté

➢Voici certaines chaînes de ce graphe : (C,D,B,B,A), (D,B,C,E),

(E,C,D,B,C,D,B,A).
➢Elles sont respectivement de longueurs 4, 3 et 7.
➢ Par contre (C,B,D,A) et (B,E) ne sont pas des chaînes.
➢ Voici certains cycles de ce graphe : (C,D,B,B,C), (D,B,A,B,C,E,C,D).
➢ Par contre (D,B,A,D) et (B,C,E,B) ne sont pas des cycles.
 Graphe orienté
■ On peut définir de même les notions de chaîne et cycle dans un graphe
orienté G=(V,E) en « oubliant » son orientation. Une chaîne sera ainsi une
suite de sommets de G, où deux sommets consécutifs sont reliés par un arc,
sans condition de direction sur ce dernier. Un cycle sera comme
précédemment une chaîne ayant une origine et une extrémité confondues.

Les parcours (B,A,E), (A,B,D,C) et (A,B,C,D,B) sont des chaînes,

(B,C,D,B) est un cycle.
 Chemins. Circuits
Les concepts de chemins et circuits vont eux être spécifiques aux graphes
orientés.

■ Définitions
Soit G=(V,E) un graphe orienté.
■ Un chemin de G est une suite ( 0, 1,⋯, ) de sommets de G,
où deux sommets consécutifs quelconques sont reliés par un
arc dirigé du premier vers le second. Autrement dit
∀ , 0≤ ≤ −1, ( , +1) ∈
■ Les sommets 0et sont respectivement l’origine et
l’extrémité du chemin.
■ On appelle longueur du chemin le nombre d’arcs le
constituant, c'est-à-dire n dans la description précédente.
■ Un circuit est un chemin de longueur non nulle dont l’origine et
l’extrémité coïncident.
𝑛
𝑛
𝑖
𝑖
𝑥
𝑥
𝑥
𝑥
𝑥
𝑖
𝑖
𝑛
𝑥
𝑥
𝐸
 Chemins et circuits dans un graphe orienté

■ Voici certains chemins de ce graphe : (A,B,D,C,B), (E,A,A,B),

(D,C,D,C,B).
Ils sont respectivement de longueurs 4, 3 et 4.
■ Par contre (A,B,C,D,B) et (D,C,B,A)ne sont pas des chemins.
■ Voici certains circuits de ce graphe : (B,D,C,B) , (D,C,B,D,C,D).
■ Par contre (B,C,D,B) et (A,B,D,C,B,A) ne sont pas des circuits.
 Parcours élémentaires et simples
Définition
■ Dans un graphe non orienté (resp. orienté), une chaîne
(resp. un chemin) est dite simple si elle ne passe pas deux
fois par la même arête (resp. arc).
■ Dans un graphe non orienté (resp. orienté), une chaîne
(resp. un chemin) est dite élémentaire si elle ne passe pas
deux fois par le même sommet.

✓ Ces définitions à propos des chaînes et chemins s'appliquent bien sûr aux cas
particuliers des cycles et circuits. Le fait que leurs origines et extrémités soient
confondues n'impactera pas par contre leur éventuel caractère élémentaire.

✓ Il est clair qu'une chaîne ou un chemin élémentaire est nécessairement simple.

En effet, si un parcours ne passe pas deux fois par un même sommet il ne pourra
pas passer deux fois par une même arête ou un même arc.
 Exemple : Chaînes simples et élémentaires

■ (E,C,D,B,C) est une chaîne simple, et (C,D,B,B,C)

est un cycle simple.
■ (A,B,D,C,E) est une chaîne élémentaire, et (B,D,C,B)
est un cycle élémentaire.
Exemple: Chemins simples et élémentaires

■ (E,A,B,D,C,B) est un chemin simple, et

(B,D,C,B)est un circuit simple.
■ (E,A,B,D,C) est un chemin élémentaire, et
(D,C,D) est un circuit élémentaire.
 Nombre de chaînes ou de chemins de longueur donnée

■ Le résultat suivant permet de déterminer le nombre de

chaînes ou chemins d'une certaine longueur à l'aide
des puissances de la matrice d'adjacence.
■ Propriété
Soit G=(V,E) un graphe non orienté (resp. orienté) et A
sa matrice d’adjacence. Soit p un entier naturel non nul.
Alors, le coefficient situé à l'intersection de la i-ème ligne
et de la j-ème colonne de est égal au nombre de
chaînes (resp. chemins) de longueur p, ayant pour
origine le i-ème sommet et pour extrémité le j-ème.
■ Ce résultat donne le nombre de chaînes ou chemins
d’une longueur donnée mais pas leur description. En cas
de besoin, il faudra les déterminer « à la main ».
𝐴
𝑝
Nombre de chaînes de longueur donnée

■ Sa matrice d'adjacence est

01000
11110
Ma = 01011
01100
00100
 Nombre de chaînes de longueur donnée

On montre facilement que

11110 14221
14221 49762
2 3
= 12310 et = 27353
12121 26531
01011 12310

■ Il y a ainsi par exemple 4 chaînes de longueur 3 de B vers A :

(B,A,B,A), (B,C,B,A), (B,D,B,A) et (B,B,B,A).
𝑀
𝑎
Il y a également 3 cycles de longueur 3 de D vers D : (D,B,C,D),
𝑀
𝑎
■
(D,C,B,D) et (D,B,B,D).
 Graphes connexes
■ La notion de connexité formalise le fait pour un
graphe d'être d'un seul tenant.
■ Définition
Soit G=(V,E) un graphe orienté ou non.
■ On dit que G est connexe si pour toute paire {x,y}
de sommets de G il existe une chaîne reliant x et
y.
■ Le fait qu’un graphe soit connexe ou non ne
dépend donc pas de son éventuelle orientation.
Des graphes connexes et non connexes
■ Le graphe suivant est connexe :

■ Le graphe suivant n'est pas connexe :

■ En effet, il n'y par exemple pas de chaîne reliant les sommets B et G.

■ Comme on vient de le voir sur cet
exemple, tous les graphes ne sont pas
connexes. Mais ceux qui ne le sont pas
peuvent toujours apparaître comme une
réunion de sous-graphes connexes.

Définition
Soit G=(V,E) un graphe orienté ou non.
On peut décomposer G en sous-graphes induits dont chacun sera connexe.
Ces sous-graphes s’appellent les composantes connexes de G.
 Décomposition en composantes connexes

■ Le graphe suivant n'est pas connexe :

■ Mais on peut le décomposer en trois

composantes connexes : {B,C,D,E}, {I,J,K,H} et
{A,F,G}.
Graphes fortement connexes
La définition suivante ne concerne que les
graphes orientés et est plus contraignante
que celle de connexité.

Définition
■ Soit G=(V,E) un graphe orienté.
■ On dit que G est fortement connexe si
pour tout couple (x,y) de sommets de G il
existe un chemin d'origine x et d'extrémité
y.
 Des graphes fortement connexes ou non

■ Le graphe suivant n'est pas fortement connexe :

En effet, il n'y a par exemple pas de chemin d'origine

B et d'extrémité E.
■ Le graphe suivant est par contre fortement
connexe :
Graphes Eulériens et
Hamiltoniens

Pr. Lekbir Afraites

2022-2023
 Plan

✓ Graphes eulériens
✓ Graphes hamiltoniens
■ Dans ce chapitre, nous allons tout d'abord effectuer
des parcours dans un graphe en imposant
des contraintes
■ Cela nous conduira à l'étude des
graphes eulériens et hamiltoniens
■ Toutes ces thématiques ont pour point commun de
reposer sur des propriétés des degrés des
sommets du graphe.
 Graphes Eulériens

04/03/2024 70
 Graphes non orientés
■ Un peu d'histoire sur le problème fondateur de la théorie
des graphes
■ Sept ponts de Konisgberg
Graphes non orientés

■ Q : peut-on effectuer un parcours dans la ville de

Königsberg en empruntant ces sept ponts une et une seule
fois ?
 Graphes non orientés
■ Le mathématicien Lucas Edouard a illustré le problème
précèdent sous :
 Graphes non orientés
■ Ce problème est modélisé par un graphe non
orienté dont les sommets A,B,C et D sont les rives
■ Et les arêtes sont les sept ponts.
 Graphes non orientés

■ Reformulons la question : peut-on trouver

une chaîne passant une et une seule fois par
toutes les arêtes de ce graphe ?
 Graphes non orientés
■ Nous allons d'abord généraliser à n'importe quel
graphe non orienté.

■ Définitions
■ Soit G=(V,E) un graphe non orienté.
■ Une chaîne eulérienne de G est une chaîne simple
passant par toutes les arêtes de G, c’est-à-dire une chaîne
passant une et une seule fois par toutes les arêtes de G.
■ Un cycle eulérien est une chaîne eulérienne ayant les
mêmes extrémités.
■ Un graphe eulérien est un graphe possédant un cycle
eulérien.
 Graphes non orientés
■ Remarques :
- Condition nécessaire pour qu’un graphe admette une
chaîne ou un cycle eulérien est bien sûr qu’il
soit connexe
- Condition nécessaire pour qu’un graphe admette un
cycle eulérien est que chacun de ses sommets ait un
degré pair. En effet, pour constituer un tel cycle on doit
pouvoir repartir de chaque sommet autant de fois que l'on
y arrive, et ce sans emprunter deux fois la même arête :
 Graphes non orientés
■ Théorème
Soit G=(V,E) un graphe non orienté connexe.
- Le graphe G admet un cycle eulérien si et
seulement si tous ses sommets ont un degré pair.
- Le graphe G admet une chaîne eulérienne qui
n’est pas un cycle si et seulement si tous ses
sommets ont un degré pair sauf exactement deux
d’entre eux. Ces deux sommets particuliers seront
les extrémités de cette chaîne.
 Graphes non orientés
■ Résoudre : Problème des sept ponts de Königsberg

Les 4sommets de ce graphe ont des degrés impairs, il n’existe donc ni cycle eulérien,
ni chaîne eulérienne. Le problème des ponts de Königsberg n’a donc pas de solution.
 Graphes non orientés
Problème du dessin d'enveloppe
■ Question : peut-on dessiner une enveloppe ouverte (resp. fermée)
sans lever le crayon et sans repasser sur une ligne déjà dessinée ?
Cela revient à se demander si l'on peut trouver une chaîne
eulérienne dans les graphes suivants :

Dans le premier cas la réponse est non car tous les sommets ont un degré impair.
Dans le second cas, deux sommets exactement ont un degré impair,
il existe donc une chaîne eulérienne ayant ces deux sommets pour extrémités.
Nous laissons le lecteur la déterminer "à la main".
 Graphes non orientés
Algorithme de détermination Cy.E.
■ Soit G=(V,E) un graphe non orienté connexe possédant un cycle eulérien.
1. Choisir un sommet arbitrairement.
2. Construire un cycle simple (quel qu’il soit) ayant pour origine et extrémité ce
sommet (c’est toujours possible).
3. Si ce cycle est eulérien, la recherche est terminée.
4. Sinon, considérer le sous-graphe de G obtenu en supprimant les arêtes du cycle
précédent.
5. À partir d’un sommet commun au sous-graphe restant et au cycle, construire de
nouveau un cycle simple.
6. Insérer ce second cycle dans le premier.
7. Recommencer à partir de l'étape 3.

■ Remarque : cet algorithme fini tjs par trouver un C. E. mais pas d’unicité
Exemple : détermination d'un cycle eulérien
■ Considérons le graphe non orienté dont la représentation sagittale est la
suivante :

■ Ce graphe est eulérien car il est connexe, et tous les degrés de ses
sommets sont pairs.

04/03/2024 82
 Suite
■ On commence donc par choisir un sommet, par exemple A. On construit
alors un cycle simple d'origine et extrémité A, comme (A,D,E,F,A),
représenté en rouge ici :

On considère ensuite le sous-graphe de G obtenu en supprimant ce cycle :

04/03/2024 83
 Suite
■ A partir du sommet D, on peut construire un second cycle simple, par
exemple (D,C,B,D), ici en vert :

■ On supprime ce nouveau cycle :

04/03/2024 84
 Suite
■ La construction du prochain (et dernier) cycle simple est triviale, il s'agit de
(E,A,B,E), mis en évidence en mauve :

■ Il ne reste plus qu’à insérer les deux derniers cycles dans le premier, il vient
(A,D,C,B,D,E,A,B,E,F,A) :

04/03/2024 85
 Graphes non orientés
Algorithme de détermination Ch.E.
■ Soit G=(V,E) un graphe non orienté connexe possédant une chaîne eulérienne.
1. Choisir arbitrairement l'un des deux sommets de degré impair.
2. Construire une chaîne simple (quelle qu’elle soit) ayant pour origine ce sommet et pour
extrémité l’autre sommet de degré impair (c’est toujours possible).
3. Si cette chaîne est eulérienne, la recherche est terminée.
4. Sinon, considérer le sous-graphe de G obtenu en supprimant les arêtes de la chaîne
précédente.
5. À partir d’un sommet commun au sous-graphe restant et à la chaîne, construire un cycle
simple.
6. Insérer ce cycle dans la chaîne.
7. Recommencer à partir de l'étape 3.

■ Remarque : cet algorithme fini tjs par trouver un C. E. mais pas d’unicité
 Exemple : détermination d'un chaîne eulérienne

■ Ce graphe possède une chaîne eulérienne car il est connexe, et ses sommets ont un degré pair
sauf exactement deux d'entre eux, A et D.
■ On commence donc par choisir l'un de ces deux sommets, par exemple D. On construit alors une
chaîne simple d'origine D et d'extrémité A, comme (D,C,B,D,F,A), représentée en rouge ici :

04/03/2024 87
 Suite
■ On considère ensuite le sous-graphe de G obtenu en supprimant cette
chaîne :

■ La construction du (seul) cycle simple est triviale, il s'agit de (B,E,A,B), ici

en vert :

04/03/2024 88
 Suite
■ Il ne reste plus qu’à insérer ce dernier cycle dans la chaîne, il vient
(D,C,B,E,A,B,D,F,A) :

04/03/2024 89
 Cas des graphes orientés

■ Définitions
■ Soit G=(V,E) un graphe orienté.
■ Un chemin eulérien de G est un chemin simple passant par tous les arcs de G,
c’est-à-dire un chemin passant une et une seule fois par tous les arcs de G.
■ Un circuit eulérien est un chemin eulérien ayant les mêmes extrémités.
■ Un graphe eulérien est un graphe possédant un circuit eulérien.

Sans surprise, les conditions pour qu'un graphe orienté soit eulérien vont porter sur
la connexité et les valeurs des degrés des sommets. Mais cette fois-ci la parité des
degrés ne sera pas suffisante. En effet, pour que l'on puisse repartir d'un sommet autant
de fois que l'on y arrive sans emprunter deux fois le même arc, il va falloir que son degré
entrant soit égal à son degré sortant :

90
04/03/2024
Graphes orientés
Définitions
Soit G=(V,E) un graphe orienté.
Un chemin eulérien de G est un chemin simple passant
par tous les arcs de G, c’est-à-dire un chemin passant
une et une seule fois par tous les arcs de G.
Un circuit eulérien est un chemin eulérien ayant les
mêmes extrémités.
Un graphe eulérien est un graphe possédant un circuit
eulérien.
■ Remarque : les conditions pour qu'un graphe orienté soit
eulérien vont porter sur la connexité et les valeurs
des degrés des sommets.
il va falloir que son degré entrant soit égal à son degré sortant
 Graphes orientés
Théorème
Soit G=(V,E) un graphe orienté connexe.
Le graphe G admet un circuit eulérien si et seulement si tous ses
sommets ont un degré entrant égal à leur degré sortant.
Le graphe G admet une chemin eulérien qui n’est pas un circuit si et
seulement si tous ses sommets ont un degré entrant égal à leur
degré sortant, sauf deux d’entre eux et qui vérifieront
+( )= −()−1
+( ) = −( ) + 1
Ce chemin aura pour origine et pour extrémité .
𝑦
𝑥
𝑦𝑥
𝑑
𝑦
𝑑
𝑦
𝑑
𝑥
𝑑
𝑥
 Exemple : Un graphe eulérien
■ Considérons le graphe orienté dont la représentation sagittale est la suivante :

■ Ce graphe est eulérien car il est connexe, et tous ses sommets ont un degré
entrant égal à leur degré sortant.

04/03/2024 93
 Un graphe possédant un chemin eulérien

■ Ce graphe est eulérien car il est connexe, et tous ses sommets ont un degré
entrant égal à leur degré sortant à part les sommets E et F qui vérifient les
conditions du théorème. Il existe donc un chemin eulérien d'origine E et
d'extrémité F.

04/03/2024 94
 Graphes orientés

■ Les méthodes pour déterminer un chemin ou un

circuit eulérien sont exactement les mêmes que
dans le cas non orienté, en tenant bien sûr
compte de l’orientation.
■ Il faut juste bien penser que dans la recherche
d’un chemin eulérien, l’origine du chemin doit être
le sommet dont le degré sortant est supérieur au
degré entrant.
 Exemple : Détermination d'un cycle eulérien

■ Nous avions établi qu'il existe un chemin eulérien d'origine E et d'extrémité F.

■ Pour en déterminer un, on commence par construire un chemin simple
d'origine E et d'extrémité F, comme (E,B,A,F), représenté en rouge ici :

04/03/2024 96
 Suite
■ On considère ensuite le sous-graphe de G obtenu en supprimant ce chemin :

■ La construction du (seul) circuit simple est triviale, il s'agit de (B,E,D,C,B), ici en

vert :

04/03/2024 97
 Suite

■ Il ne reste plus qu’à insérer ce dernier circuit dans le chemin, il vient

(E,B,E,D,C,B,A,F) :

04/03/2024 98
 Graphes hamiltoniens

04/03/2024 99
■ Nous allons cette fois-ci imposer une contrainte à nos
parcours relative aux sommets d'un graphe.
■ Un peu d’Histoire : question formulée en 1859 par Sir William
Rowan Hamilton
■ On considère 20 villes du globe terrestre positionnées sur les
sommets d’un dodécaèdre régulier

■ La question est la suivante : peut-on effectuer un parcours en

passant une et une seule fois par chacune de ces villes et en
revenant à son point de départ ?
■ On peut associer un graphe planaire, dont les sommets et les
arêtes correspondent à ceux du dodécaèdre

■ Ce graphe est construit à partir de ce que l'on appelle

le diagramme de Schlegel du dodécaèdre
■ Reformulons notre question : peut-on trouver un cycle
passant une et une seule fois par tous les sommets de ce
graphe ?

■ Un tel parcours sera qualifié d'hamiltonien.

Cas général
Définitions
Soit G=(V,E) un graphe orienté ou non.
Une chaîne, un chemin, un cycle ou un circuit de G sont
dits hamiltoniens s’ils passent une et une seule fois par
tous les sommets de G.
Un graphe hamiltonien est un graphe non orienté
possédant un cycle hamiltonien ou un graphe orienté
possédant un circuit hamiltonien.

■ la recherche de parcours eulérien est un problème relativement

facile
■ la recherche de parcours hamiltonien est extrêmement difficile.
■ Pour l’instant, on ne connaît d’ailleurs pas de conditions générales
permettant d’affirmer qu’un graphe est hamiltonien.
Exemple : Un graphe non orienté hamiltonien

■ Ce graphe est hamiltonien car il possède le cycle (A,E,B,C,D,F,A).

04/03/2024 104
 Un graphe orienté hamiltonien

■ Ce graphe est hamiltonien car il possède le cycle

(E,D,C,B,A,F,E).

04/03/2024 105
 Conditions suffisantes d'existence
■ Si l'on ne connait pas encore de conditions nécessaires pour
affirmer qu'un graphe est hamiltonien ou non, il existe
quelques conditions suffisantes.
■ La condition suivante est ainsi assez grossière.

Propriété
Soit G=(V,E) un graphe non orienté.
Si G possède un sommet de degré 1 il ne peut pas être
hamiltonien.

Ce résultat est assez évident, car pour qu'un graphe possède un cycle hamiltonien
on doit pouvoir arriver et repartir par n’importe quel sommet, et donc le degré de chacun
d'eux doit être au moins égal à 2.
Exemple : Un graphe non hamiltonien

■ Ce graphe n'est pas hamiltonien car le sommet F est de degré 1.

04/03/2024 107
 Conditions suffisantes d'existence
■ La condition suivante est du au mathématicien Dirac .
Condition de Dirac
Soit G=(V,E) un graphe non orienté d'ordre n,
avec ≥ 3 .
Si pour tout sommet x de G on a ( )≥
2
alors G est hamiltonien.
■ Cette condition suffisante mais absolument pas nécessaire
est en pratique peu vérifiée.
𝑑
𝑥
𝑛
𝑛
Exemple : Application de la condition de Dirac

■ Ce graphe est d’ordre 5 et chacun de ses sommet a un degré au moins

égal à 3. Il est donc hamiltonien.
■ Voici un exemple de cycle hamiltonien : (A,B,C,E,D,A)

04/03/2024 109
 Conditions suffisantes d'existence
■ La condition précédente va permettre de prouver que les
graphes complets sont hamiltoniens.

Propriété
Soit G=(V,E) un graphe non orienté d'ordre n,
avec n≥3.
Si le graphe G est complet alors il est hamiltonien.

Preuve
Le degré de chaque sommet est égal à n−1 donc
la condition de Dirac est vérifiée.
 Un graphe complet hamiltonien

■ Nous espérons que le lecteur saura trouver de lui-même un cycle

hamiltonien dans ce graphe...

04/03/2024 111
 Applications

04/03/2024 112
 Organisation de dîners
■ Cinq amis dînant autour d’une table ronde se demandent
combien de dîners pourront-ils organiser afin que personne
n’ait deux fois le même voisin.
■ Modélisons ce problème par un graphe complet à cinq
sommets :
■ Un plan de table va correspondre à un cycle hamiltonien de ce graphe. En
effet, positionner les convives autour de la table en ne se souciant que de
l'identité de chacun des voisins revient à énumérer les différentes personnes.

■ Deux cycles hamiltoniens ayant une arête commune correspondront à des

plans de table où deux amis se retrouveront deux fois côte à côte.

■ La question se ramène donc à dénombrer le nombre de cycles

hamiltoniens disjoints, c’est-à-dire n’ayant aucune arête commune.

■ Ce graphe comportant 10 arêtes, et un cycle hamiltonien en possédant 5, il y

aura au plus deux cycles hamiltoniens disjoints. Et il y en a exactement deux :
(A,B,C,D,E,A) et (A,C,E,B,D,A).

■ Ces amis pourront donc organiser deux dîners avec cette contrainte.

04/03/2024 114