Année Universitaire © Cours de B.

HADDAR – ENET’COM
2024 - 2025 [email protected]
1
 Motivations
 La théorie des graphes permet de résoudre
efficacement une grande variété de problèmes
pratiques ou récréatifs en les ramenant à des
configurations qui se dessinent simplement à l’aide de
points et de liaisons entre ces points.

 S’ouvrir sur la théorie des graphes, c’est s’ouvrir à de

nouveaux raisonnements, c’est s’entraîner à avoir un
autre regard mathématique pour la résolution des
problèmes.

© Cours de B. HADDAR – ENET’COM – 2024/2025 2

 Motivations
 La théorie des graphes ouvre un grand champ de
modélisation conduisant à des solutions efficaces.
 Montrer comment l’utilisation judicieuse d’un graphe
peut rendre certains problèmes concrets accessibles à
un raisonnement mathématique.
Un bon dessin vaut mieux qu’un bon discours !
 Apprendre à représenter une situation à l’aide
d’un graphe en se posant d’abord les questions
suivantes: "quels objets vont être des sommets,
lesquels deviennent les arêtes ?".
© Cours de B. HADDAR – ENET’COM – 2024/2025 3
 Contenu du cours
 La modélisation d’une situation par un graphe orienté
ou non, éventuellement étiqueté ou pondéré et dont la
solution est associée à:

 La recherche de l’existence d’une chaîne ou d’un

cycle eulérien.
 La recherche du plus court chemin (chaine) dans
un graphe.
 La coloration d’un graphe.
 La recherche du nombre chromatique.
© Cours de B. HADDAR – ENET’COM – 2024/2025 4
 Contenu du cours
 À travers la maîtrise de quelques notions:
 L’ordre d’un graphe, le degré d’un sommet,
 Graphe simple, graphe complet, graphe connexe,
 Chaîne, longueur d’une chaîne, cycle,
 Théorème d’Euler, chaîne eulérienne, cycle
eulérien.
 Les arbres, l’arbre couvrant.
 Flots.
© Cours de B. HADDAR – ENET’COM – 2024/2025 5
 Utilité et applications
 Optimisation des réseaux de transport: transports routiers
ou transports d’information:
 Quel est le plus court chemin (en distance ou en temps) pour se
rendre d’une ville à une autre ?
 Peut-on mettre une rue en sens unique sans rendre impossible la
circulation en ville ?
 Conception de réseaux électriques, de réseaux de
communication
 Comment minimiser la longueur totale des connexions d’un
circuit ?
 Mécanique statistique, formules chimiques, informatique
théorique, sciences sociales, géographie, architecture...
© Cours de B. HADDAR – ENET’COM – 2024/2025 6
 Aperçu historique
 Le célèbre problème des sept ponts de Königsberg
(Actuellement Kaliningrad) (Euler, 1736):
 Partir d’une terre quelconque A, B, C, ou D et traverser chacun
des ponts une fois et une seule et revenir à son point de départ.

© Cours de B. HADDAR – ENET’COM – 2024/2025 7

 Aperçu historique
 Nous pouvons réduire chaque terre de Königsberg à un simple point
(que nous appellerons sommets ou nœud), connecté par des liens que
nous appellerons arêtes.
 Ce type de dessin est appelé un graphe.

 Le problème des Sept ponts de Königsberg peut maintenant se

formuler de la manière suivante : Peut-on trouver un "trajet" dans ce
graphe qui passe exactement une fois par chaque arête ?
© Cours de B. HADDAR – ENET’COM – 2024/2025 8
 Aperçu historique

 Ce problème est à première vue banal car il suffit de donner une telle
promenade pour affirmer l’existence d’une solution. Par contre,
montrer qu’il n’existe pas de tel parcours reste incertain sans l’aide
des mathématiques.
 Leonhard Euler, mathématicien bâlois, montra que c’était impossible
et fut amené pour cela à introduire les premiers rudiments de théorie
des graphes, dont celle de cycle eulérien qui va être définie ci-
dessous.
© Cours de B. HADDAR – ENET’COM – 2024/2025 9
© Cours de B. HADDAR – ENET’COM – 2024/2025 10
 Définition d’un graphe
