****** الجمهورية التونسية
Ecole Supérieure d'Ingénieurs *******
Privée de Gafsa
****** المدرسة العليا الخاصة للمهندسين بقفصة
Etablissement d'Enseignement *******
Supérieur Privé Agréé par l'Etat مؤسسة جامعية خاصة مرخص لها من طرف
Sous N° 05-2013 2013-05 :الدولة تحت عدد
Niveau II1
Matière TD2: Algorithmique de graphe et Année universitaire 2022-2023
optimisation
Exercice n°1
Première partie : Etude d’un graphe
On considère le graphe ci-dessus.
1) a) Ce graphe est-il connexe ?
b) Justifier l’existence d’une chaîne eulérienne.
2) a) Déterminer un encadrement du nombre chromatique de ce graphe.
Deuxième partie : Visite d’un musée
1
Voici le plan d’un musée : les parties grisées matérialisent les portes et les visiteurs
partent de l’accueil, visitent le musée et doivent terminer leur visite à la boutique.
1) Représenter la situation à l’aide d’un graphe en précisant ce que représentent arêtes
et sommets.
2) Pourquoi est-il possible de trouver une chaine où les visiteurs passent une fois et
une seule par toutes les portes ?
- Donner un exemple d’une telle chaine.
3) Comment colorier les salles y compris l’accueil et la boutique, en utilisant un
minimum de couleurs, pour que 2 salles qui communiquent par une porte aient des
couleurs différentes ?
Exercice n°2
- Pour le graphe pondéré ci-dessus on cherche à trouver l’arbre couvrant
minimum en appliquant l’algorithme de PRIM.
Exercice n°3
2
- On cherche à trouver l’arbre couvrant minimum en appliquant l’algorithme de
PRIM et l’algorithme de Kruskal.
-
Exercice n°4
1- En détaillant bien toutes les étapes, appliquez l’algorithme de Prim et de Kruskal
sur le graphe suivant.
2- Quel est le poids d’un arbre couvrant de poids minimal ?
Exercice n°5
- Appliquer l'algorithme de Prim pour trouver un arbre couvrant de poids
minimum du graphe G représenté sur le graphe suivant.
3
4
