Téléchargez comme DOCX, PDF, TXT ou lisez en ligne sur Scribd
Télécharger au format docx, pdf ou txt
Vous êtes sur la page 1/ 4
****** الجمهورية التونسية
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.
