LF 2 IMM

Année Universitaire © Cours de B. RABHI– ISSAT Kasserine

2019 - 2020 [email protected]
© Cours de B. Rabhi – ISSAT 1
Kasserine – 2019/2020
 Motivations
 La théorie des permet de
efficacement graphes une variété résoudre de
pratiques ou récréatifsgrande problèmes
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. Rabhi– ISSATKasserine – 2019/2020 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. Rabhi– ISSATKasserine – 2019/2020 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. Rabhi– ISSATKasserine – 2019/2020 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, eulérienne,
chaîne eulérien. cycle
 Les arbres, l’arbre couvrant.
 Flots.
©Cours de B. Rabhi– ISSATKasserine – 2019/2020 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. Rabhi– ISSATKasserine – 2019/2020 6
 Aperçu historique
 Le célèbre problème des sept ponts de
(Actuellement Kaliningrad) (Euler, 1736):
Königsberg
 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. Rabhi– ISSATKasserine – 2019/2020 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. Rabhi– ISSATKasserine – 2019/2020 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. Rabhi– ISSATKasserine – 2019/2020 9
©Cours de B. Rabhi– ISSATKasserine – 2019/2020 10
 Définition d’un
Définition
graphe
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. Rabhi– ISSATKasserine – 2019/2020 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. Rabhi– ISSATKasserine – 2019/2020 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. Rabhi– ISSATKasserine – 2019/2020 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é
©Cours de B. Rabhi– ISSATKasserine – 2019/2020
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

à
©Cours de B. Rabhi– ISSATKasserine – 2019/2020
15
 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 à

©Cours8.
de B. Rabhi– ISSATKasserine – 2019/2020
16
 Degré d’un
Définitions graphe
 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. Rabhi– ISSATKasserine – 2019/2020

17
 Degré d’un
Exercice graphe
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. Rabhi– ISSATKasserine – 2019/2020 18

 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. Rabhi– ISSATKasserine – 2019/2020 19

 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. Rabhi– ISSATKasserine – 2019/2020 20
 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
©Cours de B. Rabhi– ISSATKasserine – 2019/2020 constitué de deux composantes connexes séparées. 21
 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. Rabhi– ISSATKasserine – 2019/2020 22
 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
©Cours de B. Rabhi– ISSATKasserine – 2019/2020 23
deux sommets.
 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. Rabhi– ISSATKasserine – 2019/2020 24

 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. Rabhi– ISSATKasserine – 2019/2020 25

 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. Rabhi– ISSATKasserine – 2019/2020 26
 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. Rabhi– ISSATKasserine – 2019/2020 27

 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. Rabhi– ISSATKasserine – 2019/2020 28

 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. Rabhi– ISSATKasserine – 2019/2020 29

 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
 Ungraphe 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. Rabhi– ISSATKasserine – 2019/2020 30
 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. Rabhi– ISSATKasserine – 2019/2020 31
 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. Rabhi– ISSATKasserine – 2019/2020 32

 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. Rabhi– ISSATKasserine – 2019/2020 33
 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. Rabhi– ISSATKasserine – 2019/2020 34

 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. Rabhi– ISSATKasserine – 2019/2020 35

 Matrice
d’adjacence
Exemple 1

Exemple 2

©Cours de B. Rabhi– ISSATKasserine – 2019/2020 36

 Matrice
Définitions d’adjacence
 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. Rabhi– ISSATKasserine – 2019/2020 37
 Matrice
Exercice
d’adjacence
B C
Soit le graphe 𝐺 ci- A
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. Rabhi– ISSATKasserine – 2019/2020 38
 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. Rabhi– ISSATKasserine – 2019/2020 39

 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

𝑴B.Rabhi
©Cours de
𝟓
𝑫 ).Kasserine – 2019/2020
𝑨 –,ISSAT 40
 Graphes bipartites
Définition

 Un graphe bipartite (ou biparti) � 𝒀

