Les graphes

Un graphe est constitué d'un ensemble d'objets (représenté par des sommets) reliés entre eux par des liens (les arrêtes du graphes).

Un graphe permet de représenter le réseau ferroviaire, le réseau internet, un labyrinthe ou certains problèmes de choix de chemins

I- L'EXEMPLE DU BERGER

Le problème : Un berger près d'une rivière, possède une chèvre, un chou et un loup. Le berger doit faire passer un à un ces 3 derniers de l'autre côté de la rivière par barque.

CONDITIONS:

Sans le berger :

- La chèvre et le loup sont seuls = le loup mange la chèvre, 

- Le chou et la chèvre sont seuls = la chèvre mange le chou.

En présence du berger : personne ne mange.

 II- COMMENT SORTIR D'UN LABYRINTHE ?

Les intersections sont les sommets du graphe et sont repérées par des lettres. Les couloirs sont les arrêtes.