INFOTEST DEC 09 MATRICE-GRAPHE

   INFO TEST               NOM : X           Prénom :   X Date:  Déc.         Classe: BTS

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

Soit G un graphe de sommets ABCDEF. Le tableau des prédécesseurs est :

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

•• Donner la matrice M adjacente à G. 

 Il y a 7 arcs  et 6 sommets.   

  / 0 1 1 0 0 0   \
| 0 0 0 1 1 0    |
| 0 0 0 0 1 0    |
M  = | 0 0 0 0 0 1    |
| 0 0 0 0 0 1    |
   \ 0 0 0 0 0 0   /

•• Déssiner G.

                                     

.•• Trouver M2

 

  / 0 0 0 1 2 0   \
| 0 0 0 0 0 2    |
| 0 0 0 0 0 1    |
M²  = | 0 0 0 0 0 0    |
| 0 0 0 0 0 0    |
   \ 0 0 0 0 0 0   /

 

 •• Trouver M3

 

  / 0 0 0 0 0 3   \
| 0 0 0 0 0 0    |
| 0 0 0 0 0 0    |
M3  = | 0 0 0 0 0 0    |
| 0 0 0 0 0 0    |
   \ 0 0 0 0 0 0   /

 

•• Y a-t-il des chemins de longueur 2 ? Précisez les.

 Il y en a:     1 + 2+ 2+1  = 6

      Il y en 1 de A à D :      ABD 

      Il y en a 2 de A à E :    ABE     ACE 

      Il y en a 2 de B à F :     BDF      B EF      

      Il y en a 1 de C à F:       CEF       

•• Combien y a -t-il de chemins de longueur 3 arrivant à B ?

Il y en a  0  car la colonne de B dans M3  n'a que des 0.

•• Donner les niveaux des sommets.

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

  •  Résoudre  dans IR3 le système :

     2 x - 3 y + z = 6         L1

      x + 2 y + 3 z = 2       L2

       x + 2  y + z = 0        L3

  Considérons  L2     ↔       L1     

  On obtient le système équivalent suivant:

       x + 2 y + 3 z = 2      L1   

         2 x - 3 y + z = 6         L2       

          x + 2  y + z = 0       L      

     Considérons:

                   L2     ←       L2     -   2   L1    

                 L      ←       L3     -      L1     

   On obtient le système équivalent suivant

     x + 2 y + 3 z = 2           L1   

            - 7 y - 5 z = 2           L2       

                     - 2 z =  - 2       L  

    Alors :       L     donne  z = 1

        Puis     L2       donne     - 7 y = 2 + 5 z = 2 + 5 = 7

                                              y = - 1

          Enfin      L1       donne x = 2 - 2 y - 3 z = 2 + 2 - 3 = 1

                                             x = 1         

    Conclusion :  SIR3 ={ ( 1 ; - 1 ; 1 ) }