Université Ferhat Abbas Sétif 1

Faculté des sciences

Département informatique

Niveau L2
2022/2023
 Rappels
a) Graphe planaire
 Un graphe est dit planaire s’il possède au moins une représentation
planaire.
 Théorème KURATOWSKI : Un graphe est planaire si et seulement s’il
ne contient pas un sous-graphe homéomorphe à K3,3 et à K5.
(subdivision à K3,3 (le sous-graphe complet biparti à 3+3 sommets) et K5
(clique de 5 sommets))
 Dans un graphe planaire simple, il existe un sommet de degré ≤5.
 Relation d'Euler : Soit G un graphe planaire connexe, f le nombre de
faces de cette représentation, n le nombre de sommets et m le nombre
d'arêtes de G, on a : n-m+f=2.
Rappels
c) Graphe Eulérien
 Un graphe non orienté est Eulérien si, et seulement si, il est connexe et tous
ses sommets sont de degré pair.
 Un graphe orienté est Eulérien si, et seulement si, il est connexe et pour tous
ses sommets le degré sortant est égal au degré entrant : ∀ x X : d+(x) = d-(x).
 Dans tous les cas (G orienté ou pas) si seulement deux sommets ne vérifient
pas les conditions précédentes alors G est semi-Eulérien (G admet chaine ou
chemin Eulérien).
d) Graphe hamiltonien
 Théorème de Meyniel (1973) : soit G un graphe simple d’ordre n, fortement
connexe. Si pour toute paire {x, y} de sommets non voisins (non adjacents),
on a dG(x) + dG (y) ≥ 2 *n -1 alors ce graphe contient un circuit hamiltonien.
 Théorème de Dirac (1952) : Soit G = (X, U) un graphe simple d'ordre n≥ 3. Si
pour tout sommet x de G, on a dG (x) >= n/2, alors G admet un cycle
hamiltonien.
 Théorème d'Ore (1961) : Soit G = (X, U) un graphe simple d'ordre n ≥ 3 tel que
toute paire {x, y} de sommets non adjacents vérifie dG (x) + dG (y)>=n admet
un cycle hamiltonien.
 Rappels
e) Arbre
 Un arbre d'ordre n ≥2 admet au moins deux sommets pendants.
 Un graphe admet un arbre comme graphe partiel si et seulement si est
connexe.
f) Coloration
 Tout graphe planaire est 4-chromatique
 P ≤ (G)≤ 1+ D
❑ Soit D le degré maximal des sommets d’un graphe G,
alors (G) ≤ 1+ D.
❑ Soit P l’ordre de « Clique » maximal contenu dans un graphe,
alors P ≤ (G).
 Exercice1:
Trois pays envoient chacun à une conférence deux espions ;
chaque espion doit espionner tous les espions des autres
pays (mais pas son propre collègue !).
a) Représenter cette situation par un graphe d’ordre 6.
b) Ce graphe est-il complet ? est-il connexe ?
c) Quel est le degré de chaque sommet ? Déduire le nombre
d’arêtes.
Exercice1: Solution
a) Représenter cette situation par un graphe d’ordre 6.
1 2
Sommets: les espions
6 Arêtes: la relation espionner
3
5 4
b) Ce graphe est-il complet ? est-il connexe ?
Le graphe n’est pas complet car les paires de sommets ( 1, 2), (3,
4) et (5, 6) ne sont pas adjacents.
Il est connexe car entre chaque pair de sommet on peut trouver
une chaine les reliant.
c) Quel est le degré de chaque sommet ? Déduire le nombre
d’arêtes.
d(1)= d(2)= d(3)= d(4)= d(5)= d(6)=4, et on a ∑ d(x)= 2*m
➔ 4*6= 2*m ➔ m=12 arêtes.
 Exercice2:
Un groupe de six personnes se
retrouve pour dîner. Le graphe ci-
contre précise les
«incompatibilités d’humeur »
entre les personnes de ce groupe
(une arête reliant deux personnes
indique que celles-ci s’entendent
très modérément…).
a) Proposer un plan de table (la
table est ronde) pour ce groupe en
évitant de placer côte à côte deux
personnes «incompatibles ».
b) Combien y a-t-il de solutions
possibles ?
Exercice2: solution
a) Proposer un plan de table
Il s’agit de trouver des cycle
hamiltoniens dans le graphe
complémentaire du graphe (dont les
arêtes sont en rouge), on peut trouver
le plan( 1, 6, 3, 2, 4, 5)
b) Combien y a-t-il de solutions
possibles ?
Il y’ a 1 seule solution, car il y a deux sommet
de degré=2 (2 et 5) de plus ont un sommet
adjacent en commun (4) ➔ 5 personnes ne
peuvent changer de places il reste une seule
qui prend la sixième chaise.
Pour démontrer ça on fait le parcours en
largeur du graphe complémentaire (en rouge)
Exercice2: solution
b) Parcours en largeur du graphe complémentaire (en rouge) pour déterminer
le nombre de solution possible: on cherche toutes les chaines commençant en
1, parcourant tous les sommets une et une seule fois et se terminant en 1.
➔Parcourir 6 niveaux (longueur de la chaine)
Niveau 0
1
Niveau 1
3 5 6
Niveau 2
2 1 6 1 4 1 3 4
Niveau 3
3 4 1 3 4 2 5 6 1 2 6 2 5 6

3 Niveau 4
2 5 6 2 6 5 3 4 1 3 4 3 4 4 1 4

3 4 1 4 1 2 6 1 2 6 Niveau 5
1 4 1 3 4 5 2 6 1 2 6
4 Niveau 6
1 3 4 3 1 4
On remarque qu’il y a deux chaine de longueur 6 se terminant en 1: 1, 5, 4, 2, 3, 6, 1, et 1, 6,
3, 2, 4, 5, 1, mais pour un plan de table il y a une seule solution puisque c’est la même
chaine en inversant.
Exercice3:
Un livreur d’une société de vente à domicile
doit, dans son après- midi, charger son camion
à l’entrepôt noté A, livrer cinq clients que nous
noterons B, C, D, E et F, puis retourner à
l’entrepôt. Le réseau routier, tenant compte des
sens de circulation, et les temps de parcours (en
minutes) sont indiqués sur le graphe G suivant :
a) Donner la matrice M associée au graphe G.
Soit la matrice M6. On s’intéresse aux chemins
partant de l’entrepôt A et se terminant en A.
b) Combien existe-t-il de chemins de longueur
6 reliant A à A ?
c) Citer ces chemins.
d) Parmi ceux qui passent par tous les sommets
du graphe, lequel minimise le temps de
parcours ?
e) Quelle conséquence peut tirer le livreur du
dernier résultat ?
Exercice3: Solution
a) Donner la matrice M associée au graphe G.
A B C D E F
A 0 0 0 0 1 0
B 1 0 0 0 0 1
C 0 1 0 1 0 1
D 1 0 1 0 0 1
E 0 0 0 1 0 0
F 1 1 1 0 0 0
b) Combien existe-t-il de chemins de longueur 6
reliant A à A? Il y a 8 ( à partir de la matrice M6)
c) Citer ces chemins: en utilisant la parcours en
largeur on aura les chemins suivants:
(A, E, D, F, C, D, A) , (A, E, D, F, C, F, A) ,
(A, E, D, F, C, B, A) t= 28, (A, E, D, F, B, F, A) ,
e) Par conséquent, le
(A, E, D, C, D, F, A) , (A, E, D, C, B, F, A) t= 28,
livreur va prendre le
(A, E, D, C, F, B, A) t= 21 , (A, E, D, A, E, D, A) , chemin cité dans d)
d) Parmi ceux qui passent par tous les sommets du pour minimiser son
graphe, (A, E, D, C, F, B, A) minimise le temps de temps de travail.
parcours, avec 21 min de temps de transport.
 Exercice 4:
a) Appliquer l’algorithme de Welsh et Powell aux graphes G1, G2
et G3.

b) Proposer une suite d'entiers naturels telle qu'il n'existe aucun

graphe (simple ou pas) ayant comme degrés les valeurs de la
suite. Justifier votre réponse.
 Exercice 4(solution)
a/ Le nombre chromatique γ(G)
 D est le degré maximal des sommets du graphe G.
 P est l’ordre de « clique » maximal contenu dans le graphe
 Donc : P ≤ γ(G) ≤ 1+D

Nombre chromatique γ(G) : est le nombre de couleurs qu’on

peut attribuer aux sommets d’un graphe non-orienté de
façon à ce que deux sommets adjacents ne soient pas colorés
de la même couleur.
Algorithme de coloration de welsh et
powell
1. Repérer le degré de chaque sommet.
2. Ranger les sommets par ordre de degrés décroissants.
3. Attribuer au premier sommet (A) de la liste une couleur.
4. Suivre la liste en attribuant la même couleur au premier sommet
(B) qui ne soit pas adjacent à (A).
5. Suivre (si possible) la liste jusqu’au prochain sommet (C) qui ne
soit adjacent ni à A ni à B.
6. Continuer jusqu’à ce que la liste soit finie.
7. Prendre une deuxième couleur pour le premier sommet (D) non
encore coloré de la liste.
8. Répéter les opérations 4 à 7.
9. Continuer jusqu’à avoir coloré tous les sommets.
 Exercice 4:(solution)
