ACTIVITE GRAPHES ORIENTES

   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 :   .................

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

      2. a.Compléter le tableau :

PREDECESSEURS     SOMMETS SUCCESSEURS
                A   
               B     
                 C  

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

      PREDECESSEURS     SOMMETS NIVEAUX
                A     
                B    
                C    

     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                                                          
                    B                                            
                    C                                                 

     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 =

 /                                        \
|                                         |
 \                                     /

      5. Trouver la  matrice M².

            M²  =

 /                                     \
|                                   |
 \                                 /

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

            .................................

      6.   Trouver la matrice M3   .

                   M3     =

 /                                 \
|                               |
 \                            /

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

         .......................................................

       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                                                        
                    B                                                  
                    C                                                

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

               M ' =  

 /                                 \
|                               |
 \                            /

    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 ]     = 

 /                                 \
|                               |
 \                            /

        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².

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

               des termes des deux matrices)

                 Que peut-on dire de   M  (+)   M [ 2 ]   (+)   M [ 3 ]    ?    ......................

                

 /                                 \
|                               |
 \                            /

             

             Que remarquez vous ?

          ..............................................