CI-1
TP Recherche Opérationnelle
2022 - 2023
But du TP :
Dans ce TP, on se propose d’implémenter des graphes en langage Python ainsi que
certaines fonctionnalités de base de manipulation des graphes.
On étudiera également des problèmes d’optimisation sur les graphes en s’appuyant sur
des algorithmes standards et d’autres spécifiques.
Exercice 1
On considère le graphe symétrique pondéré G suivant :
Partie I :
On souhaite implémenter et manipuler ce graphe en utilisant le langage Python.
1. Donner A la matrice d’adjacence de ce graphe.
2. Implémenter cette matrice sur Python en utilisant obligatoirement le module NymPy
et afficher le résultat obtenu.
3. Ecrire une fonction degres(M) qui prends en argument la matrice d’adjacence M d’un
graphe et qui retourne les degrés de ses sommets. Appliquer cet algorithme sur le
graphe G précédent.
4. Ecrire une fonction eulerien(M) qui prends en argument la matrice d’adjacence M
d’un graphe et qui permet de détecter si le graphe est eulérien, semi-eulérien ou
non. Appliquer cet algorithme sur le graphe G précédent et sur d’autres graphes de
votre choix.
TP Recherche Opérationnelle
Partie II :
5. Implémenter la fonction Dijkstra(S, M) permettant de déterminer les plus courts
chemin du sommet S vers le reste des sommets du graphe de matrice d’adjacence M.
6. Afficher le résultat obtenu par l’exécution de la fonction précédente sur le graphe
précédent en prenant comme sommet racine S=0.
7. Modifier la fonction précédente pour afficher l’arborescence des plus courts chemins
issus du sommet S. Afficher le résultat obtenu par l’exécution de cette fonction sur le
graphe précédent.
8. Donner une présentation claire de l’algorithme Floyd-Warshall.
9. Implémenter la fonction FloydWarshall(M) avec M représente la matrice d’adjacence
d’un graphe. Donner son exécution sur le graphe précèdent.
Exercice 2
Dans un parcours de certification, chaque étudiant dispose d’un score de 100 points au
départ. Par la suite, il peut faire des transitions d’un niveau vers un autre niveau de
certification selon les possibilités données par le graphe ci-dessous. A chaque transition son
score est multiplié par la valeur présente sur l’arc.
Par exemple, si un étudiant réalise le parcours 1 -> 2 -> 6 -> 8, son score final sera comme
suit : score_final = 100 x 2 x 6 x 10 = 12000
10. Implémenter un algorithme permettant de déterminer le parcours permettant
d’obtenir le meilleur score. Expliquer toutes les étapes nécessaires.
11. Donner le résultat de l’exécution de cet algorithme sur le graphe précédent.
Commenter le résultat obtenu.