Définition
Un graphe 𝐺 = ⟨𝑉, 𝐸⟩ est défini par un ensemble non vide de sommets 𝑉
et un ensemble d’arêtes 𝐸 ⊆ 𝑉 × 𝑉 . Une arête de G étant une paire de
sommets de 𝐺. Le cardinal |𝑉| est appelé ordre du graphe.
Exemple

sommet isolé

© Cours de B. HADDAR – ENET’COM – 2024/2025 11

 Exemples de graphes

Le graphe d’un tournoi 𝐺 = (𝑉, 𝐸) où :

𝑉 est l’ensemble des participants au tournoi,
𝐸 est l’ensembles des paires de joueurs se rencontrant dans le
tournoi.

La carte routière de la Tunisie

𝑉 est l’ensembles des villes de la Tunisie,
E = {{𝑥 , 𝑦}/ il y a au moins une route directe reliant les
villes 𝑥 et 𝑦}

© Cours de B. HADDAR – ENET’COM – 2024/2025 12

 Graphe Simple
Définition
Un graphe simple est un graphe qui ne possède ni boucle ni
arêtes multiples.
Exemples

© Cours de B. HADDAR – ENET’COM – 2024/2025 13

 Adjacence des sommets et des arêtes
Définitions
 Deux sommets sont adjacents s’ils sont connectés par, au moins, une
arête.
 Deux arêtes sont adjacentes si elles ont une extrémité commune.
Exemple A C
B

D F
E
 Le sommet A est adjacent aux sommets B, C et D; mais n’est pas
adjacent à E ou F.
 Les arêtes (A, B) et (B, E) sont adjacentes car elles ont une extrémité
commune qui est le sommet B.
© Cours de B. HADDAR – ENET’COM – 2024/2025 14
.
 Degré des sommets
Définition
Le degré d’un sommet 𝑣 est le nombre d’arêtes ayant comme extrémité
ce sommet, noté 𝑑 𝑣 .
Lorsque 𝑑(𝑣) = 0, on dit que 𝑣 est un sommet isolé, lorsque 𝑑(𝑣) = 1,
le sommet 𝑣 est dit pendant.
A C
Exemple B

D F
E

Les sommets A, B, C et E sont adjacents et ont un degré égale à

3. Les sommets D et F sont de degré 2.
.
© Cours de B. HADDAR – ENET’COM – 2024/2025 15
 Degré des sommets
La somme des degrés est le nombre d’extrémités des arêtes.
Théorèmes
 La somme des degrés des sommets d’un graphe est un nombre pair.
 Le nombre de sommets de degré impair est un nombre pair.

Propriété
Pour tout graphe 𝐺 = 𝑉, 𝐸 :

෍ 𝑑 𝑣 = 2|𝐸|
Preuve 𝑣∈𝑉

Il suffit de voir que chaque arête relie deux sommets du graphe 𝐺, et donc
qu’elle est comptée exactement deux fois dans la somme.
© Cours de B. HADDAR – ENET’COM – 2024/2025 16
 Degré des sommets
Définition
 Une boucle est une arête qui relie un sommet à lui même.
 Un graphe est dit simple, s’il ne contient pas de boucles et s’il n’y a
pas plus d’une arête reliant deux mêmes sommets.
Remarque
Remarquez que l’on compte les extrémités, ainsi une boucle augmente de
2 le degré du sommet considéré.
Exemple

Le sommet rouge a un degré égal à 8.

© Cours de B. HADDAR – ENET’COM – 2024/2025 17
 Degré d’un graphe
Définitions
 Le degré d’un graphe est le degré maximal de tous ses sommets.
 Une suite décroissante (au sens large) d’entiers est graphique s’il
existe un graphe simple dont les degrés des sommets
correspondent à cette suite (par exemple, le triangle à trois sommets
correspond à la suite 2, 2, 2).
Exemple
Ces deux graphes distincts correspondant à la suite (4, 3, 3, 2, 2).

© Cours de B. HADDAR – ENET’COM – 2024/2025 18

 Degré d’un graphe
Exercice
Déterminer ceux qui sont successible de décrire une même situation.

a) b) g) h)

c) d)

i) j)

e) f)

© Cours de B. HADDAR – ENET’COM – 2024/2025 19

 Degré d’un graphe
Solution de l’exercice
Les graphes successible de décrire une même situation sont:
a) b) g) h)

6/// 2,2,2,2,2,2 7/// 2,2,2,2,2,2,2,