est �
un graphe non tel
orienté que
l’ensemble des sommets
peut
partitionné en deux sous-ensembles
être
disjoints 𝑋 et 𝑌 tels que chaque arête
du graphe a la forme { 𝑥, 𝑦+ ,
avec Exemple de graphe
biparti complet
𝑥 ∈ 𝑋 et 𝑦 ∈ 𝑌.
©Cours de B. Rabhi– ISSATKasserine – 2019/2020 41
 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. Rabhi– ISSATKasserine – 2019/2020 42

 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. Rabhi– ISSATKasserine – 2019/2020 43

 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. Rabhi– ISSATKasserine – 2019/2020 44

 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, 𝒓 = 𝒂 − 𝒔 + 𝟐.
©Cours de B. Rabhi– ISSATKasserine – 2019/2020
Par exemple, pour le graphe ci-dessus, 𝑟 = 45
 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. Rabhi– ISSATKasserine – 2019/2020 46

 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. Rabhi– ISSATKasserine – 2019/2020 47
©Cours de B. Rabhi– ISSATKasserine – 2019/2020 48
 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 et un
sommets partie ensemble
A = *𝑎1, 𝑉
cartésien 𝑎2×
,…𝑉 ,dont élémentsdu sont
𝑎𝑝+
appelés produit
arcs.
 Si 𝑎 = (𝑥, 𝑦) est un arc du graphe 𝐺, 𝑥 est Graphe orienté
l’extrémité initiale (ou origine de 𝑎) et 𝑦
est l’extrémité finale (ou destination) de 𝑎.
 Un arc (𝑥 , 𝑥) est appelé une boucle.
©Cours de B. Rabhi– ISSATKasserine – 2019/2020 49
 Degré d’un
Définition
sommet
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. Rabhi– ISSATKasserine – 2019/2020 𝒅− 𝟐. 50
 Chemin et circuit
Définitions
 Un chemin (ou chaine orientée) est une
suite de sommets 𝑐 = 𝑣1, 𝑣2, … , 𝑣𝑛 telle
que ∀ 𝑖∈ *1, … , 𝑛 − 1+ (𝑣𝑖, 𝑣𝑖+1) ∈ 𝐴.
 Onappelle distance entre deux
d’un graphe orienté la longueur
sommets du
plus petit chemin les
reliant.
 S’il n’existe pas de chemins entre Ici d(1, 3)=2 ; d(1, 4)=2 ;
les sommets 𝑥 et 𝑦, on pose 𝑑 𝑥, 𝑦 d(5, 2)=∞
= ∞.
 Un circuit (ou cycle orienté) est un chemin
©Cours de B. Rabhi– ISSATKasserine – 2019/2020
fermé simple (𝑣 = 𝑣 ). 51
 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. Rabhi– ISSATKasserine – 2019/2020 52

 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 deux sommets exactement (𝑎 et 𝑏) on a 𝒅+ 𝒂 =
pour 𝒂 +𝟏
𝒅
𝒅 +− 𝒃 = 𝒅− 𝒃 − et
𝟏.

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

©Cours de B. Rabhi– ISSATKasserine – 2019/2020
53
 Matrice
Définition d’adjacence
Soit 𝐺 = 𝑉 , un graphe orienté, avec 𝑉 = *𝑣1, 𝑣2, … , 𝑣𝑛+ .
𝐴
matrice d’adjacence La du graphe est matrice 𝑴 (𝑮 )
la 𝟏, 𝒔𝒊
dont les
𝑣𝑖, 𝑣𝑗
coefficients (𝑚𝑖,𝑗) sont définis par : 𝒎𝒊,𝒋 =
𝟎, 𝒔𝒊 𝑣𝑖 , 𝑗 ∈ 𝑨
Exemple 𝑣 ∉ 𝑨

©Cours de B. Rabhi– ISSATKasserine – 2019/2020

54
 Matrice
Propriétés d’adjacence
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

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

 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. Rabhi– ISSATKasserine – 2019/2020
55
 Matrice
Définitions d’adjacence
 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. Rabhi– ISSATKasserine – 2019/2020
56
 Matrice
Exemple
d’adjacence
 Donner le nombre de chaînes orientées de longueur minimale pour
aller de 𝐷 à 𝐸 ?

©Cours de B. Rabhi– ISSATKasserine – 2019/2020

57
 Matrice
Exemple d’adjacence
 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
©Cours de B. Rabhi– ISSATKasserine – 2019/2020
chaîne ( 𝑴 𝟓 𝑫, 𝑬 = 𝟏). 58
 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. Rabhi– ISSATKasserine – 2019/2020

59