Title °TD Recherche opérationnelle SMI5 FSSM MARRAKECH.pdf ✅

Université Cadi Ayyad Faculté des Sciences Semlalia Département Informatique Filière : SMI-S6 Année Universitaire 2020-2021 Page 1/2 Recherche opérationnelle TD N°1 Exercice N°1 : Un étudiant distrait s’aperçoit qu’il doit présenter, le lendemain matin, une interrogation portant sur des exercices de recherche opérationnelle. Peut-être a-t-il la possibilité de préparer la matière de deux ou trois chapitres choisis au hasard dans les 12 chapitres du programme ; ces douze chapitres ne sont cependant pas tout à fait indépendants : Le chapitre... 1 2 3 4 5 6 7 8 9 10 11 12 Nécessite la compréhension préalable des chapitres... - 1 1 2 1 2 1 - - - - 8 8 10 8 10 Aider cet étudiant à représenter au moyen d’un graphe la situation (préoccupante) qui est la sienne. Exercice N°2 : Un tournoi oppose n personnes (n pair) ; chaque joueur doit affronter tous les autres joueurs. Construire un graphe représentant toutes les parties possibles de deux joueurs, si n=4 et n=6. (Suite TD2) Exercice N°3 : Trois professeurs P1, P2 et P3 doivent donner ce lundi un certain nombre d’heures de cours à trois classes C1, C2 et C3 : - P1 doit donner une heure de cours à C1 ; - P2 doit donner une heure de cours à C1, deux heures à C2 et deux heures à C3 ; - P3 doit donner une heure de cours à C1 et une heure à C3 ; Comment représenter cette situation par un graphe ? (Suite TD2)
Université Cadi Ayyad Faculté des Sciences Semlalia Département Informatique Filière : SMI-S6 Année Universitaire 2020-2021 Page 2/2 Exercice N°4 : Considérant les graphes définis ci-dessous par leur matrice d’adjacence. - Sont-ils sans boucle ? symétriques ? transitifs ? complets ? - Déterminer leur fermeture transitive. - Sont-ils sans circuit ? si oui, construire leur noyau et les partager en niveaux. A. B. C. D. E. F. . 1 . . . . 1 . 1 . . 1 1 . . .             . 1 1 . . . . 1 . . . . . . 1 .             . . . . 1 . . . . 1 . . . . 1 . . . . 1 1 1 1 1 .                 . 1 . 1 . 1 . 1 . 1 . 1 . 1 . 1 . 1 . 1 . 1 . 1 .                 . . . 1 . . . 1 . 1 . 1 . . . 1 . . . 1 . 1 . 1 .                 . 1 1 1 1 . . 1 . 1 . . . . . . . 1 . 1 . . 1 . .                 Exercice N°5 : Aider l’étudiant de l’exercice 1 à déterminer les chapitres qui lui permettent de voir le plus de matière distincte possible sans devoir lire de chapitres préalables ! Exercice N°6 : Quelles sont les propriétés du graphe associé à l’exercice 1 ? Quelle interprétation peut-on donner aux niveaux ?
Université Cadi Ayyad Faculté des Sciences Semlalia Département Informatique Filière : SMI-S6 Année Universitaire 2020-2021 Page 1/3 Recherche opérationnelle TD N°2 Exercice N°1 : Etablir, dans l’exercice N°3_TD N°1, un horaire s’étalant sur un minimum d’heures. Exercice N°2 : Effectuer une coloration des sommets du graphe G ci-dessous : Exercice N°3 : Un groupe d’étudiants Y doit présenter un certain nombre d’épreuves écrites ; l’ensemble de toutes les épreuves est noté X. Comme il s’agit d’examens écrits, on désire que tous les étudiants qui doivent passer une même épreuve la présentent simultanément. Si un étudiant passe au plus un examen par jour, quelle est la durée minimale de la session ? Exercice N°4 : a) Effectuer une coloration des sommets du graphe G (X, E) ci-dessous : Déterminer des bornes, intérieure et supérieure, pour le nombre chromatiqueγ ( ) G . b) Soit G’(X’, E’) le sous-graphe construit à partir de G en ne conservant que les cinq premiers sommets x1,..., x5. Notons G X E '( ', ') le graphe complémentaire de G’ ( E ' est l’ensemble 1 2 4 3 6 5 7 8 3 5 2 7 1 4 6 8
Université Cadi Ayyad Faculté des Sciences Semlalia Département Informatique Filière : SMI-S6 Année Universitaire 2020-2021 Page 2/3 des couples non ordonnés de sommets de X’ n’appartenant pas à E’). Le graphe G ' est-il biparti ? Exercice N°5 : Deux professeurs x1 et x2 doivent donner certain nombre d’heures de cours à deux classes y1 et y2 : Nombre d’heures de cours à donner a y1 y2 x1 x2 3 2 1 1 Déterminer l’horaire minimal permettant de dispenser ces cours. Exercice N°6 : Déterminer un arbre partiel de poids minimum dans le graphe valué ci-dessous (les nombres associés aux arêtes représentent les poids de ces arêtes) : 3 2 7 1 4 8 6 5 9 1 7 2 8 9 12 14 13 16 5 15 6 11 3 10 4