INFO TEST BTS1 B 21 janvier 2015

              INFO     TEST  BTS 1B    Matrices et Graphes     21 janvier 2015

    EXERCICE  1

      1.  Résoudre le système suivant en le triangularisant:

           x + 2 y + 5 z = 8                 L1

           2 x + 5 y + 3 z = 10           L2

           2 x + y − z = 2                    L3

       2.  a. Ecrire sous forme matricielle le système précédent.

            b. Résoudre dans  IR 3  le système précédent à l'aide de la calculatrice.

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

  REPONSE:

          1. Le système s'écrit en considérant

                               L 2    ←   L2 − 2 L 1           L 3    ←   L3 − 2 L 1     

           x + 2 y + 5 z = 8                       L1

                    y − 7 z = − 6                    L2

                − 3 y −11 z =  − 14              L3  

     c-à-d      en considérant          L 3    ←   L3  +  3 L 2 

            x + 2 y  + 5 z   = 8                    L1

                    y −   7 z   =  − 6                 L2

                        − 32  z = − 32                L3  

        L 3       donne  z = 1

      Puis L 2 donne y = − 6 + 7 z = 1

      Enfin    L1  donne   x = 8 − 5 z  −2 y =  8 − 5 − 2 = 1

             Conclusion :   S =  { ( 1 ; 1 ; 1 ) }

      2. Le système s'écrit  sous la forme matricielle:   M X = Y

             On a :

                    Bt4 

        b.Utilisons la calculatrice :

                Det( M ) ≠ 0

            Donc   X =   M − 1 × Y

                    Bt3

             Même conclusion que dans la première question.

              c-à-d 

                  Conclusion :   S =  { ( 1 ; 1 ; 1 ) }

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

    EXERCICE 2

        1. Soit G un graphe orienté de six sommets ABCDEF.

                 On admet que le graphe ne comporte pas de

                 chemin fermé.  soit M sa matrice d'adjacence.

            a.  Combien de sommets distincts ou confondus faut-il considérer pour

                 donner un chemin de longueur 3 s'il en existe?

               REPONSE:

                 Conclusion:

                Il faut citer  4 sommets distincts ou confondus.

            (    Il y a 3 arcs donc 3 intevalles donc 4 sommets à citer.

                  Ici si l'ontient compte qu'il n'y a pas de chaîne fermée

                  il faudra 4 sommets distincts)

            b. Peut-on trouver un chemin de longueur 6 ? Justifier.

                Que peut-on en déduire pour M6   ?

                  REPONSE:

                   Un chemin de longueur 6    nécessite de citer 7 sommets distincts ou confondus.

                  Or le graphe a 6 sommets . Donc pour  citer 7 sommets  il faut répéter

                   au moins deux fois l'un d'entre eux. On est obligé de repasser par un même sommet.

                   Il y a donc une chaîne fermée qui est crée. Ce qui est contraire aux hypothèses.

                      Conclusion:    Non il n'y a aucun chemin de longueur 6.

                     Par conséquent M6 est la matrice nulle.

         2. On admet à présent que le graphe G possède les arcs suivants:

              ( A , B ) ; ( A , C ) ; ( C , F ) ; ( C , B ) ; ( B , D ) ; ( D , F ) ; ( E , F ) ; ( E , B )

            a. Donner la matrice M.

                  REPONSE:

                    Conclusion:

                     We56

            b. Commet peut-on interpréter les colonnes de zéros de M ?

                 REPONSE:

                  Conclusion:

                 Il n' y a aucun chemin qui arrive à A ni à E.

         3. Ce graphe G possède-t-il une boucle?

              REPONSE:

             Il n'y a aucun 1 dans la diagonale principale de M

              Conclusion : NON

         4.  Donner le tableau des prédécesseurs et des niveaux de G.

                   REPONSE:           

Prédécesseurs  Sommets   
  A
A C E B
A   C
B D
  E
CDE F

 

Prédécesseurs  Sommets  Niveaux 
  A    0
     A     C   E  B    2 
      A  C    1
     B  D   3 
  E    0
   C   D   E  F    4

         5. Faire le dessin de G en l'ordonnant suivant les niveaux.

                 REPONSE:

        We60 1

         6.a.Donner les matrices M2 , M2 , M3 , M4  ,  M5  ,  M6  .

                    REPONSE:

                    We66

                      We68 

                      We70

                       M5 = 0  matrice nulle

                      M6  = 0   matrice nulle

             b. Combien de chemins de longueur 4  a-t-on ?

                  Il y a un unique terme de M4  qui est non nul. c'est 1.

                     Conclusion:  Il y a un seul chemin de longueur 4.

         7. Reproduire le graphe G en mettant cette fois tous les raccourcis en couleur.

                  REPONSE:

              We160

         8.  Calculer la somme booléenne :                        

                        Ne4 

                On obtient :

   We241

                              We81

                    Il y a donc 5 raccourcis.

         9. On donne à présent les distances suivantes en Km.

               AB = 5     AC = 3    CF = 20   CB = 7     BD 11    DF = 7  EF = 30   EB = 15 

             Donner en le justifiant un chemein de A à F qui soit de plus petite

                 distance en Km.

                 We601

                  Faisons un tableau de Moore-Dijkstra

 We456

  We578

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