a/ En appliquant l’algorithme de Welsh et Powel : → Algorithme de
coloration
LE GRAPHE G1:
Etape1:

Etape2:

Etape 3, 4:

Etape 7:

Etapes 8, 9
Exercice 4: (solution)

On a besoin de 3 couleurs donc : γ(G1)=3.

P<= γ(G1)<= D+1 ➔ 3<= γ(G1) <= 3+1
γ(G1) est minimal
Exercice 4(solution)
On applique les étapes précédentes de l’algorithme «Welsh et
Powel » avec G2 et G3 :
Pour G2 :

On a besoin de 2 couleurs donc : γ(G2)=2.

(2<=γ(G2)<=3+1) ➔ γ(G2) est minimal
Pour G3 :

On a besoin de 3 couleurs donc : γ(G3)=3.

(3<=γ(G2)<=6+1) ➔ γ(G3) est minimal
Exercice 4(solution)
b) Proposer une suite d'entiers naturels telle qu'il
n'existe aucun graphe (simple ou pas) ayant comme
degrés les valeurs de la suite. Justifier votre réponse.
Les suites non-graphiques :
S1 (1,1,3,5,4,1,1), s2( 5,5,1,2) , s3 (3,3,1,1) …etc. : ce sont
des suites de degré des sommets non graphiques.
(on peut pas dessiner le graphe correspond)
Exercice 5
Le graphe suivant représente le plan d'une
ville. Les arcs du graphe représentent les
principales avenues (sens de circulation)
et les sommets du graphe les carrefours
entre ces avenues.
a) Appliquer l’algorithme vu en cours pour déterminer les composantes
fortement connexes de ce graphe. En quoi le nombre de composantes
fortement connexes du graphe peut-il être modifié par l’ajout d’un
nouvel arc ?
b) Peut-on trouver un trajet de longueur quelconque qui permet d'aller
de D à B en respectant les sens de circulation ? Justifier la réponse.
c) Calculer la matrice M3.
d) Combien y-a-t-il de chemins de longueur 3 arrivant au E ? Expliquer
la démarche.
Combien y-a-t-il de chemins de longueur 3 partant du B et arrivant en A
? Écrire tous ces chemins.
e) Combien y-a-t-il de circuits de longueur 3 partant du B ?
f) Combien y-a-t-il de circuits de longueur 3 ?
Exercice 5( Solution)
a)Appliquer l’algorithme CFC pour
déterminer les composantes fortement
connexes du graphe.
Algorithme CFC
Données: un graphe orienté G=(X, U).
Debut
k0; WX;
tant que W≠  faire
choisir un sommet x de W et le marquer
d’un signe (+) et (-). k0; W {A, B, C, D, E, F}
Marquet tous les successeurs directs et Choisir A (-) (+),
indirects de x avec (+)
Marquer tous les prédécesseurs directs et Marquer (+) {E, D} , Marquer (-) {B, C,E, D, F}
indirects de x avec (-) C1={A, D, E}
k k+1;
Ck l’ensemble des sommets marqués W={B, C, F}
avec (+) et (-) Choisir B (-) (+),
W w – Ck Marquer (+) {C, F} , Marquer (-) {C, F}
Fin tant que
Fin C2={B, C, F}
Résultat: la liste {C1, C2, …, Ck} de W= 
composantes fortement connexes de G
Fin
Les CFC= {C1, C2}/ C1={A, D, E} , C2= {B, F, C}
En quoi le nombre de composantes fortement connexes du graphe peut-il être modifié par
l’ajout d’un nouvel arc ?
L’ajout d’un nouvel arc peut servir à réduire le nombre de composantes fortement connexes
Exercice 5
b) Peut-on trouver un trajet de
longueur quelconque qui permet d'aller
de D à B en respectant les sens de circulation ? Justifier la
réponse.
On ne peut pas trouver ce trajet car tous les arcs entre les
composantes fortement connexes C1 contenant D et C2
contenant B sont dans le sens de C2 vers C1.
c) Calculer la matrice M3.
M= 0 0 0 0 1 0 M2= 0 0 0 1 1 0 M3= 1 0 0 0 0 0
1 0 1 0 0 1 1 1 1 1 2 0 3 1 1 3 1 1
1 1 0 1 0 0 2 0 1 0 1 1 1 1 1 2 4 0
1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 0
0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 1 0
0 0 1 0 1 0 1 1 0 2 0 0 3 0 1 0 1 1
Exercice 5
d) Combien y-a-t-il de chemins de longueur 3
arrivant au E ? Expliquer la démarche.
À partir de la matrice M3, la colonne E représente les A B E
nombres de chemins arrivant en E et partant de
chacun des sommets; en calculant la somme, nous 1 0 0 0 0 0
obtiendrons le nombre de tous les chemins de B 3 1 1 3 1 1
longueur 3 arrivant en E: (1+3+1+1= 6) 1 1 1 2 4 0
Combien y-a-t-il de chemins de longueur 3 partant 0 0 0 1 1 0
du B et arrivant en A ? Écrire tous ces chemins.
Ligne B colonne A de M3= 3 chemins de longeur 3 0 0 0 0 1 0
allant de B à A; 3 0 1 0 1 1
e) Combien y-a-t-il de circuits de longueur 3 partant
du B ?
Ligne B Colonne B= 0 circuits de longueur 3 partant
de B
f) Combien y-a-t-il de circuits de longueur 3 ?
Les circuits de longueur 3 sont dans la première
diagonale de la matrice M3, en calculant la somme
des valeurs, nous obtiendrons le nombre de circuits
de longueur 3 =(1+2+1+1+1=6 circuits de longueur 3)
Exercice 6
Soit G=(X, U) un graphe non-orienté.
a) Proposer un algorithme qui vérifie si G contient ou
pas un sommet pendant dans le cas ou G est représenté
par matrice d’adjacence A.
b) Proposer un algorithme qui calcule le degré
maximum de G en utilisant la matrice d’adjacence A. On
appelle degré maximal d'un graphe G qu'on note par
Δ(G), le plus grand degré dans le graphe G.
Exercice 6 (Solution)
a) Proposer un algorithme qui vérifie si G contient ou pas un sommet
pendant dans le cas ou G est représenté par matrice d’adjacence A.
Algo sommet pendant
Donnée: Matrice d’adjacence A du graphe G;
Début
pendant false;
pour i allant de 1 à n faire
s0;
pour j allant de 1 à n faire
s s+ A[i, j];
fin pour
si s=1 alors pendant  true; break;
fin pour
Fin
Résultat: si pendant est vrai alors le graphe contient un sommet
pendant sinon, il ne le contient pas
Exercice 6 (Solution)
b) Proposer un algorithme qui calcule le degré maximum de G en
utilisant la matrice d’adjacence A. On appelle degré maximal d'un
graphe G qu'on note par Δ(G), le plus grand degré dans le graphe G.
Algo degré maximum
Donnée: Matrice d’adjacence A du graphe G;
Début
D_max 0;
pour i allant de 1 à n faire
s0;
pour j allant de 1 à n faire
s s+ A[i, j];
fin pour
si s> D_max alors D_max  s;
fin pour
Fin
Résultat: D_max le degré max du graphe G
 Exercice 7