5/// 3,3,3,3,2 5/// 3,3,3,3,2
c) d)

i) j)
6/// 2,2,2,2,2,2 6/// 2,2,2,2,2,2

e) f)
5/// 4,3,3,2,2 5/// 3,3,2,2,2

5/// 2,2,2,2,2 5/// 4,3,3,2,2

© Cours de B. HADDAR – ENET’COM – 2024/2025 20

 Graphe complet
Définition
Un graphe complet 𝐾𝑛 avec 𝑛 sommets est un graphe dans lequel
chaque sommet est relié à tous les autres (avec une arête entre chaque
paire de sommets).
Exemple
Voici les cinq premiers graphes complets

𝒏(𝒏−𝟏)
Dans un graphe complet 𝑲𝒏 , le nombre d’arêtes est égal à
𝟐
© Cours de B. HADDAR – ENET’COM – 2024/2025 21
 Graphe connexe
Définition
Un graphe est connexe s’il existe une chaîne reliant une paire de
sommets 𝑖 et 𝑗 quelconques (s’il est possible à partir de n’importe quel
sommet, de rejoindre tous les autres en suivant les arêtes).

Exemple

Graphe connexe
Graphe non connexe
Ce graphe est non connexe malgré qu’il est
constitué de deux composantes connexes séparées.
© Cours de B. HADDAR – ENET’COM – 2024/2025 22
 Chaînes
Définitions

 Une chaîne dans 𝐺 est une suite de la forme

(𝑣0 , 𝑒1 , 𝑣1 , 𝑒2 , . . . , 𝑣𝑘−1 , 𝑒𝑘 , 𝑣𝑘 ) ayant pour éléments alternativement
des sommets (𝑣𝑖 ) et des arêtes (𝑒𝑖 ), commençant et se terminant par un
sommet, et telle que les extrémités de 𝑒𝑖 soient 𝑣𝑖−1 et 𝑣𝑖 , 𝑖 = 1, . . . , 𝑘.
 Par convention, on impose à toute chaîne de contenir au moins
une arête.
 La longueur d’une chaîne est le nombre d’arêtes qui la composent.
 Une chaîne est dite fermée si son origine et son extrémité sont
confondus.

© Cours de B. HADDAR – ENET’COM – 2024/2025 23

 Chaînes

 Le graphe ci-contre contient, par exemple, les

deux chaînes suivante: (𝑣1 , 𝑒3 , 𝑣3 , 𝑒4 , 𝑣4 ) et
𝑣4 , 𝑒4 , 𝑣3 , 𝑒2 , 𝑣2 , 𝑒1 , 𝑣1 .

Remarque
 On ne change pas une chaîne en inversant l’ordre des éléments dans la
suite correspondante, ainsi les chaînes (𝑣1 , 𝑒3 , 𝑣3 , 𝑒4 , 𝑣4 ) et
(𝑣4 , 𝑒4 , 𝑣3 , 𝑒3 , 𝑣1 ) sont identiques.
 On appelle distance entre deux sommets la longueur de la plus petite
chaîne les reliant.
 On appelle diamètre d’un graphe la plus longue des distances entre
deux sommets.
© Cours de B. HADDAR – ENET’COM – 2024/2025 24
 Chaînes
Définitions
 Une chaîne élémentaire est une chaîne ne passant pas deux fois par
un même sommet, c’est-à-dire dont tous les sommets sont distincts.
 Une chaîne simple est une chaîne ne passant pas deux fois par une
même arête, c’est-à-dire dont toutes les arêtes sont distinctes.
 Une chaîne telle que 𝑣0 = 𝑣𝑘 (si son origine et son extrémité sont
Confondus) est appelée chaîne fermée.
 Pour un graphe simple d’ordre 𝑛 , le degré d’un sommet est un entier
compris entre 0 et 𝑛 − 1.

Exemple
 La chaine fghedb est une chaîne simple.

© Cours de B. HADDAR – ENET’COM – 2024/2025 25

 Cycles
Définition
 Une chaîne fermée simple est appelée cycle si seul le sommet de
départ apparaît deux fois dans la chaîne.
Remarque
 Ainsi une boucle est un cycle de longueur 1.

Exemple
 FABCF est un cycle (chaîne fermée).
 FEBD est une chaîne simple.

