INFO EX 00 SUR LES GRAPHES

INFO         EX 00     GRAPHES              MARS 09  BTS1    SUJET 2000N

 EXERCICE 1  .

      1. Graphe orienté simple du site.

    2. Vérification que la matrice M proposée est la matrice d'adjacence du graphe.

        On a les arc orienté : ( A, B )    ( B , A )

                                           ( A , C )    ( C , A )

                                           ( A , D )    ( D , A )

                                    et   ( B , E )  ( E , A )  ( E , C )

       Il est donc normal que la matrice d'adjacence du graphe soit:

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

    3. Calcul des matrices M[ 2 ]   et M[ 3 ]   .

   /    1       0       0       0       1    \
 /      1       1       1       1       0      \
 M[ 2 ]   = |        0       1       1       1       0       |
 \      0       1        1       1       0      /
   \    1       1       1       1       0    /

      

   /    1       1       1       1       0    \
 /      1       1       1       1       1      \
M[ 3 ]   = |        1       0       0       0       1       |
 \      1       0        0       0       1      /
   \    1       1       1       1       1    /

 On admet que :

   /    1       3       4       3       0    \
 /      4         1       1       1       1      \
M3   = |        3       0       0       0       1       |
 \      3       0        0       0       1      /
   \    3       1       1       1       1    /

  a. Donnons le nombre de chemins de longueur 3 d'origine B et d'extrémité A.

     Dans la matrice M3    le terme de rang ( 2 , 1 ) est  4 

     Donc il existe   4 chemins de longueur 3 d'origine B et d'extrémité A.

     Faisons l'inventaire de ces 4 chemin:    BABA         BACA      BADA       BECA

    b. Dénombrons les circuits de longueur 3.

        Dans la matrice M3    on rencontre trois fois  1 dans la diagonale principale.

        Ils sont de rang  ( 1 , 1 )  ( 2 , 2 ) et ( 5 , 5 ).

        Il y a donc trois circuits de longueur 3.

      (  C'est-à-dire chemins de longueur 3 qui reviennent au point de départ.) .

         L'un part de A et revient  A .         C'est :  ABEA       

         L'un part de B  revient en B .          C'est  : BEAB

         L'un part de E revient en E.            c'est :  EABE

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