a) Les deux graphes ci-dessous sont-ils isomorphes ? Justifier votre
réponse.

b) Les graphes simples ayant les matrices d'adjacence suivantes sont-ils

isomorphes ?

c) Les graphes simples suivants sont-ils planaires ?

 Exercice 7(solution)
Un isomorphisme de graphes est une bijection entre les
sommets de deux graphes qui préserve les arêtes.

a-1) le graphe G et H ne sont pas isomorphes :

dans le graphe H , d(4)=1 , par contre dans le graphe G il
n’existe pas un sommet de degré égal à 1. Même si G et H
ont cinq sommets et six arêtes, Ils ne sont donc pas
isomorphes.
 Exercice 7(solution)
a-2)

- Le nombre de sommets de G = le nombre de sommets de H.

- Le nombre des arêtes mG= mH = 9
- Le degré G,H : d(1)= d(2)= d(3)=d(4)= d(5)= d(6)
- Donc G et H sont isomorphes.
 Exercice 7(solution)
b-1)

- Le nombre de sommets de A=le nombre de sommets de B = 3

- Le nombre des arêtes mA= mB= 4
- Pour le graphe A : d(1)= 1, d(2)=1, d(3)=2
- Pour le graphe B : d(b)=1, d(3)=1, d(a)= 2
- Donc A et B sont isomorphes
 Exercice 7(solution)
b-2)

- Le nombre de sommets de A=le nombre de sommets de B = 4

