Année universitaire :2023/2024
Université SAAD DAHLEB 1
Niveau : L2
Faculté des sciences
Module Théorie des graphes
Département de l’informatique
Examen Durée 1h30
Matricule:……………………… Nom :…………..…...…….. Prénom :……………………..Groupe :…..
Exercice 1 : Répondre par vrai ou faux et corriger la proposition fausse (0.25 vrai /0.25 faux/
0.25 correction)
N° Correction
1 Faux
Un chemin est élémentaire si les sommets qu'il contient sont tous distincts.
2 Vrai
3 Faux
D’après la matrice d’adjacence, la taille d’un graphe non orienté est la somme des
nombres situés au-dessus (ou en dessous) de la diagonale principale
4 Faux
Le diamètre du graphe est la plus grande distance entre deux sommets du graphe.
5 Vrai
6 Vrai
7 Faux
Deux sommets xi, xj ont une relation de forte connexité s’il existe un chemin de xi
à [Link] de xj à xi
8 Vrai
9 Faux
Une composante connexe d'un graphe non orienté G est un sous-graphe induit G’
de G qui est connexe et maximal
10 Faux
Le nombre des arbres couvrant différents dans un graphe complet d’ordre 6 est
égale à 6
Exercice 2 :Soit le graphe G représenté par la matrice M qui donne les distances entre les
villes 1 à 8
1. Donner la représentation sagittale du graphe donné par (1pts -0.25 sur chaque erreur)
2
2 5
9
6 8
1 2
4
1 2 6
1 3
4 2
1
3
8 8
7 7
1/4
Année universitaire :2023/2024
Université SAAD DAHLEB 1
Niveau : L2
Faculté des sciences
Module Théorie des graphes
Département de l’informatique
2. Etudier la forte connexité du graphe ? Donner le graphe réduit et la suite des degrés qui le
représente (0.25 pour chaque CFC)
N°CFC 1CFC 2CFC 3CFC 4CFC
Sommet 1 2,5,3,7,4 6 8
Le graphe n’est pas fortement connexe (0.25) car il contient 4 composantes fortement
connexes (0.25)
Le graphe réduit : (0.25) La suite des degrés qui représente le graphe réduit
(0.5)
C2 C3
C1 (0,1) (1,2)(1,1) (2,0)
C4
3. En utilisant le graphe obtenu, Est-il possible de partir de la ville 1 et visiter les autres villes une
et une seule fois ? à quoi correspond la solution en termes de concepts liés à la théorie des
graphes ? Justifier votre réponse
Oui , On peut faire la visite. (0.25)
La solution correspond à trouver un chemin hamiltonien (0.25)
Justification le chemin hamiltonien : 1 7 3 2 4 5 6 8(0.25)
4. En utilisant le graphe obtenu, est-il possible de partir de la ville 1 et d’y revenir en passant par
chaque ville une et une seule fois ? à quoi correspond la solution en termes de concepts liés à la
théorie des graphes ? Justifier votre réponse
Non, la visite est impossible (0.25)
La solution correspond à trouver un circuit hamiltonien (0.25)
Justification : il n’existe pas un circuit hamiltonien qui passe par toutes les villes une et une seul
fois (0.25)
5. Quel est la solution à proposer pour rendre cette visite possible ?
Ajouter un arc de sommet 8 vers le sommet 1 (8 1) (0.25)
6. Quel est le chemin le plus court qui relie la ville 1 avec toutes les autres villes ? quel est
l'algorithme à appliquer ? Justifier votre choix ?
L’algorithme utilisé : Justification :
Djikstra ou Bellman- Graphe orienté avec des valeurs positifs(0.25)
ford(0.25)
1. Application de Djikstra 0.125 sur chaque ligne correcte (8 * 1/8 = 1pt)
2/4
Année universitaire :2023/2024
Université SAAD DAHLEB 1
Niveau : L2
Faculté des sciences
Module Théorie des graphes
Département de l’informatique
1 2 3 4 5 6 7 8
0 ∞ ∞ ∞ ∞ ∞ ∞ ∞
0* 6 2 8
2* 3
5 11 3* 12
5* 7
10 7* 14
10* 11
11* 13
13*
0 5 10 2 3 11 7 13
2. Application de Bellman-ford 0.125 sur chaque ligne correcte (8 * 1/8 = 1pt)
1 2 3 4 5 6 7 8
0* ∞ ∞ ∞ ∞ ∞ ∞ ∞
6* 2* 8*
11* 3* 15*
5* 12*
5* 7* 14*
10*
11*
13*
0 5 10 2 3 11 7 13
Arborescence 2
(1pts -0.25 sur 2 5
chaque erreur)
2 1 6
1 3
4 1 2
2 3
7 8
7. On considère G1 le graphe non orienté associé au graphe G :
A. Est-ce que le graphe possède-il une chaîne eulérienne ? Justifier
Non0.25, car il existe plus de deux sommets de degré impair0.25
B. Est-ce que le graphe est eulérien ? Justifier
Non0.25 , car il existe des sommets de degré impair(Il faut tous les sommets avoir des degrés
paire) 0.25
3/4
Année universitaire :2023/2024
Université SAAD DAHLEB 1
Niveau : L2
Faculté des sciences
Module Théorie des graphes
Département de l’informatique
Exercice 3 :
[Link] est le problème formel associe ?
Arbre couvrant de poids minimum 0.5
2. Déterminer la solution optimale, en indiquant le nom de l'algorithme utilisé et les étapes de
son déroulement.
L’algorithme utilisé : Kruskal Ou Prim 0.25
Kruskal
Arête AB AG BG BF AF GE FC BC FE CD DE GF
Poids 1√ 1√ 2 2√ 3 3√ 3√ 4 4 5√ 5 6 Stop
T=6
0.25 sur chaque arête dans le tableau + dessin
Prim
A AB AG BF GE CF CD STOP T=6
S Ø B G F E C D
Le graphe (1pts -0.25 sur chaque erreur) B
4 C
B C
1
2 2 3
5 A F
3 =
A F D
2 D
+ 4 4
1 G E
5
G E
3
Poids= 1+1+2+3+3+5= 15 0.25
Exercice 4 :
Le graphe 6
7
1
5
2
4
3
4/4
Année universitaire :2023/2024
Université SAAD DAHLEB 1
Niveau : L2
Faculté des sciences
Module Théorie des graphes
Département de l’informatique
L’algorithme Welsh powell Ou Dsatur 0.25 L’encadrement de nombre chromatique
Welsh powell 3 ≤X(G)≤5 0.25
sommet 7 4 5 6 2 3 1
Degré 4 4 4 4 4 2 2
Rouge √ √ √
Bleu √ √
Vert √ √
0.25 sur chaque couleur correcte (0.25 * 7 = 1.75)
L’algorithme;Dsatur L’encadrement de nombre chromatique
C1 Rouge ; C2 Bleu C3 Vert 3 ≤X(G)≤5
sommet 2 4 5 6 7 3 1
Degré 4 4 4 4 4 2 2
DSAT 4 4 4 4 4 2 2
C1 1 1 1 1
C1 1
C2 2 2 2
C2 2
C3
C3
C3
0.25 sur chaque couleur correcte (0.25 * 7 = 1.75)
Le nombre de jours : 3jours 0.25
La proposition ; 0.5
Jour 1’agences 7, 3, 1
Jour 2 l’agences 5 et 4
Jour 3 l’agences 6 et 2
5/4
