INFO EX spé bac 2009

                    EX DE BAC  ES    SPE           France     2009   

  EXERCICE 

           Le graphe ci-dessous représente le plan d'une ville.

           Le sommet A désigne l'emplacement des services techniques.

           Les sommets B , C , D, E , F et G  désignent les emplacements des jardins publics.

          Une arête représente l'avenue reliant deux emplacements et est pondérée

           par le nombre de feux tricolores situés sur le trajet.

                       3352hamospi

         Proposer un trajet, comportant un minimum de feux tricolores, reliant A à G

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

     REPONSE

                  Faisons le tableau de Moore-Dijkstra pour le graphe pondéré donné

            12valofdersi 3

     Conclusion : Un trajet, comportant un minimum de feux tricolores, reliant A à G est 

                         ACEFG comportant 7 feux tricoores.

             4789jhgfds

       1458hqpo

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