GRAPHE ORIENTE 3 BTS1

      GRAPHE ORIENTE 3         BTS1      SUITE DU COURS  NOV.08

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

   13. FERMETURE TRANSITIVE d'un graphe orienté

                 Soit G un graphe.

                  Sa fermeture transitive est le graphe orienté G ' obtenu en

                   rajoutant  à G tous les raccourcis entre les sommets déjà

                   reliés par un chemin.

                 14. PROPRIETE  admise.

                         Soit G un graphe orienté de n sommets .

                         Soit M sa matrice d'adjacence.

                        Alors :

                  La somme booléenne des matrices M , M[2]  ,   .   M[n  ]  donne

                   la matrice d'ajacence de la fermeture du graphe , c-à-d de G '.

              15 . Niveau d'un sommet d'un graphe orienté sans boucle ni circuit.

                            On rajoute une colonne au tableau des prédécesseurs.

                            Un sommet sans prédécesseur est de niveau  O.

                            On le barre dans la colonne des prédécesseurs.

                            Le ou les sommets qui apparaîssent sans prédécesseurs

                             sont de niveau alors 1.

                           On, le ou les, barre dans la colonne des prédécesseurs.

                           Les sommets alors sans prédécesseurs sont de niveau 2.

                           .....         etc   ainsi de suite.

               16. Graphe orienté ordonné suivant les niveaux.

                   Dans le dessin du graphe orienté sans boucle ni circuit,

                   les sommets de même niveau sont sur une verticale non tracée.

                  On met, de la gauche vers la droite, les sommets, de niveau 0,

                  puis ceux de niveau 1 puis ceux ..... etc

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