Chapitre 6 Problèmes de chemins
6.1. DEFINITION D'UN GRAPHE
Dans la pratique, un graphe se présente de la façon suivante :
- un ensemble de points, fini
- des flèches reliant certains de ces points entre eux.
Par exemple :
Figure 1
Les points seront appelés sommets, les flèches arcs.
D'une façon plus précise, un graphe
est constitué par le couple :
- d'un ensemble
de sommets, fini
- d'une liste d'éléments du produit cartésien
On notera que l'ordre
a de l'importance (il définit l'orientation des arcs). On
remarquera également que l'arc
peut revenir plusieurs fois dans la liste.
Pour un arc quelconque
, sera appelé l'extrémité initiale et
l'extrémité
terminale.
Un arc du type
sera appelé boucle (sur le graphe de la figure 1, un tel arc relie à
lui-même).
Si le nombre d'arcs reliant un sommet quelconque
à un sommet quelconque
ne
dépasse pas , on dira qu'on a affaire à un p-graphe.
(Le graphe de la figure 1 est un 2-graphe).