Leçon : Graphes et sous graphes pondérés, plus court

chemin
Objectif pédagogique opérationnel : A la fin de ce chapitre l’élève doit être capable de
déterminer le plus court chemin entre deux sommets d’un graphe pondéré.

Motivation : Cette leçon peut être utilisé pour l’optimisation d’itinéraires dans les ré-
seaux routiers.

Situation problème :
Une femme enceinte aimerait connaitre le plus court chemin pour se rendre à l’hôpital
central de Yaoundé pour son accouchement. Elle habite le quartier Etoug-Ebe. Pour cela, elle
consulte la carte de la ville de Yaoundé suivante :

Figure 2.1 – Extrait de la carte de Yaoundé pris sur Google Map

Pour être plus efficace, elle représente ses différentes trajectoires possibles avec le temps
moyen mis par un taximan pour aller d’un point à un autre par le graphe suivant :
 H : Hôpital central A : Carrefour Acacia G : Gendarmerie nationale E : carrefour Etoug-
Ebe M : Total Melen C : Carrefour EMIA P : poste centrale R : Rond-point Express Y :
Camp YEYAP.
Quel est le plus court chemin que cette femme devra emprunter ?

Pour pouvoir résoudre le problème de plus court chemin entre deux sommets d’un graphe,
commençons par définir ces notions qui nous seront utiles pour la suite.

Résumé

Définition 2.2.1

Un graphe valué est un graphe pour lequel chaque arête est associée à un nombre réel
appelé poids. Si ce nombre est positif, on parle alors de graphe pondéré.

Le poids d’un sous graphe (resp. d’un chemin) dans un graphe valué est la somme des
poids des arêtes composant ce sous graphe (resp. ce chemin).

Exemple 2.2.1. Le graphe suivant est un graphe valué.

Le sous-graphe ci-dessous de ce graphe a pour poids :5 + 3 + 6 + 9 + 1 = 24

Pour résoudre le problème du plus court chemin entre deux sommets d’un graphe , il
existe de nombreux algorithmes . Nous présentons ici celui du mathématicien Dijkstra.

2.2.1 Algorithme de Dijkstra

Il permet de déterminer un chemin de poids minimum entre deux sommets d’un graphe.

1 Sélectionner le sommet de départ u et fixer son poids à 0.

2 Attribuer provisoirement un poids ∞ aux autres sommets.

3 Tant qu’il reste des sommets dont les poids ne sont pas définitivement fixés, répéter
les instructions suivantes :
— Parmi les sommets dont le poids n’est pas définitivement fixé, choisir un sommet
X dont le poids p est minimal, puis fixer définitivement p comme poids.
— Pour tous les sommets Y dont le poids n’est pas définitivement fixé et qui sont
adjacents au dernier sommet fixé X, calculer la somme s du poids de X et du
poids de l’arête reliant X à Y.
— Si la somme s est inférieure au poids provisoirement affecté au sommet Y,
affecter provisoirement à Y le nouveau poids s et indiquer en indice le sommet
X pour se souvenir de sa provenance.
— Si la somme s est supérieure au poids provisoirement affecté au sommet Y,
on ne change rien.

4 Quand le sommet d’arrivé v est définitivement fixé : Le chemin de poids minimum se

lit à l’envers, de v à chacun de ses prédécesseurs successifs.
Application 2.2.1. Résolvons la situation problème en utilisant l’algorithme de Dijkstra.
Il s’agit de déterminer le plus court chemin allant du sommet E au sommet H.
A l’étape 1 : On affecte le sommet E de 0.
A l’étape 2 : On peut aller à R (poids de 10) ou M (poids de 12). Les autres sommets restent
inchangés. La valeur minimale est 10 lorsque l’on vient de E. On sélectionne R.
A l’étape 3 : Depuis R , on peut aller uniquement en A (poids de 10 + 3 = 13). La valeur
minimale est 13 lorsque l’on vient de R. On sélectionne A.
A l’étape 4 : Depuis A, on peut aller en P (poids de 13 + 15 = 28). La valeur minimale est
17 lorsque l’on vient de M. On sélectionne C.
A l’étape 5 : Depuis C, on peut aller à G (poids de 17 + 3 = 20). La valeur minimale est 20
lorsque l’on vient de C. On sélectionne G. A l’étape 6 : Depuis G, on peut aller à H,(poids
de 20 + 3 = 23). La valeur minimale est de 23 venant de G ou de Y. On peut sélectionner
l’un ou l’autre. On aura deux plus courts chemins.

On peut résumer tous ces étapes dans le tableau suivant : Où l’écriture 10 − E signifie
qu’on vient du point E avec un poids de 10.

