LISTE EX SUR LES GRAPHES

LISTE D'EX.        GRAPHES ORIENTES             BTS            Nov.  08

                         EX.1   

                                Soit le graphe orienté dont les sommets sont ABCDEF et 

                                 les arc sont : ( B , A ) , ( C , A ) , ( D , B ) , ( E , B ) , ( F , D) , ( D , E ).

                               1. Représenter G.

                               2. Donner le tableau des prédécesseurs.

                               3. Compléter ce tableau en donnant le niveau de

                                  chaque sommet, si possible( c-à-d  s' il n'y a pas de boucle ni de circuit.)

                              4. Donnner la matrice d'adjacence M de G.

                               5. Refaire la représentation du graphe  G en ordonnant ses

                                  sommets suivant leur niveau. 

                               6. Trouver les matrice M2  , M,  M  , M5  .

                             7.  a. Trouver la matrice de la fermeture transitive du graphe G en

                                      faisant la somme booléenne des matrices :

                                     M ,  M[2]  , M[3]  ,  M[4]    M[5]  .

                                  b. Trouver M[6] . 

                             8. Représenter le graphe de la fermeture transitive de G.

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

            EX.  2        Soit le graphe orienté T dont les sommets sont ABCDEFG et 

                           dont les arcs sont:  ( C , B ) , ( D , A ) , ( E , C ) , ( E , D ) 

                               ( F , D ) , ( G , E )  , ( G , F )   .

                    1. Faire le tableau des prédécesseurs.

                   2.  Compléter le tableau par les niveaux. (  si possible. )