Contrôle RO 17 SEER2 - ENSET

ECOLE NORMALE SUPÉRIEURE DE ‫ﺍﻟﻤﺪﺭﺳﺔ ﺍﻟﻌﻠﻴﺎ ﻸﺳﺎﺗﺬﺓ ﺍﻟﺗﻌﻠﻴﻢ ﺍﻟﺗﻘﻨﻲ‬
L'ENSEIGNEMENT
TECHNIQUE DE MOHAMMEDIA
ENSET ‫ﺍﻟﻤحﻤﺪﻴﺔ‬
UNIVERSITÉ HASSAN II DE CASABLANCA ‫ﺟﺎﻤﻌﺔ ﺍﻟحﺳﻦ ﺍﻟﺜﺎﻨﻲ ﺑﺎﻟﺪﺍﺭ ﺍﻟﺑﻴﻀﺎﺀ‬
Contrôle de Recherche Opérationnelle 1
Problème : Graphes, Algorithmes et Modélisation.

N.B. Les deux parties du problème sont totalement indépendantes.
I. Généralités sur les graphes.
Considérons le graphe orienté ( ) donné à la figure 1.
Figure 1.
1) Donner la matrice d’adjacence, , du graphe de la figure 1.
2) En appliquant l’algorithme de Warshall version graphe, déterminer la fermeture transitive
du graphe En déduire la matrice d’adjacence de la fermeture transitive .
3) En appliquant l’algorithme de Warshall cette fois-ci version matrice, déterminer la matrice
d’adjacence de la fermeture transitive du graphe Conclure.
II. Algorithmes et modélisation.

A. Algorithmes de Parcours et Tri-Topologique
La construction d’un entrepôt peut se décomposer en 10 tâches comme le monte le graphe
orienté de la figure 2.
Les significations des différentes tâches sont rappelées dans le tableau suivant :
Tâches Significations
A Acceptation des plans par le propriétaire
B Préparation du terrain
C Commande des matériaux
D Creusage de fondation
E Commande des portes et fenêtres
F Livraison des matériaux
G Coulage de fondation
H Livraison des portes et fenêtres
I Pose des murs
J Mise en place des fenêtres
Adresse : BP 159 Bd Hassan II, ‫ ﺷﺎﺭﻉ‬،159 ‫ ﺻﻨﺪﻭﻕ ﺍﻟﺒﺮﻳﺪ‬: ‫ﺍﻟﻌﻨﻮﺍﻥ‬
Mohammedia - Maroc ‫ ﺍﻟﻤﺤﻤﺪﻳﺔ‬،‫ﺍﻟﺤﺴﻦ ﺍﻟﺜﺎﻧﻲ‬
Tél : 0523322220 0523322220 : ‫ﺍﻟﻬﺎﺗﻒ‬
Fax : 0523322546 0523322546 : ‫ﺍﻟﻔﺎﻛﺲ‬
Site web : www.enset-media.ac.ma www.enset-media.ac.ma
L'ENSEIGNEMENT
Figure 2.
1) Simuler l’exécution de l’algorithme de parcours DFS version machine sur le graphe
donné en figure 2.
2) En appliquant le tri-topologique au graphe de la figure 2, donner un ordonnancement
des tâches et tracer le graphe ainsi ordonné.
3) Simuler l’exécution de l’algorithme BFS sur le graphe de la figure 2. En déduire
l’arborescence de parcours ordonnée.
B. Arborescences des Plus Courts Chemins.

Numérotons les sommets du graphe G  (V , E ) de 1 à n. Supposons que l’on s’intéresse aux
chemins partant du sommet 1. On construit un vecteur   1 ; 2 ;; n  ayant n composantes
tel que  j soit égal à la longueur du plus court chemin allant de 1 au sommet j. On initialise
ce vecteur à , c’est-à-dire à la première ligne de la matrice des coûts du graphe, définie
comme indiqué ci-dessous :
{ ( )
( ) ( )
où ( ) est le poids de l’arc ( )
On construit un autre vecteur p pour mémoriser le chemin pour aller du sommet 1 au sommet
voulu. La valeur p(i) donne le sommet qui précède i dans le chemin.
On considère ensuite deux ensembles de sommets, S initialisé à {1} et T initialisé à {2,3, . . .,
n}. A chaque pas de l’algorithme, on ajoute à S un sommet jusqu’à ce que de telle
sorte que le vecteur λ donne à chaque étape la longueur minimale des chemins de 1 aux
sommets de S.

Tél : 0523322220 0523322220 : ‫ﺍﻟﻬﺎﺗﻒ‬
Fax : 0523322546 0523322546 : ‫ﺍﻟﻔﺎﻛﺲ‬
L'ENSEIGNEMENT
Algorithme Machin
3
On suppose que le sommet de départ est le sommet numéroté 1. Notons qu’on peut toujours
renuméroter les sommets pour que ce soit le cas.
() ;
( )
( )
* + * +
é
’
()
’ à
( ) () ( )
( ) () ( )
( )
1. Appliquer l’algorithme Machin au graphe de la figure 3.

2. Déterminer le chemin de valeur minimale allant de X 1 à X 6 .
3. Montrer à l’aide d’un contre exemple que cet algorithme n’est pas applicable lorsque
certaines valuations sont strictement négatives.
4. Modifier l’algorithme pour la recherche d’un chemin de valeur minimale de X 1 vers
un sommet donné X k .
Figure 3
Tél : 0523322220 0523322220 : ‫ﺍﻟﻬﺎﺗﻒ‬
Fax : 0523322546 0523322546 : ‫ﺍﻟﻔﺎﻛﺲ‬

Contrôle RO 17 SEER2 - ENSET

Transféré par

Droits d'auteur :

Formats disponibles

Contrôle RO 17 SEER2 - ENSET

Transféré par

Informations du document

Titre original

Copyright

Formats disponibles

Partager ce document

Partager ou intégrer le document

Options de partage

Avez-vous trouvé ce document utile ?

Ce contenu est-il inapproprié ?

Droits d'auteur :

Formats disponibles

Contrôle RO 17 SEER2 - ENSET

Transféré par

Droits d'auteur :

Formats disponibles

ECOLE NORMALE SUPÉRIEURE DE ‫ﺍﻟﻤﺪﺭﺳﺔ ﺍﻟﻌﻠﻴﺎ ﻸﺳﺎﺗﺬﺓ ﺍﻟﺗﻌﻠﻴﻢ ﺍﻟﺗﻘﻨﻲ‬

Contrôle de Recherche Opérationnelle 1

Problème : Graphes, Algorithmes et Modélisation.

II. Algorithmes et modélisation.

B. Arborescences des Plus Courts Chemins.

où ( ) est le poids de l’arc ( )

Adresse : BP 159 Bd Hassan II, ‫ ﺷﺎﺭﻉ‬،159 ‫ ﺻﻨﺪﻭﻕ ﺍﻟﺒﺮﻳﺪ‬: ‫ﺍﻟﻌﻨﻮﺍﻥ‬

1. Appliquer l’algorithme Machin au graphe de la figure 3.

Vous aimerez peut-être aussi