© Cours de B. HADDAR – ENET’COM – 2024/2025 26

 Graphes eulériens
Définitions
 Chaîne eulérienne: chaîne simple passant par toutes les arêtes d’un
graphe une et une seule fois (sans l’obligation de finir au point par
lequel on a commencé).
 Cycle eulérien: cycle simple passant par toutes les arêtes d’un graphe
une et une seule fois et finissant à son point de départ.
 Graphe eulérien: graphe qui possède un cycle eulérien.
 Graphe semi-eulérien : graphe qui possède une chaîne eulérienne.
 Plus simplement, on peut dire qu’un graphe est eulérien (ou semi-
eulérien) s’il est possible de dessiner le graphe sans lever le crayon (et
sans passer deux fois sur le même trait!).
© Cours de B. HADDAR – ENET’COM – 2024/2025 27
 Graphes eulériens
Théorème d’Euler (1766)

 Un graphe simple connexe 𝐺 = (𝑉, 𝐸) est eulérien (c’est-à-dire

Admet un cycle eulérien) si et seulement si tous ses sommets sont
de degré pair.

Théorème

 Un graphe simple connexe 𝐺 = (𝑉, 𝐸) est semi-eulérien (c’est-à-dire

Admet une chaîne eulérienne) si et seulement si il admet 0 ou
exactement 2 sommets de degré impair.

© Cours de B. HADDAR – ENET’COM – 2024/2025 28

 Graphes eulériens
Exercice
Les graphes ci-dessous sont-ils eulériens (ou semi-eulériens) ? Si oui
proposer une chaine eulérienne.

© Cours de B. HADDAR – ENET’COM – 2024/2025 29

 Graphes eulériens
Solution de l’exercice
Les graphes ci-dessous sont-ils eulériens (ou semi-eulériens) ? Si oui
proposer une chaine eulérienne.

© Cours de B. HADDAR – ENET’COM – 2024/2025 30

 Graphe hamiltonien
Définitions
 On dit qu’un graphe est hamiltonien s’il est possible de trouver un
cycle passant une et une seule fois par tous les sommets.
 On dit qu’un graphe est semi-hamiltonien s’il est possible de trouver
une chaîne passant une et une seule fois par tous les sommets.
 Contrairement aux graphes eulériens, il n’existe pas de caractérisation
simple des graphes hamiltoniens ou semi-hamiltoniens.
Propriétés
 Un graphe possédant un sommet de degré 1 ne peut pas être
hamiltonien.
 Si un sommet dans un graphe est de degré 2, alors les deux arêtes
incidentes à ce sommet doivent faire partie du cycle hamiltonien.
 Les graphes complets 𝐾𝑛 sont hamiltoniens.
© Cours de B. HADDAR – ENET’COM – 2024/2025 31
 Graphe hamiltonien
Théorème

Soit 𝐺 = ⟨ 𝑉, 𝐸 ⟩ un graphe simple d’ordre 𝒏 ≥ 𝟑. Si pour toute paire

𝑢, 𝑣 de sommets non adjacents, on a 𝒅(𝒖) + 𝒅(𝒗) ≥ 𝒏, alors 𝐺 est
hamiltonien.

Corollaire

Soit 𝐺 = ⟨ 𝑉, 𝐸 ⟩ un graphe simple d’ordre 𝒏 ≥ 𝟑. Si pour tout

sommet 𝑢 de 𝑉, on a 𝒅(𝒖) ≥ 𝒏/𝟐, alors 𝐺 est hamiltonien.

© Cours de B. HADDAR – ENET’COM – 2024/2025 32

 Graphe hamiltonien
Remarque
Si la condition n’est pas vérifiée dans le théorème ou le corollaire, cela
ne signifie pas nécessairement que le graphe est non hamiltonien.

Exemple
Le graphe suivant ne vérifie pas le théorème car
𝑑 𝐴 + 𝑑 𝐻 < 𝑛.
Le graphe suivant ne vérifie pas le corollaire
car 𝑑(𝐴) < 𝑛/2. de même pour 𝐻.

Le graphe est hamiltonien car nous pouvons trouver un cycle où

nous pouvons visiter chaque sommet une et une seule fois tel que :
A-F-D-G-H-C-E-B-A
© Cours de B. HADDAR – ENET’COM – 2024/2025 33
 Graphe hamiltonien
