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 , M3 , M4 , 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. )