INFO EXERCICE de bac du TEST

               INFO  EXERCICE DE BAC SUR LES MATRICES.      TES  SPE       27/01/14

    EXERCICE  

       Le réseau de lignes de bus d'une ville touristique comporte

       huit intersections de ces lignes, en des lieux à visiter.

       Il est rès dense en centre-ville, mais les problèmes de circulation

       augmentent les temps de trajet dans le centre, sauf aux heures creuses.

       Les lignes périphériques semblent plus rapides.

       Le graphe ci-dessous représente le réseau de bus de cette ville:

        Gr478

        1. Dire , en justifiant la réponse, si les affirmations suivantes sont vraies ou fausses:

            a. L'ordre du graphe est égal au plus grand des degrés de ses sommets.

                Réponse : Non. L'ordre du graphe est le nombre de sommets.

                                 Ici l'ordre du graphe est donc 8.

            b. Le sous graphe bcdg est complet.

              Réponse:   OUI. Les sommets sont deux à deux adjacents.

          Sousgraphe

     c. Les sommets peuvent être coloriés en trois couleurs sans que deux

          sommets adjacents soient de la même couleur.

          Réponse:  NON.   Il faut déjà 4 couleurs pour colorier le sous graphe complet  bcdg.

     d. Il est possible de parcourir ce graphe en utilisant toutes les lignes

         une et une fois et une seule.

        Réponse:    Faisons le tableau des degrés des sommets:

Sommets    a    b    c    d    e   f     g    h 
 Degrés 2 5 4 5 3 2 4 3

                 Le graphe est connexe car deux sommets quelconques

                 sont reliés par un chemin au moins. Il est non orienté et simple .

                 Le nombre de sommets de degré impair n'est ni 0 ni 2 puisqu'il y en a 4.

                 D'après le Th.d'Euler il n'existe pas de chaîne eulérienne.

                 Donc on ne peut pas  parcourir ce graphe en utilisant

                toutes les lignes  ( c-à-d arêtes) une et une fois et une seule.

                   Conclusion:  NON

   2. Vus le problèmes de circulation, une nouvelle ligne est ouverte

       entre les points d et h.

        Gr4785

      Stéphaie visite la ville.

    a. Proposer un circuit d bus qui permette à stéphanie de visiter les huit lieux

       touristiques de la ville en partant du centre- ville  et qui lui permette

      de revenir en d.

          Réponse:    On veut un circuit de d à d qui passe au moins une fois

                             par chaque sommet.

                 On peut considérer:

                          Conclusion:      d b a c g b e h f d

    b. En plus des lieux touristiques aux huit point indiquées, toutes ls lignes de bus

      passent devant des bâtiments historiques de la ville.

      Stéphanie peut-elle utiliser toutes les lignes de bus une fois et une seule ?

           Réponse:   On a rajouté une arête d h.

           Cela change les degrés des sommets h et d.

            Donnons le nouveau tableau des degrés.

Sommets    a    b    c    d    e   f     g    h 
 Degrés 2  5  4  6   3   2 4 4

            Le graphe est toujours non orienté simple et connexe.

           Il y deux sommetsseulement  b et e qui sont de degré impair.

            Donc d'après le Th. d'Euler il existe un chemin eulérien entre b et e.

            Conclusion : OUI . Stéphanie peut utiliser toutes les lignes de bus une fois et une seule

                                 entre les sommets b et e.

           Si oui, en quels lieux doit-elle prendre le bus?

                 Réponse: Elle prend le bus en b ou e

            Peut-elle revenir en son point de départ?

             Réponse: Non . Le chemin eulérien est entre b et e

       3. Stéphanie loge chez une amie et prend le bus à la station a.

           Elle désire aller au point h.

          Le graphe ci-dessous donne le réseau complet et chaque arête est pondérée

          par la durée du parcours, en minutes, entre deux points d'intersection

          ( correspondances comprises )  aux heures creuses.

   Gr47856

          A l'aide d'un algorithme, déterminer le trajet le plus court en durée

         permettant à stéphanie d'aller de la station a à la station g.

         Présenter l'algorithme utilisé.

          Réponse:   Utilisons l'algorithme de Moore -Dijstra.

             Tableau:

       Mooresty

        g ← h( 35) ← e( 30) ← b(26) ← a ( 20 ) ← a

             Conclusion :       a b e h g    de 35 mn

         Gr4785612

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