Exemples

Le graphe ci-contre est hamiltonien car il admet au

moins un cycle hamiltonien : (1 – 2 – 3 – 4).
En voilà un autre : (3 – 2 – 1 – 4).
Remarquez que dans chaque cas, l’arête (1, 3) n’est
pas empruntée.

Le graphe ci-contre est semi-hamiltonien : il ne

comporte aucun cycle hamiltonien, par contre les
chaînes (1 – 5 – 6 – 3 – 2 – 4) et (1 – 2 – 3 – 6 – 5 – 4)
forment des chaines hamiltoniennes.
Remarquez qu’aucune chaîne hamiltonienne ne part
de 5 ou de 2.

© Cours de B. HADDAR – ENET’COM – 2024/2025 34

 Stable
Définitions
 Un stable, appelé aussi ensemble indépendant, est un sous-ensemble
de sommets (sous-graphe) deux à deux non adjacents (ne sont reliés
par aucune arête).
 La taille d’un stable est égale au nombre de sommets qu’il contient.
 Un ensemble stable maximum est un ensemble stable de cardinalité
maximale.
 Le cardinal du plus grand stable est noté 𝜶(𝑮).

Exemple
Les sous-graphes {1, 6}, {1, 5} et {2, 6} sont des
stables pour le graphe ci-contre.

© Cours de B. HADDAR – ENET’COM – 2024/2025 35

 Clique
Définitions
 Un sous-graphe est une clique si tous ses sommets sont reliés les uns
aux autres par une arête. Autrement dit, une clique est un sous-graphe
complet.

 Le cardinal de la plus grande clique est noté 𝝎(𝑮).

Exemple

Les sous-graphes {1, 2, 3}, {2, 3, 4, 5}, {2, 4, 5},

{2, 3, 4} sont des exemples de cliques pour le
graphe ci-contre. Il existe d’autre cliques dans ce
graphe.

© Cours de B. HADDAR – ENET’COM – 2024/2025 36

 Matrice d’adjacence
Définition
La matrice d’adjacence associée à un graphe 𝐺 d’ordre 𝑛 est la matrice
carrée 𝑀 de dimension 𝑛 × 𝑛, dont l’élément 𝑀𝑖,𝑗 est égal au nombre
d’arêtes reliant les sommets 𝑖 et 𝑗 et si les sommets 𝑖 et 𝑗 ne sont pas
adjacents, alors 𝑀𝑖,𝑗 = 0.

Exemple

© Cours de B. HADDAR – ENET’COM – 2024/2025 37

 Matrice d’adjacence
Exemple 1

Exemple 2

© Cours de B. HADDAR – ENET’COM – 2024/2025 38

 Matrice d’adjacence
Définitions
 La distance entre deux sommets distincts est la longueur de la plus
courte chaîne joignant ces deux sommets.
 Le diamètre d’un graphe est la plus grande des distances entre deux
sommets du graphe.
Théorème
La distance entre deux sommets distincts est le plus petit entier
naturel 𝒏 (𝒏 > 𝟎) tel que le terme d’indice 𝒊, 𝒋 de la matrice 𝑀𝑛 est
non nul.
Le nombre de chaînes de longueur 𝒏 est la trace de 𝑴𝒏 (la somme
des éléments de la diagonale), notée 𝒕𝒓(𝑴𝒏 ).
© Cours de B. HADDAR – ENET’COM – 2024/2025 39
 Matrice d’adjacence
Exercice
B C
A
Soit le graphe 𝐺 ci-contre.
1) Donner la matrice 𝑀 associée à 𝐺 en écrivant
les sommets dans l’ordre alphabétique. F D
E
2) On a calculé les matrice 𝑀2 et 𝑀5 suivantes:

a) Déduire le nombre de chaînes de longueurs 2 liant 𝐴 et 𝐷. Les écrire.

b) Déterminer le nombre de chaînes de longueur 5 reliant B et F.
© Cours de B. HADDAR – ENET’COM – 2024/2025 40
 Matrice d’adjacence
Solution de l’exercice
Soit le graphe 𝐺 ci-contre.
1) La matrice 𝑀 associée à 𝐺 en écrivant les sommets dans l’ordre
alphabétique est la suivante :

A B C

D
F
E

