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