INFO TEST TES SPE 01/12/14

                          INFO TEST      Spé maths    Lundi 1 décembre 2014

     EXERCICE 

             On considère une partie du réseau d'autoroutes de la ETIRF.

             147fdzer

          1. Tracer un graphe non orienté simple de sommets ABCDEFG 

             qui représente ce réseau.

                 On peut considérer:

                 167hacl  

        2. Quel est l'ordre de ce graphe?

                       Il est d'ordre 7 puisqu'il a 7 sommets.

        3. Ce graphe est-il connexe ?

          OUI car entre deux sommets quelconques il existe au moins un sommet.

       4. Est-il complet?

           NON car par exemple C et D ne sont pas adjacents.

       5. Quel est l'ordre m du plus grand sous graphe complet?

           Le plus grand sous graphe complet  est d'ordre m = 3.

           On peut citer FGB. Ses sommets sont deux à deux adjacents.

        6. Donner dans un tableau les degrés de ses sommets.

            Quel est le degré le plus élevé Δ ?

Sommets   A   B   C    D   E    F    G
Degrés  2  4 2 1 2 2  3 

                  Le degré le plus élevé est  Δ= 4

         7. Quel est la somme des degrés des sommets?

                      La somme des degrés des sommets est 16

         8. En déduire le nombre d'arêtes.

             16 / 2 = 8

             Il y a 8 arêtes.

          9. Un automobiliste souhaite  parcourir une seule fois toutes les portions d'autoroutes?

              Est-ce possible? Justifier

                Dans l'affirmative proposer un tel trajet. 

              OUI.

               En effet il y a au moins une chaîne eulérienne

                      d'après le th d'EULER .

                    • Le graphe est connexe (simple )

                    • Le nombre de sommets de degré impairs est 0 ou 2 , ici 2.

                      ( Ce sont les sommets D et  G )

                        Elle relie les sommets G et D.

                       Par exemple on peut citer:

                        GBEACBFGD

                        On peut préférer:

                           DGFBEACBG

               10. Encadrer le nombre chromatique δ ?

                      On a :    m ≤  δ ≤  Δ  +  1

                         c-à-d

                                       3 ≤  δ ≤ 4 + 1

                          c-à-d 

                                       3 ≤  δ ≤ 5

            Le nombre chromatique est compris entr 3 et 5.

           Il faut et il suffit  donc de considérer entre 3 et 5 couleurs pour colorier le graphe.

                11.  Colorier le graphe.   

                      Rangeons dans l'ordre décroissant des degrés les sommets.

                    Deux sommets adjacents ne peuvent pas être de la même couleur.        

Sommets  B   G   A   C   E   F    GD
Degrés  4 3 2 2 2 2  3
Couleurs  VERT   ORANGE   ORANGE  BLEU   BLEU   BLEU  BLEU 

                  1671hacl

                Il a donc suffit de 3 couleurs.

      12. Donner la matrice M  associée ( adjacente ) au graphe.

             On a :

                258laodf

        13 . Trouver à l'aide de la calculatrice les matrices  M3  .

                   On a :            

                            1975fpalh 

                         134gmqazn

           Dans la matrice M3  que représente le terme 6 de rang ( 3 , 2 ).

                   Il y a 6 chemins de longueur 3 qui relient  les sommets C et B.         

  FALCULTATIF

       On considère à présent le graphe précédent pondéré en minutes 

                   de la façon suivante:

                   AE = 11 mn          BG = 5 mn

                   AC  = 7 mn            BF = 20 mn

                    CB = 12 mn         GF = 12 mn

                     EB = 5 mn          GD = 17 mn                              

                     A l'aide d'un algorithme trouver un plus court chemin pour aller

                      du sommet A au sommet F.

                    On a :

                                               14mjkli

                   Faisons un tableau de l'algorithme de Moore

                       1111sde45     

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

          EXERCICE 2

       Résoudre dans IR3 le système suivant:

        x + y + z = 1

        x + 2 y + 3 z = 2

        40 x + 20 y + 10 z = 3

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

         REPONSE:

     Le système s'écrit    M × X = Y

               avec les matrices :

                   2591dmenc

             14937hqoy

     Comme M est une matrice inversible ( det( M ) ≠ 0 ) le 

            système s'écrit :

                  X = M − 1 × Y

         La calculatrice donne alors:

             753159jazet

       Conclusion :  SIR3   = { (  − 1,7   ; 4 , 4    ;    − 1,7  )  }  

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