Les graphes

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

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 loup, une chèvre et un choux sont présents. Lorsque le berger surveille, le loup ne mange pas la chèvre et la chèvre ne mange pas le choux, si il est absent, le loup mage la chèvre qui elle mange le choux. Ils arrivent devant une rivière. Le berger doit faire traverser le loup, la chèvre et le choux mais ne peut les rapprendre qu un seul à la fois dans sa barque. Comment doit il procéder ?

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.