© Cours de B. HADDAR – ENET’COM – 2024/2025 41

 Matrice d’adjacence
Solution de l’exercice
2) On a calculé les matrice 𝑀2 et 𝑀5 suivantes:

a) En déduire le nombre de chaînes de longueur 2 liant 𝐴 et 𝐷. Les écrire.

Une seule chaîne (voir 𝑴𝟐 𝑨,𝑫). La chaîne est : A-B-D.

b) Déterminer le nombre de chaînes de longueur 5 reliant B et F.

Le nombre de chaînes de longueur 5 reliant B et F est 26 (voir 𝑴𝟓 𝑨,𝑫).

© Cours de B. HADDAR – ENET’COM – 2024/2025 42
 Graphes bipartites
Définition

 Un graphe bipartite (ou biparti) est 𝑿 𝒀

un graphe non orienté tel que

l’ensemble des sommets peut être
partitionné en deux sous-ensembles
disjoints 𝑋 et 𝑌 tels que chaque arête
du graphe a la forme {𝑥, 𝑦}, avec 𝑥 ∈
𝑋 et 𝑦 ∈ 𝑌. Exemple de graphe
biparti complet

© Cours de B. HADDAR – ENET’COM – 2024/2025 43

 Graphes bipartites
Exemple d’application

 Trois professeurs 𝑃1, 𝑃2, 𝑃3 devront donner lundi prochain un certain

nombre d’heures de cours à trois classes 𝐶1, 𝐶2, 𝐶3. 𝑃1 doit donner 2
heures de cours à 𝐶1 et 1 heure à 𝐶2 ; 𝑃2 doit donner 1 heure de
cours à 𝐶1, 1 heure à 𝐶2 et 1 heure à 𝐶3 ; 𝑃3 doit donner 1 heure de
cours à 𝐶1, 1 heure à 𝐶2 et 2 heures à 𝐶3.

Modéliser cette situation par graphe.

© Cours de B. HADDAR – ENET’COM – 2024/2025 44

 Graphes bipartites
Exemple d’application

 Graphe biparti construit avec les nœuds sont les professeurs et les
cours. Les arêtes (relation symétrique) sont les cours donnés par un
professeur. On obtient le graphe biparti suivant :

© Cours de B. HADDAR – ENET’COM – 2024/2025 45

 Graphes planaires
Définition

 Un graphe est dit planaire s’il peut être dessiné dans le plan sans
croisement d’arcs ou d’arêtes. Par exemple, le graphe complet 𝐾4
peut être dessiné des deux manières données ci-dessous.
 Comme le graphe de droite ne contient pas de croisement, 𝐾4 est
planaire.

Exemple

© Cours de B. HADDAR – ENET’COM – 2024/2025 46

 Graphes planaires
 Un graphe planaire divise le plan en régions
internes et une région externe. Dans le
graphe ci-contre, les régions internes sont 𝐴, 𝐵
et 𝐶 et la région externe est 𝐷.

Théorème

 Pour tout graphe planaire connexe avec 𝑠 sommets, 𝑎 arêtes et 𝑟

régions, 𝒓 = 𝒂 − 𝒔 + 𝟐.
Par exemple, pour le graphe ci-dessus, 𝑟 = 4, 𝑎 = 6 et 𝑠 = 4.
© Cours de B. HADDAR – ENET’COM – 2024/2025 47
 Graphes planaires
Exemple d’application

 Considérons un problème très classique : trois maisons doivent être

reliées a trois fournisseurs (eau, gaz, électricité). Cela peut-il se faire
sans croisement?

© Cours de B. HADDAR – ENET’COM – 2024/2025 48

 Graphes planaires
Exemple d’application

 Vous réalisez que la question posée est : "le graphe ci-dessous est-il
planaire?"

 Ce graphe est suffisamment important pour porter un nom: on

l'appelle 𝐾3,3 (cela signifie qu'il possède trois sommets, chacun
d'entre eux étant connecté à un autre ensemble de trois sommets).
© Cours de B. HADDAR – ENET’COM – 2024/2025 49
© Cours de B. HADDAR – ENET’COM – 2024/2025 50
 Graphe orienté
Définitions
 Un graphe orienté 𝐺 est la donnée d’un
