Les graphes

Un graphe est un outil permettant de rpz des objets (sommets) et des liens/interactions entre ces objets (arêtes). Exemples : réseaux SNCF, les villes et les routes, les réseaux informatiques, les labyrinthes. Les graphes peuvent permettre de trouver la sortie de labyrinthes.

L'Exemple du berger

Un berger a un loup, une chèvre et un chou. 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 faire ?

Quatre personnages dans deux états possibles, 16 combinaisons possibles.

Chaque combinaisons sera représentée par l'état sur la rive de départ.

Chaque combinaison est un sommet, chaque trajet une arête.

Combinaisons impossibles : 

chou/chèvre

loup/berger

loup/chèvre

berger/chou

Sortir d'un labyrinthe

Un labyrinthe peut être décrit par un graphe, les croisements étant les objets placés au sommets, et les couloirs les liens entre les sommets;