TEST GRAPHES BTS1 29 janvier 2014
EXERCICE
Dès leur arrivée à 8 h dans un garage, les deux employés Bertand et Didier
consultent les différentes opérations qui seront à effectuer sur
différents véhicules.
Les opérations, qui sont notées A B C D E F G H J K L, ne se font pas
dans n'importe quel ordre.
Certaines opérations nécessitent la réalisation d'une ou plusieurs opérations
préalables.
Le gérant, pour la gestion du travail, a conçu le tableau suivant.
| Opérations péalables nécessaires | Opérations | Durée des opérations en mn |
| A | 4 | |
| B | 5 | |
| A | C | 6 |
| B C | D | 10 |
| D | E | 8 |
| D | F | 2 |
| F | G | 3 |
| D | H | 15 |
| C | J | 12 |
| G E | K | 7 |
| J K H | L | 5 |
1. Déterminez les niveaux des différentes opérations.
2.a. Dessiner un graphe de sommets les opérations,
correspondant au tableau, ordonné suivant les niveaux.
b. Donner la matrice d'adjacence du graphe .
3. Bertand a été désigné pour accomplir sur un véhicule les opérations
de A jusqu'à L.
A quelle heure, au mieux, aura- t- il terminé son travail ?
4. Didier a été désigné pour accomplir sur un autre véhicule l'opération B et
toutes les suivantes lui permettant de terminer par l'opération L.
Combien de temps mettra t- il au pire pour réaliser ce travail ?
5. Donner la matrice de la fermeture transitive du graphe.
Dessiner le graphe avec les raccourcis.
---------------------------------------------------------------------------------------------------