Correction d’examen final
Questions de cours ( 06 pts)
1. Le degré maximal d’un graphe simple à n sommets est n-1 01
2. Quel est le nombre maximal d’arêtes (la taille) d’un graphe simple à n sommets :
n
Selon le lemme de la poigné de mains deg( s) 2 * A
s 1
n
D’où A deg( s) / 2 01
s 1
3. Existe-t-il un graphe à 6 sommets dont les degrés sont (1, 2, 3, 4, 5, 5) ? Oui 01
Justification : Un tel graphe doit contenir des arêtes multiples ou des boucles. On a deux sommets de
degré 5 (un lien avec toutes les autres sommets), tandis qu’on a un sommet de degré 1(contradiction).
4. La question se traduit en termes de graphe de la façon suivante : existe-t-il un graphe de 8 sommets avec
2 sommets de degré 4, 1 sommet de degré 2 et 5 sommets de degré 5 ? Ce graphe n’existe pas. 01
5. Non, on ne peut pas construire un graphe simple d’ordre N, tel que tous ses sommets ont des degrés
différents (de 0 à N-1). 01
Justification : Le sommet de degré N-1 devrait avoir une arête vers tous les autres, et ce n'est pas possible
puisqu'un sommet est de degré 0(isolé).
6. On ne peut pas utiliser l'algorithme de Dijkstra pour calculer les plus courts chemins dans un graphe si et
seulement si ce dernier contient des valeurs (poids) négative. 0,5
7. Un graphe admet un cycle eulérien si et seulement s'il n y pas des sommets de degré impair. 0,5
Exercice 01 ( 07 pts)
Soit le graphe G1= (V, E) ci-contre :
1. La matrice d’adjacence A de G1. 1,5
A partir de la matrice A, on peut déduire le
A B C D E F G H I J K L degré de sommet B :
On a :
A 0 1 0 0 0 0 0 0 0 0 0 0 12
d ( B) a2 j 3
B 0 0 1 1 1 0 0 0 0 0 0 0
j 1
C 0 0 0 0 0 1 0 0 0 0 0 0 12
d ( B ) ai 2 2
D 0 0 0 0 0 0 0 0 0 0 0 0
i 1
E 0 1 0 0 0 1 0 0 0 0 0 0 D’où d ( B) 5 0,5
F 0 0 1 0 0 0 0 0 0 0 0 0
A
G 0 0 0 0 0 0 0 1 0 1 0 0 A partir de la matrice M, on peut déduire le
H 0 0 0 0 0 0 0 0 0 0 1 0 degré de sommet G :
I 0 0 0 0 0 0 1 0 0 0 0 0
17
J 0 0 0 0 0 0 0 0 1 0 0 0 d (G ) a7 j 4 0,25
j 1
K 0 0 0 0 0 0 0 0 0 0 0 1
L 0 0 0 0 0 0 0 0 0 1 0 0
1. La matrice d’incidence aux arcs M de G1. 02
01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17
A 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
B 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0
C 0 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0
D 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
E 0 0 0 1 1 0 0 1 1 0 0 0 0 0 0 0 0
F 0 0 0 0 0 1 1 1 0 1 0 0 0 0 0 0 0
M
G 0 0 0 0 0 0 0 0 1 0 1 1 1 0 0 0 0
H 0 0 0 0 0 0 0 0 0 1 1 0 0 1 0 0 0
I 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0
J 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 0
K 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1
L 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1
2. Oui, G1 est connexe, parce que, quelques soient deux sommets i et j, il existe une chaîne (peu importe le
sens) joignant i à j. 0,5
G1 n’est pas fortement connexe, parce que, quelques soient deux sommets i et j, il n’existe pas un chemin
de i à j et un chemin de j à i ( exemple A et C). 0,5
3. Déterminer les composantes fortement connexes du G1.
(a) La CFC contenant le sommet A, C1={A} 0,25
(b) La CFC contenant le sommet B, C2={B, E} 0,25
(c) La CFC contenant le sommet C, C3={C, F} 0,25
(d) La CFC contenant le sommet D, C4={D} 0,25
(e) La CFC contenant le sommet G, C5={G, H, I, J, K, L} 0,25
4. Ci-contre le graphe réduit GR du graphe G1. 01
Exercice 02 ( 07 pts)
1. Ci-contre le graphe G2 =(V, E) de la situation :
2. L’algorithme utilisé : Algorithme de Dijkstra 0,25
Calcule des itinéraires : 2,5
A B C D E
0 ∞ ∞ ∞ ∞
1h30 (A) 2h00 (A) ∞ 2h15 (A)
2h00 (A) ∞ 2h15 (A)
h
4 55 (C) 2h15 (A)
4h55 (C)
Les itinéraires les plus rapides entre la ville A et toutes les autres villes :
A → B : 1h30 ; A → C : 2h00 ; A → E : 2h15 ; A → C → D : 4h55 01
3. Ci-contre le graphe partiel correspondant aux itinéraires obtenus : 01
4. Oui il est unique. 0,25