Tous les sommets ayant été fixés, on lit « à l’envers » la solution : H, qui vient de G, qui
vient de C, qui vient de M, qui vient de E ou encore H, qui vient de Y, qui vient de M, qui
vient de E.
D’où le trajet le plus rapide est celui de Carrefour Etoug-Ebe- Total Melen - Carrefour
EMIA - Gendarmerie Nationale- Hôpital Central ou encore celui de Carrefour Etoug-Ebe-
Total Melen - Camp YEYAP - Hôpital Central. Avec pour temps minimal 23 minutes.
Exercice d’application 2.2.1. Pour chacun des graphes suivants, déterminez un sous graphe
et calculez son poids.

Devoir 2.2.1. Exercice 1 ∗∗

Déterminez le plus court chemin allant du point E au point S dans le graphe suivant et
calculez son poids.

Exercice 2 ∗∗
Un voyageur de commerce prépare sa tournée. II doit visiter un certain nombre de clients
A, B, C, D, F et G en partant de E pour arriver en S . Les liaisons possibles sont représentes
ci-dessous avec la durée des trajets qui sont les poids des arêtes du graphe. Ce voyageur de
commerce souhaiterait savoir si un ordre de visite qui minimise la durée totale du trajet de
E à S lui permettrait de rencontrer tous ses clients. Est-ce possible ?
Exercice 3 ∗∗∗
Sur les arêtes du graphe suivant, représentant un réseau autoroutier, on a marqué les
distances entre deux étapes et, entre parenthèses, les prix des péages. Entre D et A, détermi-
nez :
— la chaîne la plus courte ;
— la chaîne qui minimise la somme dépensée en péage.

Exercice 4 ∗∗∗
Sur le tableau suivant sont indiqués les temps moyens (en minutes) mis par un automobi-
liste pour relier deux lieux de la ville de Yaoundé. On souhaite aller d’un point R (Rond-point
Express) au point M (Marché central). Déterminez un chemin qui soit le plus rapide à l’aide
de l’algorithme de Dijkstra.
 Leçon : Graphes eulériens et graphes hamiltoniens
Objectif pédagogique opérationnel :
A la fin de cette leçon l’élève doit être capable de déterminer s’il est possible de dessiner
un graphe sans lever le crayon et sans passer deux fois sur la même arête.

Motivation : Cette leçon permet de résoudre le problème qui consiste à visiter une ville
en passant dans un lieu une et une seule fois.

Situation problème :
Un livreur de journaux dans la ville de Yaoundé veut assurer sa livraison du jour dans 04
sous-préfectures de la ville, pour des raisons d’économies de carburant, il ne veut pas passer
par la même route deux fois.

Figure 2.2 – Plan des sous-préfectures de la ville de Yaoundé

Il représente La position des différentes sous-préfectures par le graphe ci-dessous. Ce

livreur pourra t’il réaliser son souhait ?
 Activité d’apprentissage

1 Soit les graphes suivants, calculer le degré de chaque sommets ?

2 Pour chaque graphe, combien y’a-t-il de sommets de degré pair ? Impair ? Que constates-
tu ?

Résumé
Nous allons définir les notions de graphes eulériens et de graphes hamiltoniens, qui ont
des applications particulièrement utiles dans la résolution d’un grand nombre de problèmes
concrets. Par exemple, ces notions sont utiles pour résoudre une énigme ayant la naissance
de la théorie des graphes :"les sept ponts de la ville de Königsberg".

Définition 2.3.1

On appelle cycle eulérien d’un graphe G un cycle contenant une et une seule fois toutes
les arêtes de G.
Un graphe est dit eulérien s’il possède un cycle eulérien.
On appelle chaîne eulérienne d’un graphe G une chaîne passant une et une seule fois
par chacune des arêtes de G.
Un graphe ne possédant que des chaînes eulériennes est semi-eulérien.

Remarque : 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 la même arête.

Exemple 2.3.1. Le graphe suivant possède plusieurs cycles eulériens :par exemple A − C −
E − D − B − C − D − A − B − E − A. C’est donc un graphe eulérien.
 Ce théorème donne une caractérisation simple des graphes eulériens.

Théorème 2.3.1 (EULER)

Un graphe connexe possède un cycle eulérien si et seulement si tous ses sommets sont de
degré pair.

