Chemins et circuits
Chemins et circuits
Un chemin conduisant du sommet a au sommet b est une suite de la forme (v0,e1,v1,e2,v2, ..., ek,vk) où les vi sont des sommets (v0=a et vk=b) et les ei sont des arcs tels que ei va de vi-1 à vi. Sur le digraphe ci-contre, on peut voir par exemple le chemin (v3,e3,v4,e4,v5). Par convention, tout chemin comporte au moins un arc.
On appelle distance entre deux sommets d'un digraphe la longueur du plus petit chemin les reliant. S'il n'existe pas de chemin entre les sommets x et y, on pose d(x,y) = infini. Par exemple, sur le digraphe ci-contre, d(v1,v5)=2, d(v1,v6)=1, d(v6,v1)=infini.
Un circuit est un chemin avec u0=uk. Le digraphe ci-contre ne contient pas de circuit.
Les notions de longueur, de chemins et de circuits sont analogues à celles des chaînes et des cycles pour le cas non orienté.
Un digraphe est fortement connexe, si toute paire ordonnée (a, b) de sommets distincts du graphe est reliée par au moins un chemin. En d'autres termes, tout sommet est atteignable depuis tous les autres sommets par au moins un chemin.
On appelle composante fortement connexe tout sous-graphe induit maximal fortement connexe (maximal signifie qu'il n'y a pas de sous-graphe induit connexe plus grand contenant les sommets de la composante).
On souhaite prélever 4 litres de liquide dans un tonneau. Pour cela, nous avons à
notre disposition deux récipients (non gradués!), l'un de 5 litres, l'autre de 3 litres.
Comment doit-on procéder?
Deux joueurs disposent de 2 ou plusieurs tas d'allumettes. À tour de rôle,
chaque joueur peut enlever un certain nombre d'allumettes de l'un des tas (selon la règle choisie). Le joueur qui retire la dernière allumette perd la partie.
Modéliser ce jeu à l'aide d'un graphe dans le cas où l'on dispose au départ de deux
tas contenant chacun trois allumettes, et où un joueur peut enlever une ou deux
allumettes à chaque fois.
Que doit jouer le premier joueur pour gagner la partie à coup sûr?
Donnez un algorithme permettant de calculer la distance entre deux sommets x et y d'un digraphe connexe.
Proposez un algorithme qui détermine si un graphe est fortement connexe ou non.
Indication: utilisez un système de marquage des sommets.
Les graphes ci-dessous sont-il fortement connexes? Si non, donnez leurs composantes fortement connexes.
| a. |  |
b. |  |
| Les corrigés sont disponibles, mais seulement pour les visiteurs autorisés! |
   |
 Didier Müller, 2.2.03 |