Les graphes
Un graphe est un outil permettant de représenter des objets (sommets) et des liens ou interaction entre ces objets (arrêtes). Exemple : réseau SNCF, villes et routes, réseaux (internet), labyrinthes (les graphes peuvent permettre de trouver les sorties du labyrinthe).
I) L'exemple du berger
Un berger a un loup, une chèvre et un choux. En présence du berger, la chèvre ne mange pas le chou et le loup ne mange pas la chèvre. Pour traverser une rivière, le berger ne peut transporter qu'un de ses compagnons à la fois. Comment doit-il faire ?
Il y a 4 personnages et deux états possibles. Il y a 16 combinaisons possibles.
Chaque combinaison sera simplement représentée par l'état sur la ligne de départ.
Chaque combinaison est un sommet, chaque arrête est un trajet en barque.
Combinaisons impossibles :
-choux/chèvre
-loup/chèvre
-loup/berger
-choux/berger
-choux/chèvre/loup
-berger seul
Un labyrinthe peut être décrit par un graphe, les croisements étant les objets placés aux sommets, et les couloirs les liens entre ces sommets.
Entrée A ; Sortie Z
1) A
2) AB
3) ABC
ABM
4) ABCD
ABCK
ABM
5) ABCDK x
ABCDE
ABCK
ABM
6) ABCDEF x
ABCDEG Parcours d'un graphe en profondeur
ABCK
ABM
7) ABCDEGH x
ABCDEGI
ABCK
ABM
8) ABCDEGIJ x
ABCK
ABM
9) ABCKL x
ABCKD x
ABM
10) ABMN x
ABMZ
x = Possibilité éliminée
1) A
2) AB
3) ABC
ABM
4) ABCD
ABCK Parcours d'un graphe en largeur
ABM
5) ABMN x
ABMZ
ABCK
ABCD
Le parcours d'un graphe en largeur traite d'abord les possibilités les plus courtes. Il permet de trouver le chemin le plus court pour sortir.
Le parcours en profondeur, pour ne pas tourner en rond, doit interdire de repasser par des sommets déjà utilisés.