Cours Théorie des Graphes

Dr BADJO KIMBA Abdoul Wahid

2025-2026
Table des matières

1 Introduction à la théorie des graphes 4

1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.1.1 Dénition d'un graphe . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.1.2 Sommets d'un graphe . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.1.3 Arêtes d'un graphe . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.1.4 Degré d'un sommet . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.1.5 Exemple complet de graphe . . . . . . . . . . . . . . . . . . . . . . 7
1.2 Types de graphes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.2.1 Graphe non orienté . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.2.2 Graphe orienté . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.2.3 Cycles dans un graphe . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.2.4 Boucles dans un graphe . . . . . . . . . . . . . . . . . . . . . . . . 9
1.2.5 Graphes simples et multigraphes . . . . . . . . . . . . . . . . . . . . 10
1.2.6 Chemins et chaînes dans un graphe . . . . . . . . . . . . . . . . . . 11
1.2.7 Connexité d'un graphe . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.2.8 Distance dans un graphe . . . . . . . . . . . . . . . . . . . . . . . . 13
1.2.9 Arbres et forêts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.2.10 Comparaison : graphe orienté / non orienté . . . . . . . . . . . . . . 14
1.2.11 Graphe non pondéré . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.2.12 Graphe pondéré . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.2.13 Graphe simple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.2.14 Multigraphe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.3 Représentation des graphes . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.3.1 Listes d'adjacence . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.3.2 Matrice d'adjacence . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.3.3 Matrice d'adjacence d'un graphe pondéré . . . . . . . . . . . . . . . 18
1.3.4 Exemple de graphe pondéré avec valeurs innies dans la matrice . . 19
1.3.5 Piles et les . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
1.3.6 Représentation graphique : pile vs le . . . . . . . . . . . . . . . . . 21
1.4 Parcours de graphe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
1.4.1 Parcours en largeur (BFS) . . . . . . . . . . . . . . . . . . . . . . . 22
1.4.2 Parcours en profondeur (DFS) . . . . . . . . . . . . . . . . . . . . . 23
1.5 Plus courts chemins . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
1.5.1 Dénition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
1.5.2 Algorithme de Dijkstra . . . . . . . . . . . . . . . . . . . . . . . . . 24
1.5.3 Algorithme de Dijkstra . . . . . . . . . . . . . . . . . . . . . . . . . 25
1.5.4 Pseudo-code de l'algorithme de Dijkstra . . . . . . . . . . . . . . . 26
1.5.5 Graphe hamiltonien . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

1
 1.5.6 Graphe eulérien . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
1.6 Graphes bipartis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
1.6.1 Dénition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
1.6.2 Exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
1.6.3 Graphe biparti complet . . . . . . . . . . . . . . . . . . . . . . . . . 35
1.6.4 Propriété fondamentale . . . . . . . . . . . . . . . . . . . . . . . . . 35
1.6.5 Coloration des graphes bipartis . . . . . . . . . . . . . . . . . . . . 35
1.6.6 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
1.6.7 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
1.7 Théorie de la coloration . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
1.7.1 Dénition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
1.7.2 Nombre chromatique . . . . . . . . . . . . . . . . . . . . . . . . . . 36
1.7.3 Exemple : graphe chemin . . . . . . . . . . . . . . . . . . . . . . . . 36
1.7.4 Exemple : graphe complet . . . . . . . . . . . . . . . . . . . . . . . 37
1.7.5 Théorème des quatre couleurs . . . . . . . . . . . . . . . . . . . . . 37
1.7.6 Coloration des arêtes . . . . . . . . . . . . . . . . . . . . . . . . . . 37
1.7.7 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
1.7.8 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
1.8 Matrices associées aux graphes . . . . . . . . . . . . . . . . . . . . . . . . . 38
1.8.1 Matrice d'incidence . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
1.8.2 Exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
1.8.3 Matrice des distances . . . . . . . . . . . . . . . . . . . . . . . . . . 39
1.8.4 Exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
1.8.5 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
1.8.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
1.9 Arbres . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
1.9.1 Propriétés des arbres . . . . . . . . . . . . . . . . . . . . . . . . . . 40
1.9.2 Exemple d'arbre . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
1.9.3 Caractérisation des arbres . . . . . . . . . . . . . . . . . . . . . . . 40
1.10 Arbres couvrants minimaux . . . . . . . . . . . . . . . . . . . . . . . . . . 40
1.10.1 Dénition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
1.11 Algorithme de Kruskal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
1.11.1 Principe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
1.11.2 Étapes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
1.11.3 Pseudo-code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
1.12 Algorithme de Prim . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
1.12.1 Principe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
1.12.2 Étapes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
1.12.3 Pseudo-code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
1.13 Comparaison . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
1.13.1 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
1.14 Exemple de Kruskal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
1.14.1 Étapes de l'algorithme de Kruskal . . . . . . . . . . . . . . . . . . . 42
1.14.2 Arbre couvrant minimal . . . . . . . . . . . . . . . . . . . . . . . . 43
1.15 Algorithme de Prim . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
1.15.1 Principe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
1.15.2 Application au même graphe . . . . . . . . . . . . . . . . . . . . . . 43
1.15.3 Arbre couvrant minimal . . . . . . . . . . . . . . . . . . . . . . . . 43

2
1.16 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
1.17 Tri topologique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
1.17.1 Dénition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
1.17.2 Algorithme de Kahn . . . . . . . . . . . . . . . . . . . . . . . . . . 44
1.17.3 Exemple : graphe initial . . . . . . . . . . . . . . . . . . . . . . . . 44
1.17.4 Étape 1 : degrés entrants . . . . . . . . . . . . . . . . . . . . . . . . 44
1.17.5 Étape 2 : suppression de A . . . . . . . . . . . . . . . . . . . . . . . 44
1.17.6 Étape 3 : traitement de B et C . . . . . . . . . . . . . . . . . . . . 44
1.17.7 Étape 4 : traitement de D et E . . . . . . . . . . . . . . . . . . . . 45
1.17.8 Résultat . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
1.17.9 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
1.17.10 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

3
Chapitre 1
Introduction à la théorie des graphes

1.1 Introduction

La théorie des graphes est une branche fondamentale des mathématiques discrètes et
sommets (ou n÷uds)
de l'informatique théorique qui étudie les structures constituées de
et d'arêtes (ou liens) dénissant des relations entre ces sommets. Elle fournit un cadre
universel pour modéliser des systèmes complexes dans lesquels la topologie des relations
est primordiale.

Historique
Leonhard Euler
sept ponts de Königsberg
Les graphes apparaissent pour la première fois dans les travaux de
(1735) sur le problème des , marquant l'origine de la combinatoire
problème
moderne et ouvrant la voie à l'étude formelle des structures relationnelles. Le
des quatre couleurs, conjecturé par Francis Guthrie en 1852 et démontré par Appel
et Haken en 1976 à l'aide de méthodes informatiques, illustre l'importance des outils
computationnels dans les preuves mathématiques modernes.

Propriétés structurales
Les graphes se caractérisent par plusieurs propriétés essentielles :

 Orientation des arêtes : un graphe peut être orienté (digraphe) ou non orienté.
 Pondération : les arêtes peuvent porter des valeurs numériques représentant des
coûts, distances ou capacités.

 Connexité et composantes : un graphe peut être connexe ou comporter plusieurs

composantes isolées.

 Cycles et acyclicité : la présence ou l'absence de cycles est cruciale pour l'analyse

algorithmique (ex. arbres, DAG).

 Planarité et représentation géométrique : certains graphes peuvent être des-

sinés sur un plan sans arêtes qui se croisent.

Applications
La théorie des graphes est utilisée dans de nombreux domaines :

4
  Informatique et réseaux : structures de données, analyse de réseaux sociaux,
moteurs de recherche, intelligence articielle.

 Transport et logistique : optimisation des itinéraires, planication de ux et

gestion des infrastructures.

 Sciences physiques et chimiques : modélisation de molécules, interactions bio-

logiques, systèmes de communication.

 Mathématiques appliquées et théorie algorithmique : combinatoire, optimi-

sation, théorie des jeux et analyse de complexité.

Intérêt
La théorie des graphes fournit un langage unié et des outils rigoureux pour représen-
ter, analyser et résoudre des problèmes complexes dans des contextes variés, allant des
sciences fondamentales à l'ingénierie et aux systèmes informatiques distribués.

1.1.1 Dénition d'un graphe

Dénition 1.1.1. Un graphe est une structure mathématique notée G = (V, E), où :
 V est un ensemble ni de sommets (ou n÷uds);
 E est un ensemble d'arêtes (ou liens) reliant les sommets.
