TD Série 3 Mathématiques II Recherche Opérationnelle PDF

Module : Mathématiques II EST Khénifra Élément : Recherche Opérationnelle Filière : GI (S3) TD : Série 3 Exercice 1 On considère la matrice suivante...

Module : Mathématiques II EST Khénifra Élément : Recherche Opérationnelle Filière : GI (S3) TD : Série 3 Exercice 1 On considère la matrice suivante   0 1 1 1 0 1   1 0 1 1 1 1   1 1 0 1 1 0     M=     1 1 1 0 1 1   0 1 1 1 0 1     1 1 0 1 1 0 1. Construire un graphe non orienté G, dont M est sa matrice d’adjacence. 2. calculer d(3). 3. Montrer que G n’admet pas de cycle Eulérien. 4. Montrer que G admet une chaine Eulérienne. Déterminer une telle chaine. 5. Calculer M 2 , et déduire le nombre des chaines de longueur 2, qui relient les sommets 3 et 5. Exercice 2 Soit le graphe orienté valué suivant 1. Appliquer l’algorithme de Dijkstra sur ce graphe. 2. Justifier pourquoi ce graphe peut être vu comme un réseau. 3. En utilisant l’algorithme de Ford-Fulkerson, calculer le flot maximale qui peut circuler dans ce réseau. Exercice 3 On considère le graphe orienté valué G suivant : 1. Donner la matrice d’adjacence M du graphe G. 2. Calculer d+ (2) et d− (5). 3. Calculer M 2 , et déduire le nombre de chemins de longueur 2 qui relient les sommets 1 et 5. 4. Dans cette question on regarde G comme un graphe non-orienté : montrer que G n’admet pas de cycle Eulérien mais il admet une chaine Eulérienne. Déterminer une telle chaine. 5. En utilisant l’algorithme de Dijkstra, Donner les plus courts chemins allant de 1 aux autres sommets. 6. Justifier pourquoi on peut considérer G comme un réseau. 7. En utilisant l’algorithme de Ford-Fulkerson, calculer le flot maximale qui peut circuler dans ce réseau, et déterminer une coupe minimale dans ce cas.