- Le nombre des arêtes mA=8 mB= 10
-Donc, A et B ne sont pas isomorphes
 Exercice 7(solution)
c) Les graphes simples suivants sont-ils planaires ?

Un graphe est planaire si on peut le redessiner sans qu’il y

aura d’intersection entre les arrêtes. Et lorsque n-m+f=2
Les deux graphes sont planaires ; on peut les redessiner
 Exercice 8
a) Trois maisons doivent être reliées à 3 usines qui leur
fournissent l'eau, le gaz et l'électricité ; on demande de
tracer le plan du réseau de telle manière que les tuyaux ne
se croisent pas.
b) Est-il possible que dans un pays, il existe cinq villes
toutes reliées aux quatre autres par des routes différentes
qui ne se croisent pas ? (Raisonnement par l’absurde)
c) Le graphe ci-contre admet –il un cycle eulérien ?
Une chaine eulérien ? Si ce n’est pas le cas,
comment le rendre eulérien ?
Exercice 8 (Solution)
a) Trois maisons doivent être reliées à 3 usines qui leur fournissent l'eau, le gaz
et l'électricité ; on demande de tracer le plan du réseau de telle manière que les
tuyaux ne se croisent pas.
Essayons de dessiner le plan,
sous forme d’un graphe planaire
Ça revient à démontrer que le graphe
bipartie K3,3 est un graphe planaire.
Dans un graphe bipartie K3,3 on a m=3*6/2
∑ d(x)= 2*m ➔n*3= 2*m ➔ 6*3= 2* m ➔ m=9
D’après la formule d’Euler: dans un graphe planaire connexe à n sommets, m
arêtes et f faces, on a : n-m+f=2
Donc: f= 2-n+m= 2-6+9 ➔ f=5
Et comme G est bipartie et simple, chacune des faces utilise au moins 4 arêtes
et chaque arête intervient sur 2 faces
Ainsi, 4f<= 2m➔ f<= 2*9/4 ➔ f<=18/4
Comme 5 est > 18/4 Alors K3,3 n’est pas planaire.
La réponse est: Non, K3,3 n’est pas planaire, et par conséquent il n’est pas
possible de relier les 3 maisons aux 3 usines sans que les tuyaux ne se croisent.
Exercice 8 (Solution)
b) Est-il possible que dans un pays, il existe cinq villes toutes
reliées aux quatre autres par des routes différentes qui ne se
croisent pas ? (Raisonnement par l’absurde)
La situation se représente sous forme d’un graphe complet K5
(on cherche à démontrer si K5 est planaire)
Dans un graphe complet K5 on a m=(n*(n-1))/2
∑ d(x)= 2*m ➔n*(n-1)= 2*m ➔ 5*4= 2* m ➔ m=10
D’après la formule d’Euler: dans un graphe planaire connexe à n
sommets, m arêtes et f faces, on a : n-m+f=2
Donc: f= 2-n+m= 2-5+10 ➔ f=7
Mais, G est simple, chacune des faces utilise au moins 3 arêtes et
chaque arête intervient sur 2 faces
Ainsi, 3f<= 2m➔ f<= 2*10/3 ➔ f<=20/3
Comme 7 est > 20/3 Alors K5 n’est pas planaire.
Exercice 8 (Solution)
c) Le graphe ci-contre admet –il un cycle eulérien ?
Une chaine eulérien ? Si ce n’est pas le cas,
comment le rendre eulérien ?
❑cycle eulérien => connexe, et tous les degrés sont pair.
G n’admet pas un cycle eulérien, car d(4)= 3 (impair).
❑chaine eulérienne => connexe, et le nombre des sommets
de degré impair 0 ou 2.
G admet une chaine eulérienne d(4) = 3, d(5) = 3, et les autres
sommets sont de degrés pairs.
❑ Il suffit de rendre tous les sommets de degré
pair pour le rendre eulérien. (on peut
enlever l’arête (4, 5), et il devient eulérien.
Exercice 9
Soit un réseau comportant des
machines A, B, C, D, et E qui
doivent pouvoir communiquer
entre elles. Les coûts de liaisons
envisagées sont représentés par
la matrice suivante:
➢ Comment câbler le réseau à
moindre coût ?
Exercice 9: (Solution)
Le graphe correspondant à ce
réseau est le suivant:
➢ Comment câbler le réseau à
moindre coût ?
Répondre a cette question revient
à chercher l’arbre couvrant de
poids minimal ➔ utiliser
l’algorithme de Prim ou celle de
Kruskal
Exercice 9: (Solution)
Algorithme de Prim
Données: un graphe non orienté G=(X, U)
valué par  : X→  et un sommet s.
Début
Poids 0;(poids total de l’arbre couvrant);
U’ ;
Marquer s;
Tant que (il reste des sommets non marqués) faire
  arête de poids minimal joignant un sommet marqué
x et un sommet non marqué y;
Marqué y;
U’ U’  {};
Poids Poids+ ();
Fin tant que
Résultat: un arbre couvrant minimal T= (X, U’).
Exercice 9: (Solution) +
+
Algorithme de Prim +
Données: un graphe non orienté
G=(X, U)
valué par  : X→  et un sommet s.
Début +
+
Poids 0;(poids total de l’arbre
couvrant);
Poids  0; U’ ; Marquer A
U’ ;   (A, E);
Marquer s; Marquer E;
Tant que (il reste des sommets non U’ {(A, E)}
marqués) faire Poids 4;
  arête de poids   (E, D);
minimal joignant un sommet Marquer D;
marqué x et un sommet non U’ {(A, E), (E, D)}
marqué y; Poids 6;
Marqué y;   (D, C);
U’ U’  {}; Marquer C;
Poids Poids+ (); U’ {(A, E), (E, D), (D, C)}
Fin tant que Poids 9;
Fin   (C, B);
Résultat: un arbre couvrant Marquer B;
minimal T= (X, U’). U’ {(A, E), (E, D), (D, C), (C, B)}
Poids 11;
Résultat: T(X, U’)(l’arbre couvrant en bleu sur le
graphe)
Exercice 9: (Solution)
Algorithme de Kruskal
Données: un graphe non orienté G=(X, U)
valué par  : X→ .
Début
Poids 0;(poids total de l’arbre couvrant); U’ ;
Pour tout s dans X faire
E(s) {s} fin pour // E(s) représente les sommets reliés à s
Pour {s, s’}  U dans l’ordre croissant faire
si E(s) <> E(s’) alors //s et s’ n’ont pas de sommets reliés en commun
U’  U’  (s, s’); Poids  Poids + ((s, s’));
F E(s)  E(s’);
pour tout z dans F faire
E(z) E(z)  F; fin pour
Fin si
Fin pour
fin
Résultat: un arbre couvrant minimal T= (X, U’).
Exercice 9: (Solution)
Algorithme de Kruskal Arêtes avec poids
Données: un graphe non orienté G=(X, U) ascendants:
valué par  : X→ . (B, C) 2
Début (E, D) 2
Poids 0;(poids total de l’arbre couvrant); (C, D) 3

U’ ; (A, E) 4

Pour tout s dans X faire (B, D) 4 éliminé

E(s) { s} finpour (A, B) 5 éliminé
(B, E) 6 éliminé
Pour {s, s’}  U dans l’ordre croissant faire
si E(s) <> E(s’) alors Poids 0, U’ 0;
U’  U’  (s, s’); Poids  E(A)={A}, E(B)={B}, E(C)={C}, E(D)={D},
Poids + ((s, s’)); E(E)={E},
E(B) <> E(C) ➔ dessiner (B, C)
F E(s)  E(s’); Poids 2
pour tout z dans F faire E(B)=E(C)  {B, C}
E(z) F; E(E) <> E(D) ➔ dessiner (E, D)
fin pour Poids 4
Fin si E(E)=E(D)  {E, D}
E(C) <> E(D) ➔ dessiner (C, D)
Fin pour Poids 7
fin E(B)=E(C)=E(D) =E(E)  {B, C, E, D}
Résultat: un arbre couvrant minimal T= (X, E(A) <> E(E) ➔ dessiner (A, E)
U’). Poids 11
E(A)=E(E)= E(B)=E(C)=E(D)  {A, B, C, E, D}
Exercice 10
On considère les deux graphes non-orientés valués G1 et G2.
1- Déterminer un arbre couvrant de G1 De poids minimal
depuis le sommet s0 en utilisant l’algorithme de Prim.
2- Déterminer le poids minimal d’un arbre recouvrant le
graphe G2 en utilisant l’algorithme de Kruskal. Combien y a-t-
il d’arbres couvrants de poids minimal ?
Exercice 10: (Solution) + + +
1- Algorithme de Prim sur G1
Données: un graphe non
orienté G=(X, U) + +
+
valué par  : X→  et un Poids  0; U’ ; Marquer s0
sommet s.   (s0, s1);
Début Marquer s1;
Poids 0;(poids total de U’ {(s0, s1)}
l’arbre couvrant); Poids 1;
  (s1, s2);
U’ ;
Marquer s2;
Marquer s; U’ {(s0, s1), (s1, s2)}
Tant que (il reste des sommets Poids 2;
non marqués) faire   (s1, s5);
  arête de poids Marquer s5;
minimal joignant un sommet U’ {(s0, s1), (s1, s2), (s1, s5)}
marqué x et un sommet non Poids 6;
marqué y;   (s5, s4);
Marqué y; Marquer s4;
U’ U’  {}; U’ {(s0, s1), (s1, s2), (s1, s5), (s5, s4)}
Poids Poids+ (); Poids 8;
  (s4, s3);
Fin tant que Marquer s3;
Fin U’ {(s0, s1), (s1, s2), (s1, s5), (s5, s4), (s4, s3)}
Résultat: un arbre couvrant Poids 11;
minimal T= (X, U’). Résultat: T(X, U’)(l’arbre couvrant en bleu
sur le graphe)
Exercice 10: (Solution) Arêtes avec poids ascendants:
2- Algorithme de Kruskal sur G2
Données: un graphe non orienté G=(X, U) (s1, s5) 1 (s4, s8) 3
valué par  : X→ .
(s3, s5) 1 (s2, s5)éliminé
3
Début
Poids 0;(poids total de l’arbre couvrant); (s5, s6) 1 (s2, s7)éliminé
3
U’ ;
Pour tout s dans X faire (s1, s3)éliminé
2 (s0, s3) 4
E(s) { s} finpour
(s1, s7) 2 (s7, s8)éliminé
4
Pour {s, s’}  U dans l’ordre croissant faire
si E(s) <> E(s’) alors (s3, s6)éliminé
2 (s0, s1)éliminé
5
U’  U’  (s, s’); Poids 
Poids + ((s, s’)); (s5, s7)éliminé
2 (s4, s7)éliminé
5
F E(s)  E(s’);
pour tout z dans F faire
(s2, s6) 2 (s2, s8)éliminé
5
E(z) F; (s1, s4) 3 (s0, s4)éliminé
6
fin pour
Fin si Poids 0, U’ ; E(s)={s}, pour tout sommet s
Fin pour E(s1) <> E(s5) ➔ dessiner (s1, s5); Poids 1, E(s1)=E(s5)  {s1, s5}
fin
Résultat: un arbre couvrant minimal
E(s3) <> E(s5) ➔ dessiner (s3, s5)
T= (X, U’). Poids 2, E(s1)=E(s3)=E(s5)  {s1, s3, s5}
E(s5) <> E(s6) ➔ dessiner (s5, s6)
Nombre d’arbres Poids 3, E(s1)=E(s3)=E(s5)=E(s6)  {s1, s3, s5, s6}
couvrant E(s1) <> E(s7) ➔ dessiner (s1, s7)
minimaux: Poids 5, E(s1)=E(s3)=E(s5)=E(s6)= E(s7)  {s1, s3, s5, s6, s7}
Lorsqu’on échange E(s2) <> E(s6) ➔ dessiner (s2, s6)
Poids 7, E(s1)=E(s2)=E(s3)=E(s5)=E(s6)= E(s7)  {s1, s2, s3, s5, s6, s7}
entre les deux arcs
E(s1) <> E(s4) ➔ dessiner (s1, s4), Poids 10,
(s1, s7) et (s5, s7) – E(s1)=E(s2)=E(s3)=E(s4)=E(s5)=E(s6)= E(s7)  {s1, s2, s3, s4, s5, s6, s7}
qui sont de même E(s4) <> E(s8) ➔ dessiner (s4, s8), Poids 13,
poids, on aura un E(s1)=E(s2)=E(s3)=E(s4)=E(s5)=E(s6)= E(s7)= E(s8)  {s1, s2, s3, s4, s5, s6, s7, s8}
arbre différent➔ il E(s0) <> E(s3) ➔ dessiner (s0, s3), Poids 17,
ya 2 arbres E(s0)= E(s1)=E(s2)=E(s3)=E(s4)=E(s5)=E(s6)= E(s7)= E(s8)  {s0, s1, s2, s3, s4, s5,
couvrants s6, s7, s8}
minimaux
Exercice 11

En utilisant l’algorithme de Dijkstra, trouver les plus

courts chemins de s aux autres sommets du graphe G de
la Figure ci-contre.
A chaque étape, on donnera le pivot utilisé et les
modifications apportées aux distances à partir de s. A la
fin de l’exécution, donner l’arborescence des plus courts
chemins d’origine s.
Exercice 11 (Solution)
Algorithme (Moore –dijkstra): déterminer les plus courts chemins du sommet
s aux autres sommets dans un graphe dont les longueurs sont positives.
a) Initialisation
𝜋 𝑠  0; 𝑆ҧ  {1,2,…,N}\{s}
Pour tout (i  𝑆)ҧ faire
si (i   (s) ) alors
𝜋 𝑖  lsi;
sinon
𝜋 𝑖  +
finsi
finpour
b) Tant que (𝑆ҧ ≠ ∅) faire
sélectionner j𝑆ҧ tel que 𝜋 𝑗 = min 𝜋 𝑖 /𝑖 ∈ 𝑆ҧ
𝑆ҧ 𝑆ҧ \{j};
pour tout (𝑖 ∈  (j) ∩ 𝑆)ҧ faire
𝜋 𝑖  min{ 𝜋 𝑖 , 𝜋 𝑗 + lji } fin pour
fin tant que
Lorsque l’algorithme se termine, 𝜋 𝑖 correspond à la valeur du plus court
chemin entre s et i.
Exercice 11 (Solution)
s a b c d e f g h