couple 𝐺 = 𝑉, 𝐴 où 𝑉 = {𝑣1 , 𝑣2 , … , 𝑣𝑛 }
est un ensemble fini dont les éléments sont
appelés sommets et un ensemble A =
{𝑎1 , 𝑎2 , … , 𝑎𝑝 }partie du produit cartésien
𝑉 × 𝑉 dont les éléments sont appelés arcs.
 Si 𝑎 = (𝑥, 𝑦) est un arc du graphe 𝐺, 𝑥 est
l’extrémité initiale (ou origine de 𝑎) et 𝑦
est l’extrémité finale (ou destination) de 𝑎. Graphe orienté

 Un arc (𝑥 , 𝑥) est appelé une boucle.

© Cours de B. HADDAR – ENET’COM – 2024/2025 51

 Degré d’un sommet
Définition

Soit 𝑥 un sommet d’un graphe orienté:

 On note 𝒅+ (𝒙) (le demi-degré extérieur

de 𝑥) le nombre d’arcs ayant 𝑥 comme
extrémité initiale.

 On note 𝒅− (𝒙) (le demi-degré intérieur

de 𝑥) le nombre d’arcs ayant 𝑥 comme Dans le graphe ci-dessus,
extrémité finale. on a:
d(A)=4
 d 𝒙 = 𝒅+ (𝒙) + 𝒅− (𝒙) 𝒅+ 𝑨 = 𝟐
𝒅− 𝑨 = 𝟐.
© Cours de B. HADDAR – ENET’COM – 2024/2025 52
 Chemin et circuit
Définitions
 Un chemin (ou chaine orientée) est une
suite de sommets 𝑐 = 𝑣1 , 𝑣2 , … , 𝑣𝑛 telle
que ∀ 𝑖 ∈ {1, … , 𝑛 − 1} (𝑣𝑖 , 𝑣𝑖+1 ) ∈ 𝐴.
 On appelle distance entre deux sommets
d’un graphe orienté la longueur du plus
petit chemin les reliant.
 S’il n’existe pas de chemins entre les
sommets 𝑥 et 𝑦, on pose 𝑑 𝑥, 𝑦 = ∞. Ici d(1, 3)=2 ; d(1, 4)=2 ;

 Un circuit (ou cycle orienté) est un chemin d(5, 2)=∞

fermé simple (𝑣1 = 𝑣𝑛 ).
© Cours de B. HADDAR – ENET’COM – 2024/2025 53
 Graphe orienté eulérien
Définitions
 Un chemin est dit eulérien s’il passe une fois et une seule par
chaque arc.
 Un graphe orienté est dit eulérien s’il admet un cycle orienté
eulérien.
Exemple

Dans ce graphe, le chemin formé des

arcs a – b – c – d – e – f – g est un chemin
eulérien de longueur 7.

© Cours de B. HADDAR – ENET’COM – 2024/2025 54

 Graphe orienté eulérien
Théorèmes
Soit 𝐺 un graphe connexe orienté:
 𝐺 admet un cycle orienté eulérien si et seulement si pour tout
sommet 𝑥 de 𝐺, on a 𝒅+ 𝒙 = 𝒅− 𝒙 .
 G admet une chaîne orientée eulérienne qui n’est pas un cycle si et
seulement si pour tout sommet 𝑥 de 𝐺, on a 𝒅+ 𝒙 = 𝒅− 𝒙 , sauf
pour deux sommets exactement (𝑎 et 𝑏) on a 𝒅+ 𝒂 = 𝒅− 𝒂 + 𝟏 et
𝒅+ 𝒃 = 𝒅− 𝒃 − 𝟏.

Admet un cycle Admet une chaîne N’admet ni cycle ni chaîne

© Cours de B. HADDAR – ENET’COM – 2024/2025 55
 Matrice d’adjacence
Définition
Soit 𝐺 = 𝑉 , 𝐴 un graphe orienté, avec 𝑉 = {𝑣1 , 𝑣2 , … , 𝑣𝑛 } . La
matrice d’adjacence du graphe est la matrice 𝑴(𝑮) dont les
𝟏, 𝒔𝒊 𝑣𝑖 , 𝑣𝑗 ∈ 𝑨
coefficients (𝑚𝑖,𝑗 ) sont définis par : 𝒎𝒊,𝒋 = ቐ
𝟎, 𝒔𝒊 𝑣𝑖 , 𝑣𝑗 ∉ 𝑨

