Graphes orientés (digraphes)
Graphes orientés (digraphes)En donnant un sens aux arêtes d'un graphe, on obtient un digraphe (ou graphe orienté).
Un digraphe fini G = (V, E) est défini par l'ensemble fini V = {v1, v2, ..., vn} (|V| = n) dont les éléments sont appelés sommets, et par l'ensemble fini E = {e1, e2, ..., em} (|E| = m) dont les éléments sont appelés arcs.
Un arc e de l'ensemble E est défini par une paire ordonnée de sommets. Lorsque e = (u, v), on dira que l'arc e va de u à v. On dit aussi que u est l'extrémité initiale et v l'extrémité finale de e.
Construire un graphe orienté dont les sommets sont les entiers compris entre 1 et 12 et dont les arcs représentent la relation «être diviseur de».
| Le corrigé est disponible, mais seulement pour les visiteurs autorisés! |
   |
 Didier Müller, 8.2.03 |