0 + + + + + + + + s(0)

7 3 4 + + + + + b(3)
(s) (s) (s)

5 4 + + + 11 + c(4)
(b) (s) (b)

5 7 + + 11 + a(5)
Algorithme (Moore –dijkstra):
(b) (c) (b)
Initialisation
𝜋 𝑠  0; 𝑆ҧ  {1,2,…,N}\{s}
Pour tout (i  𝑆)ҧ faire 7 6 + 11 + e(6)
si (i   (s) ) alors (c) (a) (b)
𝜋 𝑖  lsi;
sinon 7 8 9 + d(7)
𝜋 𝑖  + (c) (e) (e)
finsi
finpour
8 9 13 f(8)
b) Tant que (𝑆ҧ ≠ ∅) faire
(e) (e) (d)
sélectionner j𝑆ҧ tel que 𝜋 𝑗 =
min 𝜋 𝑖 /𝑖 ∈ 𝑆ҧ
𝑆ҧ 𝑆ҧ \{j}; 9 13 g(9)
pour tout (𝑖 ∈  (j) ∩ 𝑆)ҧ faire (e) (d)
𝜋 𝑖  min{ 𝜋 𝑖 , 𝜋 𝑗 + lji } fin
pour
11 h(11)
fin tant que
(g)
Exercice 11 (Solution)

