Notions de chemins et de cheminement
Définition : Première définition d'un chemin
Un chemin dans un graphe (X,E) est une suite finie d'arcs U1, U2, ..., Up appartenant à E telle que
- soit le chemin est vide : p=0,
- soit tout arc de la suite, sauf le dernier, a son extrémité qui coïncide avec l'origine de l'arc suivant.
Cliquer sur Précédent ou Suivant pour visionner des exemples différents ou sur petits et grands pour changer la taille des graphes.
Définition : Deuxième définition d'un chemin
Un chemin est aussi défini par une suite de points xo, x1, ..., xp
telle que deux points qui se suivent sont toujours reliés par un arc
ayant pour origine le premier point et pour extrémité le second.
Le premier point xo est appelé origine du chemin.
Le dernier point Xp est appelé extrémité du chemin.
Avec cette deuxième définition, Xo est le chemin vide alors que Xo, Xo est la boucle en Xo .
Cette deuxième définition n'est pas suffisante si on considère des p-graphes, ce que nous ne ferons pas ici. Alors que la première définition des chemins restent valables sur les p-graphes (par exemple pour un réseau avec plusieurs routes entre deux nœuds du réseau.
Nous ne mettons pas d'illustrations présentant des chemins sous forme de listes de points, car pour bien visualiser les chemins, on a besoin de montrer également les arcs associés.
La construction d'un chemin utilise obligatoirement les successeurs ou les prédécesseurs d'un point
On passe de successeur à successeur du successeur etc. si on construit un chemin en partant de son origine.
On passe de prédécesseur à prédécesseur du prédécesseur etc. si on construit un chemin en partant de son extrémité.
Nous rappelons donc ici les définitions de successeurs et de prédécesseurs et en profitons pour présenter également les notions de degrés.
Définition : Successeurs d'un point (rappel) et demi-degré extérieur
L'ensemble des successeurs d'un point x est l'ensemble des points y tels que (x, y) ∈ E (ou encore x Γ y) et est noté Γ(x).
Cet ensemble est aussi dénommé liste des successeurs d'un point.
Le demi-degré extérieur de x est le nombre d'arcs d'origine x.
Il est noté de(x).
C'est donc aussi le nombre de successeurs de x soit card(Γ(x)).
Cliquez sur précédent et suivant pour avoir de nombreux exemples petits ou grands en utilisant le bouton du bas.
Définition : Prédécesseurs d'un point (rappel) et demi-degré intérieur
L'ensemble des prédécesseurs d'un point x est l'ensemble des points y tels que (y, x) ∈ E (ou encore x Γ-1 y ou encore y Γx) et est noté Γ-1(x). Γ-1 est la relation réciproque de Γ.
Cette ensemble est aussi dénommé liste des prédécesseurs d'un point.
Le demi-degré intérieur de x est le nombre d'arcs d'extrémité x.
Il est noté di(x).
C'est donc aussi le nombre de prédécesseurs de x soit card(Γ-1(x)).
Cliquez sur précédent et suivant pour avoir de nombreux exemples petits ou grands en utilisant le bouton du bas.
Définition : Degré d'un point
Le degré du point x, noté d(x)
est le nombre d'arêtes ayant pour extrémité x.
C'est aussi le nombre de voisins de x.
Un voisin de x est un successeur et/ou un prédécesseur de x.
Définition : Descendants et ascendants d'un point
Un point y est un descendant d'un point x s'il existe un chemin ayant pour origine x et pour extrémité y.
Un point y est un ascendant d'un point x s'il existe un chemin ayant pour origine y et pour extrémité x.
Comme tout chemin (non vide) comprend au minimum un arc ou une boucle, un point x ne fait pas toujours partie de ses descendants ou de ses ascendants.
Définition : Circuit
Si un point x fait partie de ses descendants, alors il existe un chemin ayant pour origine x et pour extrémité x, on appelle ce chemin un circuit.
Les chemins sans circuit sont des chemins élémentaires.
Définition : Chemin élémentaire
Un chemin xo, x1, ..., xp est élémentaire s'il ne passe pas deux fois par le même point
(on ne peut avoir xi=xj si i et j sont différents).
Avec la première définition des chemins, on obtient une autre définition de chemins particuliers, les chemins simples.
Définition : Chemin simple
Un chemin U1, U2, ..., Up est simple s'il ne passe pas deux fois par le même arc
(on ne peut avoir Ui=Uj si i et j sont différents).
Remarque :
Un chemin élémentaire est toujours simple alors qu'un chemin simple n'est pas toujours élémentaire.
Un chemin simple peut donc contenir des circuits.
Illustrations et animations sur les descendants et sur les ascendants
Dans les animations qui suivent, le point dont on cherche les descendants (ou les ascendants) est colorié en bleu ciel alors que les autres points sont coloriés en noir. Un cercle rouge permet de reconnaître ses descendants (ou ses ascendants). Il appartient donc à un circuit lorsqu'il est bleu ciel cerclé de rouge.
Cliquez sur précédent et suivant pour avoir de nombreux exemples petits ou grands en utilisant le bouton du bas.
Algorithme de recherche des descendants des points
Cet algorithme utilise un tableau de points marqués.
Ce tableau de marque est représenté par la couleur des points sur le graphe : bleu ciel pour le point initial, jaune pour ses successeurs, bleu ciel cerclé de jaune si le point est son propre successeur.
Ce tableau de marque est également représenté par des couleurs sur le numéro des lignes de la matrice en variables 0-1 du graphe.
L'algorithme est très simple.
On marque le point initial, puis les successeurs du point initial.
Aux itérations suivantes, on marque tous les successeurs des points déjà marqués non encore marqués jusqu'à ce que l'on ne puisse plus marquer de points.
Cliquer sur Anim pour démarrer l'animation. Sélectionner un graphe. En changeant la valeur numérique du point initial et en cliquant sur valider, on peut changer de point initial. Ensuite on clique en alternance sur d-ITet f-IT (le bouton actif) pour suivre les itérations successives de l'algorithme sur la représentation graphique et sur le bord gauche de la matrice.
Cliquez sur précédent et suivant pour avoir de nombreux exemples petits ou grands en utilisant le bouton du bas.
Algorithme de recherche des ascendants des points
Cet algorithme utilise un tableau de points marqués.
Ce tableau de marque est représenté par la couleur des points sur le graphe : bleu ciel pour le point initial, jaune pour ses prédécesseurs, bleu ciel cerclé de jaune si le point est son propre prédécesseur.
Ce tableau de marque est également représenté par des couleurs sur le numéro des colonnes de la matrice en variables 0-1 du graphe.
L'algorithme est très simple.
On marque le point initial, puis les prédécesseurs du point initial.
Aux itérations suivantes, on marque tous les prédécesseurs des points déjà marqués non encore marqués jusqu'à ce que l'on ne puisse plus marquer de points.
Cliquer sur Anim pour démarrer l'animation. Sélectionner un graphe. En changeant la valeur numérique du point initial et en cliquant sur valider, on peut changer de point initial. Ensuite on clique en alternance sur d-ITet f-IT (le bouton actif) pour suivre les itérations successives de l'algorithme sur la représentation graphique et sur le bord supérieur de la matrice.
Remarque :
Les prédécesseurs d'un point dans le graphe G sont en fait les successeurs de ce même point sur le graphe inverse G-1 obtenu en inversant le sens de tous les arcs.
De la même manière, les ascendants d'un point dans le graphe G sont en fait les descendants de ce même point sur le graphe inverse G-1 obtenu en inversant le sens de tous les arcs.
Un seul et même algorithme est donc suffisant si l'on travaille sur le graphe et/ou sur le graphe inverse.
Définition : Fermeture transitive d'un graphe
Etant donné un graphe G=(X,E), sa fermeture transitive FT=(X,E*) est défini par
( ∀ (x,y) ∈ XxX ) ((x,y )∈ E* ⇒ il existe un chemin de x à y dans le graphe G ou x=y).
La fermeture transitive d'un graphe G est donc un nouveau graphe qui traduit le fait qu'il existe ou non un chemin dans le graphe G.
On y inclut les boucles car dans ce cas on considère que l'on peut toujours se rendre de x à x (puisqu'on y est déjà).
On peut également définir la fermeture transitive d'un graphe en utilisant des opérations d'union et de produits de graphes (voir le chapitre sur les propriétés des graphes liés aux relations binaires associées).
Définition : Fermeture transitive stricte d'un graphe
Etant donné un graphe G=(X,E), sa fermeture transitive stricte FTS=(X,E+) est défini par
( ∀ (x,y) ∈ XxX ) ((x,y )∈ E* ⇒ il existe un chemin non vide de x à y dans le graphe G).
La fermeture transitive stricte d'un graphe G est donc un nouveau graphe qui traduit le fait qu'il existe ou non un chemin dans le graphe G.
On n'y inclut pas les boucles.
Une boucle existe dans la fermeture transitive stricte uniquement si elle existait déjà dans le graphe initial ou s'il existe un chemin non vide allant de x à x. Ce chemin est alors appelé un circuit.
Autres notions liées aux problèmes de cheminement
Les notions de chaînes et de cycles seront présentées dans le chapitre sur les graphes non orientés.
Les notions d'Eulérien et d'Hamiltonien seront présentées dans le chapitre sur les graphes particuliers.
