INFO ACTIVITE GRAPHE

  INFO ACTIVITE                  MARS                 2009       GRAPHE ORIENTE

  NOM:  ............                  PRENOM: ...........                   DATE:  Mars 09.        CLASSE : BTS1

 ACIVITE SUR LES GRAPHES ORIENTES.                

          Soit le graphe orienté G comportant les sommets A B C.

        

     1. A l'aide de la simple vue du graphe G dire si :

       a. Le graphe G admet ou n'admet pas  un chemin de longueur 2 :  OUI   

           C'est   le chemin A B C  qui joint A à C.

       b.  Le graphe admet ou n'admet pas un chemin de longueur 3 :  NON

      2. a.Compléter le tableau :

PREDECESSEURS     SOMMETS SUCCESSEURS
          A         B
               A           B         C
               B           C

         b. Compléter le tableau donnant les niveaux des sommets.

      PREDECESSEURS     SOMMETS NIVEAUX
          A          0
                   A            B           1 
                   B            C         2  

     On procédera de la façon suivante:

      •   Un sommet sans prédécesseur est de niveau  0.

      •  Dans la première colonne barrer les sommets sans prédécesseur.

      •   Tout sommet de la colonne centrale qui n'a alors plus  de sommet

          dans la colonne prédécesseur est de niveau 1.

       •   Dans la première colonne barrer à présent les sommets de niveau 1.

          Tout sommet de la colonne centrale qui n'a alors plus  de sommet

          dans la colonne prédécesseur est de niveau 2.

          etc.

       (  ON NE CONSIDERE LES NIVEAUX DES SOMMETS

         que dans les graphes sans boucle ( pas d'arc avec les mêmes sommets ) et

         sans circuit ( pas de chemin revenant au même sommet

     3.  Compléter le tableau suivant: 

          Mettre 1   s'il y a   un arc du sommet de départ au sommet d'arrivée,

          sinon mettre 0.   

 DEPART    \    ARRIVEE         A        B       C
                    A          0               1                 0      
                    B          0          0            1
                    C          0         0           0        

     4. En déduire la matrice M d'adjacence du graphe G.

    (  Pour l'obtenir extraire les neuf chiffres du tableau précédent sans modifier leur place.)

          M =

 /      0                 1            0    \
|        0                  0      1      |
 \       0                0    0     /

      5. Trouver la  matrice M².

            M²  =

 /       0           0            1    \
|         0           0      0      |
 \       0            0      0    /

    Retrouver la réponse à la question 1.a.

            Le    1          permet de répondre OUI . 

            Il y a un chemin de longueur 2  de A à C.

           C'est     A B C

      6.   Trouver la matrice M3   .

                   M3     =

 /       0           0            0   \
|         0           0      0     |
 \       0           0      0   /

         Retrouver la réponse à la question 1.b.

         Il n'y a aucun 1 dans cette matrice   M3   donc il n'y a aucun chemin de longueur 3 .

    7. Sur le graphe G  ,ci-dessous, rajouter le ou les raccourcis éventuels  en couleur.

        ( Un raccourci est un arc qui relie directement deux sommets déjà reliés par un chemin. ) 

 

            On note G'  le graphe ainsi complété. ( On dit  que G ' est la fermeture transitive de G  )

    8. Compléter le tableau suivant pour le graphe G'.

 DEPART    \    ARRIVEE         A        B       C
                    A           0               1                  1   
                    B           0            0              1    
                    C           0            0         0      

    9.Donner alors la matrice d'adjacence M' du graphe G'.

               M ' =  

 /       0              1                1    \
|         0              0        1      |
 \       0              0        0     /

    10.  On note M [ 2 ]    la matrice obtenue en remplaçant par 1

     tout terme non nul de  la matrice M ² et en laissant tous les termes nuls.

         M [ 2 ]     = 

 /        0             0               1     \
|         0            0       0        |
 \       0          0       0       /

        La matrice   M [ 2 ]    est dite booléenne car elle ne peut avoir que des 0 ou des 1.

       Ce qui peut ne pas être le cas pour la matrice M².    (    ICI   ON RETROUVE M²     )

       11.   Trouver la matrice M  (+)   M [ 2 ]    . (  On considère la somme booléenne (+) 

                des termes des deux matrices )

              M  (+)   M [ 2 ]   =         

 /      0       1     0       \  /   0 0    1    \   /  0 1   1    \
|      0       0     1        |        (+) |    0 0    0     | = |    0 0   1     |
 \      0       0     0      /  \    0 0    0    /  \   0 0    0   /

                 Il apparaît  que  M  (+)   M [ 2 ]   =   M'  

                et aussi   ici    M  (+)   M [ 2 ]   (+)   M [ 3 ]   =   M'  

               C'est une façon d'obtenir la matrice d'adjacence M' de

               fermeture transitive du graphe.