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. )
------------------------------------------------------------------------------------------------------------------
EX.3 ( Méthode des potentiels Métro )
Une entrprise doit accomplir des tâches diverses avec des durées différentes pour
réaliser un certain travail.Voici le tableau qui fixe les tâches et leur durée. Chaque sommet du graphe orienté simple est une tâche.
| Tâches | A | B | C | D | E | F | G |
| Tâche antérieure | A | A | A B | A C | A B | A B C D E F | |
| Durée en jours | 4 | 6 | 7 | 10 | 4 | 5 | 6 |
Une tâche antérieure n'est pas forcément la tâche précédente.
On admettra que " Prédécesseur direct" signifie " Tâche immédiatement
antérieure" .
1. Faire un tableau afin d'avoir le niveau de chacun des sommet ABCDEFG.
( Comme dans les autres exercices .)
2. a.Faire la représentation du graphe orienté ordonnancé.
( c-à-d suivant les niveaux des sommets .)
b.On convient que la valeur d'un arc est la durée de la tâche d'origine de l'arc.
Par exemple sur l'arc ( A , B ) on mettra la durée de A , c-à-d 4.
Mettre sur les arc les valeurs des arcs.
3. Reproduire cette représentation en ajoutant à côté de chaque sommet
deux cases. Pour A
0
a. Dans la première case mettre la durée maximale du chemin qui mène à
ce sommet en sommant les valeurs des arcs .
26 figure ici dans la première case du dernier sommet.
0 figure dans la première case du premier sommet.
b. Mettre encore cette durée maximale 26 dans la seconde case du dernier sommet.
| 26 | 26 |
4 . Joindre les sommets où les deux cases sont identiques
C'est le chemin dit " critique"