Dans le cas général, l'ensemble des arêtes vérie E ⊆ V × V .
Interprétation : Un graphe permet de modéliser des relations entre des entités. Les
sommets représentent les objets (personnes, villes, ordinateurs, etc.), tandis que les arêtes
représentent les interactions ou connexions entre ces objets.

Exemple 1.1.1. Considérons le graphe déni par :

V = {A, B, C, D}, E = {(A, B), (A, C), (B, D), (C, D)}.
Ce graphe comporte quatre sommets et quatre arêtes. Par exemple, les arêtes (A, B) et
(A, C) indiquent que le sommet A est relié respectivement aux sommets B et C .
Remarque 1.1.1.  Si les arêtes sont orientées, on parle de graphe orienté (ou
digraphe).
 Si elles ne le sont pas, on parle de graphe non orienté.
Les graphes sont largement utilisés dans de nombreux domaines tels que les réseaux
sociaux, les réseaux de transport, ou encore les réseaux informatiques.
1.1.2 Sommets d'un graphe
Dans un graphe G = (V, E), l'ensemble V désigne l'ensemble des sommets (ou
n÷uds) :
V = {v1 , v2 , . . . , vn }
Les sommets constituent les éléments fondamentaux du graphe. Chaque sommet re-
présente une entité élémentaire du système étudié.
Interprétation : Selon le contexte, un sommet peut représenter une personne dans
un réseau social, une ville dans un réseau routier, ou encore un ordinateur dans un réseau
informatique.

5
Exemple 1.1.2. Considérons :
V = {A, B, C, D}

Ce graphe possède quatre sommets, notés A, B, C et D.

Remarque 1.1.2.  Les sommets sont généralement représentés graphiquement par
des points.
 Le nombre de sommets d'un graphe est appelé ordre du graphe et est noté |V |.
1.1.3 Arêtes d'un graphe
Dénition 1.1.2. Dans un graphe G = (V, E), l'ensemble E représente l'ensemble des
arêtes (ou liens). Une arête est une paire de sommets appartenant à V , c'est-à-dire :
E ⊆V ×V

Les arêtes modélisent les relations, interactions ou connexions entre les sommets du
graphe.
Interprétation : Une arête peut représenter, par exemple, une route entre deux villes,
une relation d'amitié entre deux personnes, ou une connexion entre deux ordinateurs.

Exemple 1.1.3. Soit un graphe avec :

V = {A, B, C, D}

Un ensemble possible d'arêtes est :

E = {(A, B), (A, C), (B, D), (C, D)}

Cela signie que :

 A est relié à B et C ;
 B est relié à D ;
 C est relié à D.
Remarque 1.1.3.  Une arête reliant un sommet à lui-même est appelée une boucle.
 Si les arêtes sont orientées, on parle de graphe orienté (les arêtes sont alors
appelées arcs).
 Si elles ne le sont pas, on parle de graphe non orienté.
 Une arête peut être pondérée, c'est-à-dire associée à une valeur (distance, coût,
durée, etc.).
1.1.4 Degré d'un sommet
Dénition 1.1.3. Le degré d'un sommet v, noté deg(v), est le nombre d'arêtes incidentes
à ce sommet.
Cas particuliers :
 Dans un graphe non orienté, le degré correspond au nombre total d'arêtes reliées
au sommet.

6
  Une boucle compte pour deux dans le degré.
 Dans un graphe orienté, on distingue :

 le degré entrant (deg (v)) : nombre d'arcs arrivant en v ;

−

 le degré sortant (deg (v)) : nombre d'arcs partant de v .

+

Exemple 1.1.4. Considérons le graphe :

E = {(A, B), (A, C), (B, D), (C, D)}

Alors :
 deg(A) = 2
 deg(B) = 2
 deg(C) = 2
 deg(D) = 2
Remarque 1.1.4. Dans tout graphe non orienté, la somme des degrés de tous les sommets
est égale à deux fois le nombre d'arêtes :
X
deg(v) = 2|E|
v∈V

Cette propriété est appelée lemme de la poignée de main.

1.1.5 Exemple complet de graphe
Exemple 1.1.5. On considère le graphe G = (V, E) déni par :
V = {A, B, C, D}, E = {(A, B), (A, C), (B, D), (C, D)}

A B

