INFO LISTE EX SUR LES GRAPHES

 INFO LISTE D'EX SUR LES GRAPHES        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.

PREDECESSEURS          SOMMET NIVEAUX
                  B    C                   A      
                 D          E                   B     
                         C    
                       F                   D     
                  D                   E     
                      F    

                   Le nombre de prédécesseurs indique le nombre d'arcs et ainsi le nombre de 1 dans la matrice d'adjacence

                    du graphe.  Ici il y a   6 arcs.

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

PREDECESSEURS          SOMMET NIVEAUX
             C                                    B                         A             4
                         D            E                    B             3
                  C             0
           F                     D             1
                        D                      E             2
                  F           0

                •   C  et F n'ont pas de prédécesseur.  C et F sont donc de niveau 0 .

                     On barre C et F dans la colonne des prédécesseurs.

                •   Le sommet D n'a plus de prédécesseurs dans la colonne de gauche.

                    Donc D est de niveau 1.

                   On barre D dans la colonne des prédecesseurs. 

                 •   Le sommet E n'a plus de prédécesseurs dans la colonne de gauche.

                      Donc E est de niveau 2 .

                    On barre E dans la colonne des prédecesseurs. 

                    •    Le sommet B n'a plus de prédécesseurs dans la colonne de gauche.    

                         Donc B est de niveau 3.

                        On barre B dans la colonne des prédecesseurs. 

                    •      Le sommet A n'a plus de prédécesseurs dans la colonne de gauche.       

                            Donc A est de niveau 4.

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

                       Le tableau suivant permet de faire apparaître la matrice d'adjacence.

                      Il n'est pas obligatoire.

ORIGINE           \      EXTREMITE A B C D E F
                  A 0 0 0 0 0 0
                  B 1 0 0 0 0 0
                  C 1 0 0 0 0 0
                  D 0 1 0 0 1 0
                  E 0 1 0 0 0 0
                  F 0 0 0 1 0 0

           Chaque fois qu'un arc existe il y a 1 sinon 0.

            Ma matrice d'adjacence du graphe est donc:

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

                                  sommets suivant leur niveau. 

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

 

 

                               6. Trouver les matrice M2  , M3  ,  M4   , M5  .

 On a :

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

     /   0 0     0    0   0    0  \
 /       0 0 0 0 0 0     \
|        0 0 0 0 0 0       |
M3   = |        1 0 0 0 0 0       |
 \       0 0 0 0 0 0     /
    \    1 1 0 0 0 0  /

 

     /   0 0     0    0   0    0  \
 /       0 0 0 0 0 0     \
|        0 0 0 0 0 0       |
M4   = |        0 0 0 0 0 0       |
 \       0 0 0 0 0 0     /
    \    1 0 0 0 0 0  /

     /   0 0     0    0   0    0  \
 /       0 0 0 0 0 0     \
|        0 0 0 0 0 0       |
M5   = |        0 0 0 0 0 0       |
 \       0 0 0 0 0 0     /
    \    0 0 0 0 0 0  /

          Comme M5      est déjà la matrice nulle il en est de même de M6   .

 

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

    M' =  M (+)  M[2]   (+) M[3]    (+ ) ,  M[4]   (+ )  M[5]  .

 

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

    En bleu les 1 qui ne sont pas de la matrice M.  Il y a donc 5 raccourcis.

      DA                EA             FA             FB                     FE

                                  b. Trouver M[6] . 

     /   0 0     0    0   0    0  \
 /      0 0 0 0 0 0     \
|        0 0 0 0 0 0       |
M[6]   = |        0 0 0 0 0 0       |
 \       0 0 0 0 0 0     /
    \    0 0 0 0 0 0  /

 C'est la matrice nulle.

                             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.

PREDECESSEURS    SOMMETS     NIVEAUX
                                  D               A
                                  C                B
                  E                C
                  E    F                D
      G                 E
      G                 F
                G

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

PREDECESSEURS    SOMMETS     NIVEAUX
                                    D                 A             3
                                   C                   B              3
                  E                 C              2
                  E    F                 D              2
        G                   E              1
        G                   F              1
                G              0

         Voici lla représentation du graphe.

                 

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