Preuve. [5]
Soit G un graphe. Supposons G eulérien, soit alors c un cycle eulérien et x un sommet
de G. Le cycle c contient toutes les arêtes de G, donc toutes les d(x) arêtes ayant x comme
extrémité. Lors d’un parcourt de c on arrive en x autant de fois qu’on en repart, chaque
arête de G étant présente une et seule fois dans c, d(x) est nécessairement un nombre pair.
Réciproquement, supposons que tous les sommets de G soient de degré pair. Formons une
chaîne simple c1 , aussi longue que possible, à partir d’un sommet arbitraire x0 . Cette chaîne
c1 est en fait un cycle, sinon, son extrémité finale serait de degré impair. Si ce cycle c1 contient
toutes les arêtes du graphe G, c1 est le cycle eulérien cherché. Dans le cas contraire, on
considère le sous-graphe H obtenu à partir de G en éliminant les arêtes de c1 et ses sommets
qui ne sont incidents à aucune des arêtes restantes. Comme G est connexe, H possède au
moins un sommet commun avec le cycle c1 . Soit x1 un tel sommet. Les sommets de H sont
encore de degré pair. Construisons alors, de la même manière que précédemment, un cycle
c2 dans H à partir de x1 . Rallongeons le cycle c1 en insérant à partir du sommet x1 le cycle
c2 pour former un cycle c01 de x0 à x0 . Si ce cycle c01 possède toutes les arêtes de G, c01 est
le cycle eulérien cherché. Sinon, on continue ce processus, qui se terminera car les sommets
du graphe G sont en nombre fini.

Définition 2.3.2

Un chemin hamiltonien est un chemin qui visite chaque sommet d’un graphe exacte-
ment une fois.
Un cycle hamiltonien est un chemin hamiltonien qui commence et se termine au même
sommet.
Un graphe est dit hamiltonien s’il possède un cycle hamiltonien.
Un graphe ne possédant que des chaînes hamiltoniennes est semi-hamiltonien.

Exemple 2.3.2. Le graphe suivant possède plusieurs cycles hamiltoniens, par exemple :
a − b − e − c − d − f − a et d − f − e − c − b − a − d. C’est donc un graphe hamiltonien.

Remarque : Une condition nécessaire et suffisante pour visiter tous les sommets d’un
graphe sans lever le crayon est que le graphe soit hamiltonien.

Il n’existe pas une façon simple permettant de déterminer si un graphe a un cycle ha-
miltonien. Cependant, des mathématiciens ont pu trouver des conditions nécessaires et des
conditions suffisantes qui garantissent pour certains types de graphes, l’existence de cycle
hamiltonien.
 Propriété 2.3.1 (Conditions Nécessaires)

— 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.

Théorème 2.3.2 (ORE : Condition Suffisante)

Soit G un graphe simple d’ordre n ≥ 3 . Si pour toute paire {x, y} de sommets non adjacents,
on a d(x) + d(y) ≥ n alors G est hamiltonien.

Preuve. Soit G un graphe simple d’ordre n ≥ 3.

Par l’absurde, supposons que pour toute paire {x, y} de sommets non adjacents de G , on a
d(x) + d(y) ≥ n , mais que G ne soit pas Hamiltonien. Quitte à rajouter des arêtes, on peut
supposer que G soit non hamiltonien maximal, autrement dit il suffit de rajouter une arête à
G pour qu’il devienne hamiltonien.
Supposons que l’arête manquante soit (An − A1 ). Alors il existe déjà dans G une chaîne
A1 − A2 ...An . Le but est de montré qu’il existe un certain i ∈ {2, ..., n − 1} tels que les arêtes
(A1 − Ai+1 ) et (Ai − An ) existent. On aura un cycle hamiltonien A1 − A2 − ... − Ai − An −
An−1 ...Ai+1 − A1 . Ce qui fournira la contradiction.
Supposons qu’il n’existe aucun i tel que Ai + 1 soit adjacent à A1 et Ai à An . Notons k le degré
de An . Les sommets adjacents forment une suite Ai1 , Ai2 , ..., Aik avec 2 ≤ i1 < ... < ik < n − 1.
D’après la condition précédente, les sommets Ai1 +1 , ..., Aik +1 ne sont pas adjacents à A1 . Donc
le degré de A1 est inférieur à (n − 1) − k. Donc d(A1 ) + d(An ) ≤ n − 1 − k + k ≤ n − 1 ce qui
est faux.

Corollaire 2.1 (Dirac). Soit G un graphe simple d’ordre n ≥ 3. Si pour tout sommet x de
n
G, on a d(x) ≥ alors G est hamiltonien.
2
Preuve. La preuve du corollaire est évidente d’après le théorème. En effet, un tel graphe
vérifie les conditions du théorème précédent. Si x et y sont deux sommets non adjacents, on
n n
a bien : d(x) + d(y) ≥ + = n. D’où ce graphe est hamiltonien.
2 2