C D
Remarque 1.1.5. Ce graphe est non orienté (les arêtes n'ont pas de direction) et non
pondéré (aucun poids n'est associé aux arêtes).

1.2 Types de graphes

1.2.1 Graphe non orienté

Dénition 1.2.1. Un graphe non orienté est un graphe dans lequel les arêtes n'ont
pas de direction. Autrement dit, une arête reliant deux sommets u et v est notée {u, v} et
vérie :
{u, v} = {v, u}.
Interprétation : Dans un graphe non orienté, la relation entre deux sommets est
symétrique : si un sommet u est relié à un sommet v, alors v est également relié à u.

7
  Une arête {u, v} signie que l'on peut aller de u vers v et de v vers u.
 Les arêtes sont représentées graphiquement par des segments sans èche.

Exemple 1.2.1. Le graphe ci-dessous est un graphe non orienté comportant trois sommets
, et C , chacun étant relié aux deux autres.
A B

A B

Remarque 1.2.1.  Un graphe non orienté est souvent utilisé pour modéliser des
relations réciproques (amitié, routes à double sens, connexions physiques, etc.).
 Dans ce type de graphe, la notion de voisinage est symétrique : si u est voisin de v,
alors v est voisin de u.
1.2.2 Graphe orienté
Dénition 1.2.2. Un graphe orienté (ou digraphe) est un graphe dans lequel les arêtes
possèdent une direction. Ces arêtes orientées sont appelées arcs et sont représentées par
des couples ordonnés :
(u, v) ̸= (v, u).

Interprétation : Dans un graphe orienté, la relation entre deux sommets n'est pas
nécessairement symétrique. Un arc (u, v) indique un déplacement ou une relation allant
de u vers v, sans impliquer l'existence du chemin inverse.

 Un arc (u, v) signie que l'on peut aller de u vers v , mais pas forcément de v vers u.
 Les arcs sont représentés graphiquement par des èches indiquant le sens de la
relation.

Exemple 1.2.2. Le graphe ci-dessous est un graphe orienté comportant trois sommets
A, B et C . Les arcs indiquent les directions possibles entre les sommets.

A B

Remarque 1.2.2.  Dans un graphe orienté, on distingue le degré entrant et le

degré sortant de chaque sommet.
 Les graphes orientés sont utilisés pour modéliser des relations asymétriques (ux de
données, sens unique, dépendances, hiérarchies, etc.).
 Deux sommets peuvent être reliés par deux arcs opposés (u, v) et (v, u).

8
1.2.3 Cycles dans un graphe
Dénition 1.2.3. Un cycle est une suite de sommets v , v , . . . , v (k ≥ 3) telle que :
 chaque paire de sommets consécutifs est reliée par une arête (ou un arc);
1 2 k

 le premier et le dernier sommet coïncident : v = v ;

 aucun sommet n'est répété, sauf le premier et le dernier.
1 k

Cycle dans un graphe non orienté

Dans un graphe non orienté, un cycle est une boucle fermée.

Exemple 1.2.3. Le cycle A → B → C → A est mis en évidence ci-dessous :

A B

Cycle dans un graphe orienté

Dans un graphe orienté, un cycle doit respecter le sens des arcs.

Exemple 1.2.4. Le cycle orienté A → B → C → A est mis en évidence ci-dessous :

A B

Remarque 1.2.3.  Les cycles sont souvent mis en évidence graphiquement à l'aide
de couleurs ou d'un tracé plus épais.
 La détection de cycles est un problème fondamental en théorie des graphes.
 Un graphe sans cycle est dit acyclique.
1.2.4 Boucles dans un graphe
Dénition 1.2.4. Une boucle est une arête (ou un arc) qui relie un sommet à lui-même.
Autrement dit, c'est une arête de la forme :
(v, v) ∈ E.

Interprétation : Une boucle représente une relation d'un sommet avec lui-même. Cela
peut modéliser, par exemple, une action interne, une auto-connexion ou une dépendance
réexive.

9
Boucle dans un graphe non orienté
Dans un graphe non orienté, une boucle est une arête reliant un sommet à lui-même,
sans notion de direction.

Exemple 1.2.5. Le sommet A possède une boucle :

A B

Boucle dans un graphe orienté

Dans un graphe orienté, une boucle est un arc orienté partant d'un sommet et
revenant vers ce même sommet.

Exemple 1.2.6. Le sommet A possède une boucle orientée :

A B

Remarque 1.2.4.  Une boucle contribue pour deux au degré d'un sommet dans un
graphe non orienté.
 Dans un graphe orienté, une boucle contribue pour un au degré entrant et un au
degré sortant.
 Un graphe sans boucle est dit simple (s'il ne possède pas non plus d'arêtes mul-
tiples).
1.2.5 Graphes simples et multigraphes
Dénition 1.2.5. Un graphe simple est un graphe non orienté qui ne contient :
 ni boucles ;
 ni arêtes multiples (plusieurs arêtes entre deux mêmes sommets).
Interprétation : Dans un graphe simple, chaque paire de sommets est reliée par au
plus une seule arête, et aucun sommet n'est relié à lui-même.

Exemple 1.2.7. Le graphe ci-dessous est un graphe simple :

A B

Dénition 1.2.6. Un multigraphe est un graphe dans lequel on autorise :

 plusieurs arêtes entre une même paire de sommets;
10
  éventuellement des boucles.
Interprétation : Un multigraphe permet de modéliser des situations où plusieurs
relations distinctes existent entre deux mêmes entités.

Exemple 1.2.8. Le graphe ci-dessous est un multigraphe : il contient deux arêtes entre
A et B, ainsi qu'une boucle sur A.
A B

Remarque 1.2.5.  Les graphes simples sont les plus utilisés en théorie des graphes
classique.
 Les multigraphes sont utiles pour modéliser des réseaux complexes (routes multiples,
communications parallèles, etc.).
 Lorsqu'un graphe orienté autorise plusieurs arcs entre deux sommets, on parle aussi
de multigraphe orienté.
1.2.6 Chemins et chaînes dans un graphe
Dénition 1.2.7. Dans un graphe G = (V, E), un chemin est une suite de sommets :
v1 , v2 , . . . , vk
telle que chaque paire consécutive (v , v ) est reliée par une arête (ou un arc) du graphe.
i i+1

Interprétation : Un chemin représente une succession de déplacements possibles d'un

sommet à un autre en suivant les arêtes du graphe.

Exemple 1.2.9. Dans le graphe suivant, une chaîne possible est :

A→B→D

Chaîne dans un graphe non orienté

Dans un graphe non orienté, on parle souvent de chaîne.

Dénition 1.2.8. Une chaîne est une suite de sommets où chaque paire consécutive est
reliée par une arête, sans tenir compte de l'orientation.
Interprétation : On peut parcourir les arêtes dans les deux sens.
Exemple 1.2.10. La chaîne suivante est valide :
A−B−C −D

Chemin dans un graphe orienté

Dans un graphe orienté, on parle de chemin orienté.

Dénition 1.2.9. Un chemin orienté est une suite de sommets telle que chaque arc
est parcouru dans le sens de son orientation.
Interprétation : On ne peut suivre que le sens des èches.
Exemple 1.2.11. Dans le graphe suivant, on a un chemin orienté :
A→B→C

11
Longueur d'un chemin
Dénition 1.2.10. La longueur d'un chemin est le nombre d'arêtes (ou d'arcs) qui le
composent.
Exemple 1.2.12. Le chemin A → B → C → D est de longueur 3.
Remarque 1.2.6.  Un chemin est dit simple s'il ne repasse pas par un même som-
met.
 Un chemin fermé (qui revient à son point de départ) est appelé un cycle.
 Les chemins sont fondamentaux pour étudier la connexité et les distances dans
un graphe.
1.2.7 Connexité d'un graphe
Dénition 1.2.11. Un graphe est dit connexe si, pour toute paire de sommets (u, v) ∈ V ,
il existe au moins un chemin reliant u à v.
Interprétation : Un graphe connexe représente un système dans lequel il est possible
d'aller d'un sommet à n'importe quel autre en suivant les arêtes du graphe.

Exemple 1.2.13. Le graphe ci-dessous est connexe car tous les sommets sont reliés par
des chemins :
A B

C D

Dénition 1.2.12. Un graphe est dit non connexe s'il existe au moins deux sommets
entre lesquels aucun chemin n'existe.
Interprétation : Un graphe non connexe est composé de plusieurs parties isolées
composantes connexes.
appelées

Exemple 1.2.14. Le graphe suivant n'est pas connexe :

 A et B forment une composante;
 C et D forment une autre composante.
A B C D

Composantes connexes
Dénition 1.2.13. Une composante connexe est un sous-graphe connexe maximal,
c'est-à-dire un ensemble de sommets connectés entre eux et non extensible sans perdre la
connexité.
Remarque 1.2.7.  Un graphe connexe possède une seule composante connexe.
 Un graphe non connexe possède au moins deux composantes connexes.
 La connexité est une notion fondamentale pour l'analyse des réseaux.
12
1.2.8 Distance dans un graphe
Dénition 1.2.14. Dans un graphe G = (V, E), la distance entre deux sommets u et v,
notée d(u, v), est la longueur du plus court chemin reliant u à v.
Interprétation : La distance mesure le nombre minimal d'arêtes (ou d'arcs) néces-
saires pour aller d'un sommet à un autre.

 Si aucun chemin n'existe entre u et v, alors on pose d(u, v) = +∞.

 Si u = v, alors d(u, u) = 0.
Exemple 1.2.15. Dans le graphe suivant :
A−B−C −D
on a :
 d(A, B) = 1
 d(A, C) = 2 (chemin A → B → C )
 d(A, D) = 3
Dénition 1.2.15. La distance dans un graphe non pondéré est égale au nombre
minimal d'arêtes dans un chemin reliant deux sommets.
Remarque 1.2.8.  La distance est toujours positive ou nulle : d(u, v) ≥ 0.
 Elle vérie d(u, v) = d(v, u) dans un graphe non orienté.
 Dans un graphe orienté, la distance peut ne pas être symétrique.
Propriétés de la distance
 Identité : d(u, u) = 0

 Symétrie (non orienté) : d(u, v) = d(v, u)

 Inégalité triangulaire : d(u, w) ≤ d(u, v) + d(v, w)

Remarque 1.2.9. La notion de distance est fondamentale dans l'étude des réseaux, no-
tamment pour les algorithmes de plus court chemin comme l'algorithme de Dijkstra.
1.2.9 Arbres et forêts
Arbres
Dénition 1.2.16. Un arbre est un graphe non orienté, connexe et sans cycle.
Interprétation : Un arbre est un graphe dans lequel il existe un unique chemin entre
toute paire de sommets. Il ne contient aucune boucle fermée.

Exemple 1.2.16. Le graphe suivant est un arbre :

A

B C

D E

13
Remarque 1.2.10. Un arbre à n sommets possède toujours exactement n − 1 arêtes.
Propriétés des arbres
 Un arbre est un graphe connexe.
 Un arbre est acyclique (ne contient aucun cycle).
 Entre deux sommets d'un arbre, il existe un unique chemin.

 Ajouter une arête à un arbre crée toujours un cycle.

 Supprimer une arête d'un arbre le rend non connexe.

Forêts
Dénition 1.2.17. Une forêt est un graphe non orienté sans cycle. Autrement dit, une
forêt est un ensemble de plusieurs arbres disjoints.
Interprétation : Une forêt peut être vue comme un graphe dont chaque composante
connexe est un arbre.

Exemple 1.2.17. Le graphe suivant est une forêt composée de deux arbres distincts :
A D

B C E F

Remarque 1.2.11.  Une forêt est un graphe acyclique.

 Chaque composante connexe d'une forêt est un arbre.
 Les forêts apparaissent souvent dans les structures hiérarchiques et les algorithmes
d'optimisation.
1.2.10 Comparaison : graphe orienté / non orienté

Type Arêtes Exemples d'application

Non orienté Sans direction ({u, v}) Réseau de routes à double sens, réseau social (amitié)

Orienté Avec direction (u → v) Flux d'eau, dépendances de tâches, réseaux de transport

Observation : Dans un graphe orienté, la relation entre deux sommets n'est pas
nécessairement réciproque. En conséquence, les algorithmes de parcours (DFS, BFS) et
de recherche de plus court chemin doivent prendre en compte le sens des arêtes.

Remarque 1.2.12.  Un graphe non orienté peut être vu comme un cas particulier
d'un graphe orienté où chaque arête est remplacée par deux arcs opposés.
 Le choix entre orienté et non orienté dépend directement du phénomène modélisé.

14
1.2.11 Graphe non pondéré
Dénition 1.2.18. Un graphe non pondéré est un graphe dans lequel toutes les arêtes
sont considérées comme ayant le même poids, généralement égal à 1. Autrement dit, au-
cune valeur numérique (distance, coût, durée, etc.) n'est associée aux arêtes.
Interprétation : Dans un graphe non pondéré, seule la structure des connexions entre
les sommets est prise en compte, sans distinction d'intensité ou de coût entre les relations.

 Tous les déplacements entre deux sommets adjacents ont le même  coût .

 Les algorithmes se basent uniquement sur la connectivité et le nombre d'arêtes

parcourues.

Exemple 1.2.18. Un réseau social où chaque relation d'amitié est considérée comme
équivalente est un exemple typique de graphe non pondéré.
A B

Remarque 1.2.13.  Un graphe non pondéré peut être vu comme un cas particulier
de graphe pondéré où tous les poids sont égaux à 1.
 La distance entre deux sommets correspond alors au nombre minimal d'arêtes entre
eux.
1.2.12 Graphe pondéré
Dénition 1.2.19. Un graphe pondéré est un graphe dans lequel chaque arête est as-
sociée à une valeur numérique appelée poids. Ce poids peut représenter, selon le contexte,
une distance, un coût, une durée ou une capacité.
Interprétation : Un graphe pondéré permet de modéliser des situations où les re-
lations entre sommets ne sont pas équivalentes, mais possèdent une intensité ou un coût
diérent.

 Les poids sont généralement notés w(u, v) pour une arête (u, v).
 Les algorithmes de plus court chemin (comme Dijkstra) utilisent ces poids pour
optimiser les trajets.

Exemple 1.2.19. Un réseau routier est un exemple typique de graphe pondéré : les arêtes
représentent les routes et les poids représentent les distances ou les temps de trajet.
5
A B

2 3

15
Remarque 1.2.14.  Un graphe non pondéré peut être vu comme un cas particulier
de graphe pondéré où tous les poids sont égaux à 1.
 La notion de distance dans un graphe pondéré correspond à la somme minimale des
poids des arêtes d'un chemin.
1.2.13 Graphe simple
Dénition 1.2.20. Un graphe simple est un graphe non orienté qui ne contient ni
boucles ni arêtes multiples. Autrement dit, entre deux sommets distincts, il existe au plus
une seule arête.
Interprétation : Un graphe simple modélise une situation où chaque relation entre
deux entités est unique et sans auto-connexion.

A B

Remarque 1.2.15.  Les graphes simples sont les plus utilisés en théorie des graphes
classique.
 Ils servent de base pour dénir de nombreuses notions comme les chemins, les cycles
et la connexité.
 Un graphe simple est toujours non orienté (dans la dénition standard).
1.2.14 Multigraphe
Dénition 1.2.21. Un multigraphe est un graphe dans lequel il est possible d'avoir plu-
sieurs arêtes entre deux mêmes sommets, ainsi que des boucles (arêtes reliant un sommet
à lui-même).
Interprétation : Un multigraphe permet de modéliser des situations où plusieurs
relations distinctes existent entre les mêmes entités, ou lorsqu'une entité peut être reliée
à elle-même.

A B

Remarque 1.2.16.  Un multigraphe généralise la notion de graphe simple en auto-

risant des arêtes multiples.
 Les boucles et arêtes multiples sont souvent utilisées pour représenter des réseaux
complexes (communications, transports, interactions multiples).
 Si les arêtes sont orientées, on parle de multigraphe orienté.

16
1.3 Représentation des graphes

1.3.1 Listes d'adjacence

Exemple introductif : Considérons le graphe orienté suivant :
A B

C D

Dénition 1.3.1. Une liste d'adjacence est une représentation d'un graphe dans la-
quelle chaque sommet est associé à l'ensemble de ses successeurs directs (dans le cas
d'un graphe orienté) ou de ses voisins (dans le cas d'un graphe non orienté).
Liste d'adjacence du graphe précédent :
 A : B, C

 B : D

 C : D

 D : -

Interprétation : Cette représentation indique que :

 depuis le sommet A, on peut atteindre directement B et C;
 depuis B, on peut atteindre D;
 depuis C, on peut atteindre D;
 le sommet D ne possède aucun arc sortant.

Remarque 1.3.1.  La liste d'adjacence est une représentation économe en mé-

moire, particulièrement adaptée aux graphes peu denses.
 Elle permet un accès rapide aux voisins d'un sommet.
 Elle est largement utilisée dans les algorithmes de parcours comme BFS et DFS.
1.3.2 Matrice d'adjacence
Considérons la matrice d'adjacence suivante, associée aux sommets ordonnés A, B, C, D :
 
0 1 1 0
0 0 0 1
M =
0

0 0 1
0 0 0 0
Dénition 1.3.2. La matrice d'adjacence d'un graphe orienté est une matrice carrée
M = (mij ) telle que :

1 si il existe un arc de i vers j,

(

0 sinon.
m =ij

17
 Interprétation de la matrice :
Chaque ligne correspond à un sommet de départ, et chaque colonne à un sommet
d'arrivée.

 Ligne A : (0, 1, 1, 0) Le sommet A est relié à B et C .

 Ligne B : (0, 0, 0, 1) Le sommet B est relié à D uniquement.

 Ligne C : (0, 0, 0, 1) Le sommet C est également relié à D uniquement.

 Ligne D : (0, 0, 0, 0) Le sommet D n'a aucun arc sortant.

Graphe correspondant :
A B

C D

Remarque 1.3.2.  Une matrice d'adjacence permet de représenter un graphe de

manière algébrique.
 Elle est très utile pour les algorithmes utilisant des opérations matricielles.
 La somme des lignes donne le degré sortant de chaque sommet.
 La somme des colonnes donne le degré entrant.
1.3.3 Matrice d'adjacence d'un graphe pondéré
Dans un graphe pondéré, les arêtes sont associées à des valeurs numériques appelées
poids. La matrice d'adjacence est alors adaptée pour représenter ces poids.
Dénition 1.3.3. Soit un graphe pondéré G = (V, E) avec |V | = n. La matrice d'ad-
jacence pondérée est une matrice M = (mij ) dénie par :
si une arête de poids w(i, j) relie i à j,
(
w(i, j)
mij =
0 ou+∞ sinon.
Remarque importante :
 On utilise souvent 0 si l'absence d'arête n'est pas problématique.

 On utilise souvent +∞ dans les algorithmes de plus court chemin (ex : Dijkstra)
pour indiquer qu'il n'y a pas de liaison directe.

Exemple :
Considérons le graphe pondéré suivant :

5
A B

2 3

C D
1

18
 Les sommets sont ordonnés : A, B, C, D.
La matrice d'adjacence pondérée correspondante est :

 
0 5 2 0
0 0 0 3
M =
0

0 0 1
0 0 0 0
Interprétation :
 A→B a un poids de 5.

 A→C a un poids de 2.

 B→D a un poids de 3.

 C→D a un poids de 1.

 Les zéros indiquent l'absence d'arête directe.

Remarque 1.3.3.  La matrice pondérée généralise la matrice d'adjacence classique.

 Elle est essentielle pour les algorithmes de plus court chemin.
 Dans un graphe non orienté, la matrice est symétrique.
1.3.4 Exemple de graphe pondéré avec valeurs innies dans la
matrice
Considérons le graphe pondéré suivant :

4
A B

1 2

C D

Interprétation du graphe :
 A→B de poids 4

 A→C de poids 1

 B→D de poids 2

 Aucune autre arête directe

Matrice d'adjacence pondérée (ordre : A, B, C, D) :

 
0 4 1 +∞
+∞ 0 +∞ 2 
M =
+∞ +∞ 0 +∞


+∞ +∞ +∞ 0
Mineur contenant des valeurs innies :
Considérons le sous-graphe induit par les sommets {B, C, D} :

19
  
0 +∞ 2
M{B,C,D} = +∞ 0 +∞
+∞ +∞ 0
Interprétation :
 Ce mineur contient plusieurs valeurs +∞, ce qui signie qu'il n'existe pas d'arêtes
directes entre plusieurs paires de sommets.

 Par exemple, il n'existe pas de liaison directe entre B et C, ni entre C et D.

Remarque 1.3.4.  Les valeurs +∞ sont utilisées pour représenter l'absence de connexion
directe dans les algorithmes de plus court chemin.
 Même si un mineur contient des +∞, il peut exister un chemin indirect dans le
graphe complet.
1.3.5 Piles et les
Les piles et les les sont des structures de données fondamentales utilisées notamment
dans les algorithmes sur les graphes comme DFS et BFS.

Pile (Stack)
Dénition 1.3.4. Une pile est une structure de données de type LIFO (Last In, First
Out), ce qui signie que le dernier élément inséré est le premier à être retiré.
Interprétation : Une pile fonctionne comme une pile d'assiettes : on ajoute et on
retire toujours par le sommet, sans accès direct aux éléments intermédiaires.
Opérations principales :
 empiler (push) : ajouter un élément au sommet de la pile ;

 dépiler (pop) : retirer l'élément situé au sommet ;

 sommet (top) : consulter le dernier élément ajouté sans le supprimer ;

 estVide : tester si la pile ne contient aucun élément.

Utilisation en théorie des graphes :

 La pile est utilisée dans le parcours en profondeur DFS.

 Elle permet d'explorer un chemin le plus loin possible avant de revenir en arrière
(backtracking).
 Elle correspond à la gestion implicite de la récursion (pile d'appels système).

Exemple 1.3.1. Considérons une pile initialement vide :

 Empiler A → [A]
 Empiler B → [A, B]
 Empiler C → [A, B, C]
Lors des dépilements successifs :
C→B→A

Conclusion : le dernier élément inséré est le premier à sortir.

20
Remarque 1.3.5.  La pile est fondamentale pour les algorithmes récursifs et les
parcours en profondeur.
 Elle permet une gestion ecace des structures hiérarchiques.
 Elle est largement utilisée en informatique (analyse syntaxique, appels de fonctions,
DFS).
File (Queue)
Dénition 1.3.5. Une le est une structure de données de type FIFO (First In, First
Out), ce qui signie que le premier élément inséré est le premier à être retiré.
Interprétation : Une le fonctionne comme une le d'attente : les éléments arrivent
à la n et sortent par le début.
Opérations principales :
 enler (enqueue) : ajouter un élément à la n de la le ;

 déler (dequeue) : retirer l'élément situé au début ;

 tête (front) : accéder au premier élément sans le supprimer ;

 estVide : vérier si la le est vide.

Utilisation en théorie des graphes :

 La le est utilisée dans le parcours en largeur BFS.

 Elle permet une exploration par niveaux successifs.

 Elle garantit que les sommets sont traités dans l'ordre de leur découverte.

Exemple 1.3.2. Considérons une le vide :

 Enler A → [A]
 Enler B → [A, B]
 Enler C → [A, B, C]
Ordre de délement :
A→B→C
Conclusion : le premier élément inséré est le premier à sortir.
Remarque 1.3.6.  La le est fondamentale pour les algorithmes de parcours en lar-
geur (BFS).
 Elle permet une exploration par couches successives dans un graphe.
 Elle est utilisée dans de nombreux problèmes de recherche de plus court chemin en
graphe non pondéré.
1.3.6 Représentation graphique : pile vs le
Pile (Stack - LIFO)
sommet

B pop (dépiler)

A push (empiler)

21
 File (Queue - FIFO)

entrée (enqueue) A B C sortie (dequeue)

front back

1.4 Parcours de graphe

1.4.1 Parcours en largeur (BFS)

Le parcours en largeur (Breadth-First Search, BFS) est un algorithme qui explore
un graphe en visitant d'abord les sommets les plus proches d'un sommet de départ, puis
progressivement les sommets plus éloignés.
Principe :
 On part d'un sommet initial.

 On visite d'abord tous ses voisins directs.

 Puis on explore les voisins des voisins, et ainsi de suite.

Exemple :
Considérons le graphe suivant :

A B

C D

Application du BFS à partir de A :

 Étape 1 : on visite A
 Étape 2 : on visite ses voisins B et C
 Étape 3 : on visite les voisins de B et C, ici D
Ordre de parcours BFS :
A→B→C→D

Remarque 1.4.1.  BFS utilise une structure de le (queue).

 Il permet de trouver les plus courts chemins dans un graphe non pondéré.
 Il explore le graphe par niveaux.

22
1.4.2 Parcours en profondeur (DFS)
Le parcours en profondeur (Depth-First Search, DFS) est un algorithme qui explore
un graphe en suivant un chemin aussi loin que possible avant de revenir en arrière.
Principe :
 On part d'un sommet initial.

 On explore récursivement un voisin non visité.

 Lorsqu'un sommet n'a plus de voisin non visité, on revient en arrière (backtracking).

Exemple :
Considérons le même graphe :

A B

C D

Application du DFS à partir de A :

 On commence à A
 On visite B
 Depuis B, on visite D
 Retour en arrière, puis on visite C
Ordre possible de parcours DFS :
A→B→D→C

Remarque 1.4.2.  DFS utilise une structure de pile (stack) ou la récursion.

 L'ordre de parcours peut varier selon l'ordre des voisins.
 DFS est utile pour détecter des cycles et explorer des composantes connexes.
1.5 Plus courts chemins

1.5.1 Dénition
Dans un graphe pondéré, on associe à chaque arête une valeur numérique appelée
poids.
 Le poids d'un chemin est la somme des poids des arêtes qui le composent.
 La distance entre deux sommets a et b, notée δ(a, b), est dénie comme le poids
minimal de tous les chemins reliant a à b.
Formellement :
δ(a, b) = min{poids(P ) | P est un chemin de a à b}

23
Exemple : calcul de δ(A, D)
Considérons le graphe pondéré suivant :

4
A B

1 2
3

C D
5

Nous voulons calculer la distance δ(A, D).

Étape 1 : identier les chemins possibles
 A→B→D
 A→C→D
 A→B→C→D
Étape 2 : calcul des poids
 A→B →D :4+2=6
 A→C →D :1+5=6
 A → B → C → D : 4 + 3 + 5 = 12
Étape 3 : choix du minimum
δ(A, D) = min(6, 6, 12) = 6
Conclusion :
δ(A, D) = 6

Remarque 1.5.1.  Plusieurs chemins peuvent exister entre deux sommets.

 La distance correspond toujours au chemin de coût minimal.
 Les algorithmes comme Dijkstra permettent de trouver ce résultat ecacement sans
tester tous les chemins.
1.5.2 Algorithme de Dijkstra
L'algorithme de Dijkstra permet de déterminer les plus courtes distances depuis un
sommet source vers tous les autres sommets d'un graphe pondéré à poids positifs.
Principe :
 On attribue une distance provisoire à chaque sommet.

 On choisit à chaque étape le sommet non visité ayant la plus petite distance.

 On met à jour les distances de ses voisins (relaxation).

 On répète jusqu'à avoir traité tous les sommets.

Exemple : calcul des plus courts chemins à partir de A

24
 1
A B

2 3

C D
1

Étape 1 : initialisation
 d(A) = 0
 d(B) = +∞, d(C) = +∞, d(D) = +∞
Étape 2 : depuis A
 d(B) = 1
 d(C) = 2
Étape 3 : sommet le plus proche = B
 d(D) = d(B) + 3 = 4
Étape 4 : sommet suivant = C
 d(D) = min(4, d(C) + 1) = min(4, 3) = 3
Étape 5 : sommet nal = D
Résultat nal :
d(A, B) = 1, d(A, C) = 2, d(A, D) = 3

Remarque 1.5.2.  Dijkstra fonctionne uniquement avec des poids positifs ou nuls.
 Il garantit des distances optimales depuis un sommet source.
 Sa complexité dépend de la structure de données utilisée (le de priorité).
1.5.3 Algorithme de Dijkstra
L'algorithme de Dijkstra permet de déterminer les plus courts chemins depuis un
sommet source dans un graphe pondéré à poids positifs.
Exemple : calcul des distances à partir de A
1
A B

2 3

C D
1

Tableau des itérations avec explications :

25
 Étape Sommet xé d(A) d(B) d(C) d(D)
Initialisation - 0 +∞ +∞ +∞
1 A 0 1 2 +∞
2 B 0 1 2 4

3 C 0 1 2 3

4 D 0 1 2 3

Explication détaillée des étapes :

 Initialisation :

 On xe d(A) = 0 car A est le sommet de départ.

 Tous les autres sommets ont une distance innie car ils ne sont pas encore
atteints.

 Étape 1 (sommet A xé) :

 Depuis A, on atteint B avec coût 1 ⇒ d(B) = 1.
 Depuis A, on atteint C avec coût 2 ⇒ d(C) = 2.

 D reste inaccessible directement depuis A ⇒ d(D) = +∞.

 Étape 2 (sommet B xé) :

 On met à jour D via B : A → B → D = 1 + 3 = 4.
 Donc d(D) = 4.
 Étape 3 (sommet C xé) :
 On met à jour D via C : A → C → D = 2 + 1 = 3.
 On compare avec 4 et on garde le minimum : d(D) = 3.

 Étape 4 (sommet D xé) :

 D est nalisé, aucune mise à jour supplémentaire.

Résultat nal :
d(A, B) = 1, d(A, C) = 2, d(A, D) = 3

Remarque 1.5.3.  Chaque valeur du tableau représente une meilleure estimation à

chaque étape.
 Une valeur ne change que si un chemin plus court est trouvé.
 Une fois un sommet xé, sa distance devient dénitive.
1.5.4 Pseudo-code de l'algorithme de Dijkstra
Entrée : un graphe pondéré G = (V, E) avec poids positifs, et un sommet source s
Sortie : les distances minimales δ(s, v) pour tout sommet v ∈ V

26
 Algorithme de Dijkstra
1. Pour tout sommet v ∈ V , faire d(v) ← +∞
2. d(s) ← 0
3. Q ← V (ensemble des sommets non traités)
4. Tant que Q ̸= ∅ faire :
4.1 Choisir u ∈ Q tel que d(u) est minimal
4.2 Retirer u de Q
4.3 Pour chaque voisin v de u dans Q faire :
si d(u) + w(u, v) < d(v) alors
d(v) ← d(u) + w(u, v)

Explication ligne par ligne

 Ligne 1 : Initialisation des distances

 On suppose que tous les sommets sont très éloignés au départ.

 On utilise +∞ pour indiquer qu'aucun chemin n'est encore connu.

 Ligne 2 : Sommet source

 La distance du sommet de départ s est xée à 0.

 C'est le point de départ de tous les calculs.

 Ligne 3 : Ensemble des sommets non traités

 Q contient tous les sommets du graphe.

 On va progressivement les retirer lorsqu'ils sont traités.

 Ligne 4 : Boucle principale

 Tant qu'il reste des sommets non traités, on continue l'algorithme.

 Ligne 4.1 : Choix du sommet minimal

 On sélectionne le sommet u avec la plus petite distance connue.

 Ce sommet est le plus proche du départ parmi les non traités.

 Ligne 4.2 : Marquer comme traité

 Une fois sélectionné, u ne sera plus modié.

 Sa distance devient dénitive.

 Ligne 4.3 : Relaxation des voisins

 On examine tous les voisins v de u.
 On teste si passer par u améliore la distance vers v.
 Condition de mise à jour
 Si d(u) + w(u, v) < d(v) alors un chemin plus court est trouvé.

 On met à jour d(v) avec cette nouvelle valeur.

Remarque 1.5.4.  Dijkstra fonctionne uniquement avec des poids positifs.

 Il garantit des distances optimales.
 Il est souvent implémenté avec une le de priorité pour accélérer la sélection du
minimum.

27
1.5.5 Graphe hamiltonien
Dénition 1.5.1. Un graphe hamiltonien est un graphe qui contient un cycle hamil-
tonien, c'est-à-dire un cycle simple passant par tous les sommets du graphe exactement
une fois, avant de revenir au sommet initial.
Autrement dit : Un graphe est hamiltonien s'il existe un parcours fermé qui :
 visite chaque sommet une et une seule fois ;

 ne répète aucun sommet (sauf le premier à la n) ;

 forme un cycle.

Remarque :
 Un graphe peut être connexe sans être hamiltonien.

 L'existence d'un cycle hamiltonien est dicile à déterminer en général.

Cycle hamiltonien
Un cycle hamiltonien est une suite de sommets :

v1 → v2 → · · · → vn → v1

telle que :

 tous les sommets v1 , v2 , . . . , vn sont deux à deux distincts ;

 chaque sommet du graphe apparaît exactement une fois dans la suite ;

 chaque paire (vi , vi+1 ) correspond à une arête du graphe ;

 le sommet initial est égal au sommet nal (v1 ), ce qui forme un cycle.

Remarque :
 Le cycle contient exactement n arêtes si le graphe possède n sommets.

 Il ne faut pas confondre un cycle hamiltonien avec un simple cycle : ici, tous les
sommets doivent être visités.

Exemple
Considérons le graphe suivant :

A B

D C

Observation : Chaque sommet est relié de manière à former un cycle.

Cycle hamiltonien :
A→B→C→D→A
Vérication :
28
  tous les sommets A, B, C, D sont visités ;

 aucun sommet n'est répété ;

 le parcours revient au sommet initial ;

 chaque déplacement correspond à une arête du graphe.

Conclusion : Ce graphe est hamiltonien.

Contre-exemple
Considérons le graphe suivant :

A B

D C

Observation : Le sommet E est relié uniquement au sommet C .

Analyse :
 Pour qu'un cycle hamiltonien existe, chaque sommet doit être traversé avec deux
arêtes (entrée et sortie).

 Le sommet E est de degré 1.

Conséquence :
 On peut entrer dans E, mais on ne peut pas en sortir sans repasser par C.
 Cela impose de répéter un sommet, ce qui est interdit dans un cycle hamiltonien.

Conclusion :
Le graphe n'est pas hamiltonien.

Remarques
 Un graphe peut être connexe sans être hamiltonien.

 Il n'existe pas de critère simple permettant de déterminer si un graphe est hamilto-

nien.

 Le problème de déterminer l'existence d'un cycle hamiltonien est dicile (problème

NP-complet).

29
Comparaison avec les graphes eulériens
Type Porte sur Condition principale
Hamiltonien Sommets Passer une fois par chaque sommet
Eulerien Arêtes Passer une fois par chaque arête

Condition susante (théorème de Dirac)

Théorème 1.5.1. Soit un graphe simple à n ≥ 3 sommets. Si chaque sommet vérie :
n
deg(v) ≥
2
alors le graphe est hamiltonien.
Interprétation
Un graphe hamiltonien modélise des situations où l'on doit visiter chaque point une
seule fois, par exemple :

 tournées de livraison

 problème du voyageur de commerce

 planication de circuits

1.5.6 Graphe eulérien

Dénition 1.5.2. Un graphe eulérien est un graphe connexe qui possède un cycle
eulérien, c'est-à-dire un cycle qui parcourt chaque arête du graphe exactement une fois
et revient au sommet de départ.
Autrement dit : Un graphe est eulérien s'il existe un parcours fermé qui :
 utilise chaque arête une et une seule fois ;

 ne répète aucune arête ;

 commence et se termine au même sommet.

Remarque :
 La condition de connexité (en ignorant les sommets isolés) est essentielle.

 Un graphe eulérien peut revisiter des sommets, mais jamais des arêtes.

Cycle eulérien
Un cycle eulérien est une suite de sommets :

v1 → v2 → · · · → vk → v1
telle que :

 chaque paire (vi , vi+1 ) correspond à une arête du graphe ;

 chaque arête du graphe est parcourue exactement une fois ;

 aucune arête n'est répétée ;

 le parcours est fermé, c'est-à-dire que v1 = vk+1 .

Remarque :
 Un sommet peut apparaître plusieurs fois dans un cycle eulérien.

 Le nombre d'arêtes du cycle est égal au nombre total d'arêtes du graphe.

30
Exemple
Considérons le graphe suivant :

A B

D C

Observation : Chaque sommet a un degré égal à 3, donc le graphe contient des

sommets de degré impair.
Conclusion préalable : Un graphe eulérien doit avoir tous ses sommets de degré
pair, donc ce graphe n'est pas eulérien.
Remarque importante : Il ne peut donc pas exister de cycle eulérien parcourant
toutes les arêtes exactement une fois.
Correction de l'exemple : Le chemin proposé :
A→B→C→D→A→C→B→D→A

n'est pas valide comme cycle eulérien, car certaines arêtes sont répétées.
Conclusion :
Ce graphe n'admet pas de cycle eulérien.

Exemple de graphe eulérien

Considérons le graphe suivant :

A B

D C

Étape 1 : degrés des sommets

 d(A) = 3
 d(B) = 3
 d(C) = 3
 d(D) = 3
Le graphe n'est donc pas eulérien.

Pour obtenir un exemple eulérien correct, modions le graphe :

31
 A B

D C

Vérication des degrés :

 d(A) = 2
 d(B) = 2
 d(C) = 2
 d(D) = 2
Tous les sommets ont un degré pair ⇒ le graphe est eulérien.

Un cycle eulérien possible :
A→B→C→D→A→B→C→D→A
Conclusion : Le graphe est eulérien car il est connexe et tous ses sommets sont de
degré pair.

Condition nécessaire et susante

Théorème 1.5.2. Un graphe non orienté est eulérien si et seulement s'il est connexe (en
ignorant les sommets isolés) et si tous ses sommets sont de degré pair.
Remarques importantes :
 La connexité est nécessaire pour pouvoir parcourir toutes les arêtes dans un même
cycle.

 La condition degré pair garantit qu'à chaque entrée dans un sommet, il existe une
sortie possible.

 Les sommets isolés n'aectent pas l'eulériannité du graphe.

Chemin eulérien
Dénition 1.5.3. Un chemin eulérien est une suite de sommets reliant deux som-
mets du graphe, telle que chaque arête du graphe est parcourue exactement une fois, sans
nécessairement revenir au sommet de départ.
Remarque :
 Un chemin eulérien peut être ouvert (départ ̸= arrivée).

 Contrairement au cycle eulérien, il ne forme pas forcément une boucle.

Théorème 1.5.3. Un graphe non orienté est eulérien au sens de chemin (c'est-à-dire
admet un chemin eulérien) si et seulement s'il est connexe (en ignorant les sommets
isolés) et s'il possède exactement deux sommets de degré impair.
Interprétation :
 Les deux sommets de degré impair correspondent au point de départ et au point
d'arrivée du chemin.

 Tous les autres sommets ont un degré pair, garantissant une entrée et une sortie à
chaque passage.

32
Contre-exemple
Considérons le graphe suivant :

A B

Étude des degrés :

 d(A) = 1
 d(B) = 2
 d(C) = 1
Analyse :
 Le graphe est connexe.

 Il possède exactement deux sommets de degré impair (A et C ).

Conclusion :
 Le graphe n'admet pas de cycle eulérien.

chemin eulérien.
 Il admet en revanche un

Un chemin eulérien possible est :

A→B→C

Interprétation :
 A est le sommet de départ

 C est le sommet d'arrivée

 chaque arête est parcourue exactement une fois

Comparaison avec les graphes hamiltoniens

Type Porte sur Condition principale
Graphe hamiltonien Sommets Visiter chaque sommet exactement une fois (cycle)

Graphe eulérien Arêtes Parcourir chaque arête exactement une fois (cycle)

Diérence fondamentale :
 Hamiltonien → sommets
contrainte sur les

 Eulérien → contrainte sur les arêtes

Remarque importante :
 Un graphe peut être hamiltonien sans être eulérien, et inversement.

 Les deux propriétés sont indépendantes.

33
Interprétation
Les graphes eulériens modélisent des situations où l'on cherche à parcourir chaque
liaison exactement une fois, sans répétition. On les retrouve notamment dans :
 les parcours de réseaux routiers (nettoyage, inspection ou maintenance de toutes les
routes une seule fois) ;

 le problème historique des ponts de Königsberg, à l'origine de la théorie des

graphes ;

 l'optimisation de tournées logistiques (distribution, collecte de courrier, ramassage

des déchets) ;

 certaines applications industrielles où chaque arête représente une tâche à exécuter

une seule fois.

Remarque :
 Le modèle eulérien est adapté lorsque l'intérêt porte sur les arêtes du réseau.
 Cela le distingue des problèmes hamiltoniens, où l'on s'intéresse aux sommets.

1.6 Graphes bipartis

Les graphes bipartis constituent une classe importante de graphes utilisée dans de
nombreuses applications telles que l'aectation de tâches, les réseaux sociaux et les pro-
blèmes de couplage.
L'idée fondamentale est de partitionner les sommets en deux ensembles distincts.

1.6.1 Dénition
Dénition 1.6.1. Un graphe biparti est un graphe dont l'ensemble des sommets peut
être partitionné en deux ensembles disjoints U et V tels que chaque arête relie un sommet
de U à un sommet de V .
Autrement dit,

U ∩V =∅
et aucune arête ne relie deux sommets appartenant au même ensemble.

1.6.2 Exemple
Considérons les ensembles

U = {u1 , u2 }, V = {v1 , v2 , v3 }.
Les arêtes sont

E = {u1 v1 , u1 v2 , u2 v2 , u2 v3 }.

34
 v1

u1

v2

u2

v3

Ce graphe est biparti car toutes les arêtes relient un sommet de U à un sommet de V.

1.6.3 Graphe biparti complet

Dénition 1.6.2. Un graphe biparti complet, noté K , est un graphe biparti dans
lequel chaque sommet du premier ensemble est relié à tous les sommets du second en-
m,n

semble.
Le nombre total d'arêtes est

|E| = m × n.
Par exemple,

K2,3
possède 2×3=6 arêtes.

1.6.4 Propriété fondamentale

Théorème 1.6.1. Un graphe est biparti si et seulement s'il ne contient aucun cycle de
longueur impaire.
Cette propriété fournit un moyen simple de vérier si un graphe est biparti.

1.6.5 Coloration des graphes bipartis

Un graphe biparti peut être colorié avec seulement deux couleurs :

χ(G) = 2
lorsqu'il possède au moins une arête.
On attribue une couleur à tous les sommets de U et une autre couleur à tous les
sommets de V.

1.6.6 Applications
Les graphes bipartis interviennent dans de nombreux domaines :

 Aectation de tâches à des machines ;

 Attribution d'étudiants à des projets ;

35
  Systèmes de recommandation ;

 Réseaux de communication ;

 Problèmes de couplage et d'optimisation.

1.6.7 Conclusion
Un graphe biparti est un graphe dont les sommets sont répartis en deux ensembles
disjoints. Il joue un rôle fondamental en théorie des graphes et en optimisation, notamment
grâce à ses propriétés de coloration et de couplage.

1.7 Théorie de la coloration

La théorie de la coloration est une branche de la théorie des graphes qui étudie l'at-
tribution de couleurs à certains éléments d'un graphe sous des contraintes données.
Le problème le plus classique est la coloration des sommets, où deux sommets
adjacents doivent recevoir des couleurs distinctes.

1.7.1 Dénition
Soit G = (V, E) un graphe simple, où V désigne l'ensemble des sommets et E l'en-
semble des arêtes.

Dénition 1.7.1. Une coloration propre des sommets d'un graphe G est une appli-
cation
c : V −→ 1, 2, . . . , k
telle que pour toute arête uv ∈ E,
c(u) ̸= c(v).

Les entiers 1, 2, . . . , k représentent les couleurs utilisées.

1.7.2 Nombre chromatique

Dénition 1.7.2. Le nombre chromatique d'un graphe G, noté χ(G), est le plus petit
entier k pour lequel il existe une coloration propre de G utilisant k couleurs.
Ainsi,

χ(G) = min k; |; G est k -coloriable.

1.7.3 Exemple : graphe chemin

Considérons le graphe chemin P3 :

v1 − v2 − v3 .
Une coloration possible est :

c(v1 ) = 1, c(v2 ) = 2, c(v3 ) = 1.

36
 Deux couleurs susent donc :

χ(P3 ) = 2.

1.7.4 Exemple : graphe complet

Le graphe complet à n sommets, noté Kn , possède une arête entre chaque paire de
sommets distincts.
Comme tous les sommets sont adjacents deux à deux, chacun doit recevoir une couleur
diérente. Ainsi,

χ(Kn ) = n.
En particulier,

χ(K3 ) = 3.

1.7.5 Théorème des quatre couleurs

Théorème 1.7.1 (Théorème des quatre couleurs). Tout graphe planaire peut être colorié
avec au plus quatre couleurs, c'est-à-dire que pour tout graphe planaire G,
χ(G) ≤ 4.

Ce théorème arme qu'il est toujours possible de colorier les régions d'une carte plane
avec au plus quatre couleurs de manière que deux régions adjacentes ne possèdent jamais
la même couleur.

1.7.6 Coloration des arêtes

La coloration peut également porter sur les arêtes du graphe.

Dénition 1.7.3. Une coloration propre des arêtes est une application
c : E −→ 1, 2, . . . , k

telle que deux arêtes adjacentes reçoivent des couleurs diérentes.

Le plus petit nombre de couleurs nécessaire est appelé indice chromatique du graphe
′
et est noté χ (G).

1.7.7 Applications
La théorie de la coloration intervient dans de nombreux domaines :

 Ordonnancement de tâches ;

 Planication d'emplois du temps ;

 Attribution de fréquences radio ;

 Conception de réseaux de communication ;

 Allocation de ressources en recherche opérationnelle.

37
1.7.8 Conclusion
La théorie de la coloration constitue un domaine fondamental de la théorie des graphes.
Elle fournit des outils puissants pour résoudre des problèmes d'optimisation et d'allocation
de ressources tout en donnant lieu à des résultats théoriques majeurs tels que le théorème
des quatre couleurs.

1.8 Matrices associées aux graphes

Les graphes peuvent être représentés sous forme matricielle. Cette représentation per-
met d'étudier leurs propriétés à l'aide d'outils algébriques et de concevoir des algorithmes
ecaces pour leur analyse. Parmi les matrices les plus utilisées gurent la matrice d'inci-
dence et la matrice des distances.

1.8.1 Matrice d'incidence

Soit G = (V, E) un graphe comportant n sommets et m arêtes.

Dénition 1.8.1. La matrice d'incidence d'un graphe G est la matrice

M = (mij )

de dimension n × m, dénie par

1 si le sommet v est incident à l'arête e ,
(

0 sinon.
i j
m = ij

Chaque ligne correspond à un sommet et chaque colonne à une arête.

1.8.2 Exemple
Considérons le graphe déni par

V = {A, B, C}

et
E = {e1 = AB, e2 = BC, e3 = AC}.

A B

La matrice d'incidence associée est

 
1 0 1
M = 1 1 0 .
0 1 1

Chaque colonne contient exactement deux coecients égaux à 1.

38
1.8.3 Matrice des distances
Dénition 1.8.2. La matrice des distances d'un graphe G est la matrice
D = (dij )

où d désigne la longueur du plus court chemin entre les sommets v et v .

ij i j

On a toujours :
dii = 0.

1.8.4 Exemple
Considérons le graphe chemin

A − B − C − D.

Les distances sont :

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

d(B, C) = 1, d(B, D) = 2, d(C, D) = 1.

La matrice des distances est
 
0 1 2 3
1 0 1 2
D=
2
.
1 0 1
3 2 1 0

Cette matrice est symétrique :

d(u, v) = d(v, u).

1.8.5 Applications
Les matrices associées aux graphes permettent :

 de représenter un graphe algébriquement ;

 d'étudier sa structure ;

 de calculer les plus courts chemins ;

 d'analyser les réseaux ;

 de développer des algorithmes ecaces.

1.8.6 Conclusion
Les matrices d'incidence et des distances sont des outils fondamentaux en théorie des
graphes, permettant une analyse mathématique et algorithmique des réseaux.

39
1.9 Arbres

Dénition 1.9.1. Un arbre est un graphe simple, non orienté, connexe et sans cycle.
Autrement dit :

 il existe un chemin entre toute paire de sommets ;

 le graphe ne contient aucun cycle.

1.9.1 Propriétés des arbres

Soit T un arbre ayant n sommets.

 T est connexe et sans cycle ;

 |E| = n − 1 ;
 entre deux sommets, il existe un unique chemin simple.

1.9.2 Exemple d'arbre

D
B
E
A

Ce graphe est un arbre car il est connexe et ne contient aucun cycle.

1.9.3 Caractérisation des arbres

Théorème 1.9.1. Un graphe à n sommets est un arbre si et seulement si :
 il est connexe et possède n − 1 arêtes;
 ou il est sans cycle et possède n − 1 arêtes.
1.10 Arbres couvrants minimaux

Soit un graphe connexe pondéré G = (V, E).

1.10.1 Dénition
Dénition 1.10.1. Un arbre couvrant minimal est un arbre couvrant tous les sommets
de G dont la somme des poids des arêtes est minimale.
Applications :
 réseaux de transport ;

 réseaux électriques ;

 réseaux informatiques.

40
1.11 Algorithme de Kruskal

1.11.1 Principe
L'algorithme de Kruskal construit un arbre couvrant minimal en ajoutant progressi-
vement les arêtes les moins coûteuses sans créer de cycle.

1.11.2 Étapes
1. Trier les arêtes par poids croissant ;

2. Initialiser une forêt (chaque sommet est un arbre) ;

3. Parcourir les arêtes dans l'ordre :

 ajouter l'arête si elle ne crée pas de cycle ;

 sinon la rejeter ;

4. Arrêter lorsque |V | − 1 arêtes sont sélectionnées.

1.11.3 Pseudo-code
 Trier E par poids croissant

 T ←∅
 Pour chaque arête e∈E :

 si T ∪ {e} ne contient pas de cycle, alors ajouter e

 Retourner T

1.12 Algorithme de Prim

1.12.1 Principe
L'algorithme de Prim construit un arbre couvrant minimal en partant d'un sommet
et en l'étendant progressivement.
À chaque étape, on ajoute l'arête de poids minimal reliant l'arbre à un sommet exté-
rieur.

1.12.2 Étapes
1. Choisir un sommet initial ;

2. Initialiser l'arbre avec ce sommet ;

3. Tant que tous les sommets ne sont pas inclus :

 choisir l'arête de poids minimal reliant l'arbre à un sommet extérieur ;

 ajouter l'arête et le sommet associé ;

41
1.12.3 Pseudo-code
 Choisir un sommet s
 T ← {s}
 Tant que T ̸= V :

 choisir (u, v) de poids minimal avec u ∈ T, v ∈

/T
 ajouter v à T

1.13 Comparaison

Kruskal Prim
Stratégie Globale (arêtes) Locale (extension)
Structure Forêt Arbre unique
Idéal pour Graphes clairsemés Graphes denses
Démarrage Sans racine Sommet initial

1.13.1 Conclusion
Les algorithmes de Kruskal et de Prim permettent de construire un arbre couvrant
minimal selon deux approches diérentes :

 Kruskal : sélection globale des arêtes les plus légères ;

 Prim : croissance progressive à partir d'un sommet.

1.14 Exemple de Kruskal

Considérons le graphe suivant :

B
1 4
A 2 D

3 5
C

1.14.1 Étapes de l'algorithme de Kruskal

Les arêtes sont triées par ordre croissant de poids :

AB(1), BC(2), AC(3), BD(4), CD(5).

On applique ensuite l'algorithme :

 Ajouter AB(1) ;
 Ajouter BC(2) ;
 Rejeter AC(3) (formation d'un cycle) ;

 Ajouter BD(4).

42
1.14.2 Arbre couvrant minimal
L'arbre couvrant minimal obtenu est :

T = {AB, BC, BD}.

1.15 Algorithme de Prim

1.15.1 Principe
L'algorithme de Prim construit un arbre couvrant minimal en partant d'un sommet
et en ajoutant progressivement les arêtes de poids minimal reliant l'arbre aux sommets
restants.

1.15.2 Application au même graphe

On part du sommet A.
 Étape 1 : choisir AB(1) ;
 Étape 2 : parmi les arêtes incidentes à {A, B}, choisir BC(2) ;
 Étape 3 : parmi les arêtes incidentes à {A, B, C}, choisir BD(4).

1.15.3 Arbre couvrant minimal

On obtient le même arbre :

T = {AB, BC, BD}.

1.16 Conclusion

Les algorithmes de Kruskal et de Prim permettent tous deux de déterminer un arbre

couvrant minimal.

 Kruskal : sélection globale des arêtes par ordre croissant ;

 Prim : croissance progressive à partir d'un sommet initial.

1.17 Tri topologique

Le tri topologique est un outil fondamental pour l'étude des graphes orientés sans
cycle (DAG).

1.17.1 Dénition
Un tri topologique d'un graphe orienté acyclique (DAG) est un ordre linéaire de ses
sommets tel que :
si u → v, alors u apparaît avant v.
Condition d'existence Un graphe admet un tri topologique si et seulement s'il est
sans cycle.

43
1.17.2 Algorithme de Kahn
Principe : on supprime progressivement les sommets de degré entrant nul.
1. Calculer les degrés entrants de tous les sommets.

2. Mettre dans une le les sommets de degré entrant nul.

3. Tant que la le n'est pas vide :

 extraire un sommet u;
 l'ajouter au résultat ;

 supprimer ses arêtes sortantes ;

 mettre à jour les degrés entrants.

1.17.3 Exemple : graphe initial

Considérons le graphe orienté suivant :

B D

C E

On cherche un tri topologique.

1.17.4 Étape 1 : degrés entrants

 deg(A) = 0
 deg(B) = 1
 deg(C) = 1
 deg(D) = 2
 deg(E) = 1
Seul A a un degré entrant nul.

1.17.5 Étape 2 : suppression de A

On supprime A et ses arêtes :

A → B, A→C
Nouveaux degrés entrants :

 B = 0, C = 0, D = 2, E = 1

1.17.6 Étape 3 : traitement de B et C

On traite B puis C.
Après suppression :

 D devient 0
 E devient 0

44
1.17.7 Étape 4 : traitement de D et E
On peut choisir :
D puis E ou E puis D

1.17.8 Résultat
Un tri topologique possible est :

A→B→C→D→E

Un autre ordre valide est :

A, C, B, E, D
Remarque Le tri topologique n'est pas unique.

1.17.9 Applications
 planication de tâches ;

 compilation de programmes ;

 gestion des dépendances ;

 ordonnancement.

1.17.10 Conclusion
Le tri topologique permet d'ordonner les sommets d'un graphe orienté acyclique en
respectant les relations de dépendance.

45