NOM: ...... Prénom: .............. Date: ............ Classe: BTS.
-----------------------------------------------------------------------------------------------------------------------------
• Combien dans un graphe, un chemin de longueur 4 nécessite-t-il de sommets
distincts ou confonfus ? ....................
• Soit G un graphe de n sommets avec n entier naturel tel que n > 2 et sans circuit.
•• Peut-il avoir un chemin de longueur n ? .....................................
•• Que peut-on dire de la matrice M n si M est sa matrice adjacente ?
.....................................
•Soit le graphe G de sommets ABCDEF dont les arcs sont: ( A , B ) , ( A , C ) , ( C, F ) ( C , B )
( B , D ) , ( D , F ) , ( E , F ) ,( E ,B ).
•• Donner sa matrice d'adjacence M.
M =
•• Y a-t-il des boucles ? ...........
•• Comment peut-on interpréter les deux colonnes de 0 de M ?
.................
•• Représenter G.
••Compléter le tableau:
| PREDECESSEURS | SOMMETS | NIVEAUX |
| A | ||
| B | ||
| C | ||
| D | ||
| E | ||
| F |
••Refaire le graphe en l'ordonnant suivant les niveaux.
•• Trouver les matrices M2 , M3 , M4 , M5 . En déduire M6 .
•• On admet pour chaque arc les durées en mn suivantes:
AB : 2 AC: 12 CF: 17 CB : 4 BD: 7 DF : 11 EF : 12 EB: 14
Mettre sur chaque arc la durée et donner le ou les chemins de longueur minimale de A à F.
•• Trouver la matrice booléenne M' telle que : ( M ' ne peut comporter que des 0 ou 1 )
M ' = M ( + ) M[2] ( + ) M[3] ( + ) M[4] ( + ) M[5] . ( Somme booléenne )
•• Comparer M et M '.
••Soit G ' le graphe de matrice d'adjacence M '.
Représenter G ' . ( Fermeture transitive de G )
Mettre en couleur les arcs de G ' qui ne sont pas dans G.
Citer ces arcs colorés. Que représentent-ils ? .......................