TEST 5 GRAPHE BTS 2014

                      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.

---------------------------------------------------------------------------------------------------