L’arborescence des plus courts

chemins
Exercice 12
Pour le dîner, le restaurateur décide de proposer des livraisons à domicile. Il
fait un essai avec huit clients.
Sur le graphe ci-dessous, les sommets représentent les différents lieux
d'habitation de ces huit clients. Les arêtes représentent les rues et les valeurs
indiquent les durées moyennes des trajets exprimées en minutes.
a) Répondre aux questions suivantes en justifiant.
1. Existe-t-il un parcours qui emprunte toutes les rues une et une seule fois ?
2. Un tel parcours peut-il partir de H1 et y revenir ?
b) En utilisant l'algorithme de Dijkstra, déterminer le temps minimal pour
aller de H4 vers H8. Préciser le trajet correspondant.
Exercice 12 (solution)
a) Répondre aux questions suivantes en justifiant.
1. Existe-t-il un parcours qui emprunte toutes les rues une et une seule fois ?
Oui il existe, entre les sommets H1, et H6, parce que le graphe admet une chaine
eulérienne (deux sommets –H1, H6- sont de degrés impairs et tous les autres
sommets sont de degrés pairs)
2. Un tel parcours peut-il partir de H1 et y revenir ?
Non, puisque le graphe n’est pas eulérien (il n’admet pas de cycle eulérien); où
tous les sommets doivent être de degrés pairs.
Exercice 11 (Solution) H4 H1 H2 H3 H5 H6 H7 H8

b) En utilisant l'algorithme de 0 + + + + + + + H4(0)

Dijkstra, déterminer le temps
8 + + 15 + + + H1(8)
minimal pour aller de H4 vers H8. (H4) (H4)
Préciser le trajet correspondant.
17 24 15 + + + H5(15)
(H1) (H1) (H4)

17 22 + + + H2(17)
(H1) (H5)

22 34 28 + H3(22)
(H5) (H2) (H2)

27 26 50 H7(26)
(H3) (H3) (H3)
Pour aller de H4 vers H8 on a
besoins à 35 min, en prenant le 27 35 H6(27)
trajet: H4, H5, H7, H8 (H3) (H7)

35 H8(35)
(H7)