Exemple

© Cours de B. HADDAR – ENET’COM – 2024/2025 56

 Matrice d’adjacence
Propriétés

Avec les notations précédentes, nous avons les propriétés immédiates

suivantes :

 La somme des éléments de la ième ligne de 𝑀 est égale au degré

sortant 𝑑+ 𝒙𝒊 du sommet 𝒙𝒊 de G: 𝒅+ 𝒙𝒊 = σ𝒋=𝟏 𝒎𝒊,𝒋 .

 La somme des éléments de la jème colonne de 𝑀 est égale au degré

entrant 𝑑− 𝒙𝒊 du sommet 𝒙𝒊 de G: 𝒅− 𝒙𝒊 = σ𝒋=𝟏. 𝒎𝒋,𝒊 .

 σ𝒊𝒋 𝒎𝒋,𝒊 = σ𝒊=𝟏 𝒅+ 𝒙𝒊 = σ𝒊=𝟏 𝒅− 𝒙𝒊 = 𝑨 .

 𝑀 est symétrique si et seulement si 𝐺 est symétrique

© Cours de B. HADDAR – ENET’COM – 2024/2025 57
 Matrice d’adjacence
Définitions
 La distance entre deux sommets distincts est la longueur du plus
court chemin joignant ces deux sommets.
 Le diamètre d’un graphe est la plus grande des distances entre deux
sommets du graphe.
Théorème
La distance entre deux sommets distincts est le plus petit entier
naturel 𝒏 (𝒏 > 𝟎) tel que le terme d’indice 𝒊, 𝒋 de la matrice 𝑀𝑛 est
non nul.
Le nombre de circuits de longueur 𝒏 est la trace de 𝑴𝒏 (la somme
des éléments de la diagonale), notée 𝒕𝒓(𝑴𝒏 ).
© Cours de B. HADDAR – ENET’COM – 2024/2025 58
 Matrice d’adjacence
Exemple
 Donner le nombre de chaînes orientées de longueur minimale pour
aller de 𝐷 à 𝐸 ?

© Cours de B. HADDAR – ENET’COM – 2024/2025 59

 Matrice d’adjacence
Exemple
 Donner le nombre de chaînes orientées de longueur minimale pour
aller de 𝐷 à 𝐸 ?

La langueur minimale des chaînes séparant D et E est 5 car seulement pour 𝑴𝟓 on

a 𝑴𝟓 𝑫, 𝑬 > 𝟎. Il existe une seule chaîne (𝑴𝟓 𝑫, 𝑬 = 𝟏).
Remarque: Le nombre de circuits de longueur 5 est la trace de 𝑴𝟓 , 𝒕𝒓(𝑴𝟓 ) = 𝟓.
© Cours de B. HADDAR – ENET’COM – 2024/2025 60
 Matrice d’incidence
Définition
Soit 𝐺 = 𝑉 , 𝐴 un graphe orienté sans boucle, avec 𝑉 =
{𝑣1 , 𝑣2 , … , 𝑣𝑛 } et 𝐴 = {𝑎1 , 𝑎2 , … , 𝑎𝑚 }. On appelle matrice d’incidence
(aux arcs) de 𝐺 la matrice 𝑴(𝑮) dont les coefficients (𝑚𝑖𝑗 ) sont définis
−𝟏, 𝒔𝒊 𝒍′ 𝒂𝒓𝒄 𝒂𝒋 𝒔𝒐𝒓𝒕 𝒅𝒖 𝒔𝒐𝒎𝒎𝒆𝒕 𝒗𝒊
par : 𝒎𝒊𝒋 = ൞𝟏, 𝒔𝒊 𝒍′ 𝒂𝒓𝒄 𝒂𝒋 𝒆𝒏𝒕𝒓𝒆 𝒅𝒂𝒏𝒔 𝒍𝒆 𝒔𝒐𝒎𝒎𝒆𝒕 𝒗𝒊
𝟎, 𝒔𝒊 𝒗𝒊 𝒏′ 𝒆𝒔𝒕 𝒑𝒂𝒔 𝒖𝒏𝒆 𝒆𝒙𝒕é𝒎𝒊𝒕é 𝒅𝒆 𝒂𝒋
Exemple

© Cours de B. HADDAR – ENET’COM – 2024/2025 61