Les graphs

Un graphe est un outil permettant de représenter des objets (sommet) et des liens ou interactions entre ses objets (arêtes). Exemple : réseau SNCF, réseaux internet, ville et route, les labyrinthes... Les graphes peuvent permettre de trouver la sortie d'un labyrinthe.

L'exemple du berger

Un berger (b) à un loup (l) une chèvre ( c) et un choux. En présence du berger, la chèvre ne mange pas le choux et le loup ne mange pas la chèvre. Pour traverser une rivière, le berger ne peux transporter qu'un de ses compagnons à la fois.

Les 4 personnages sont dans 2 états possibles : soit sur la rive de départ soit sur la rive d'arrivée → 16 combinaisons possibles. Chaque combinaisons sera représenter par l'état sur la rive de départ. Chaque combinaison est un sommet chaque arête est un trajet en barque.

Combinaisons impossibles :

• choux/chèvre

• loup/chèvre

• loup/berger

• choux/berger

• choux/chèvre/loup

• berger

Sortir d'un labyrinthe

Un labyrinthe peut être décrit par un graphes, les croisements étant les objets placés aux sommets et les couloirs les liens entre ses sommets.

1 AB

2 ABM

   ABC

3 ABM

   ABCK

   ABCD

4 ABM

   ABCK

   ABCD

5 ABM

   ABCK

   ABCDE

   ABCDK

6 ABM

   ABCDEF

   ABCDEG

   ABCK

7 ABM

   ABCDEGH

   ABCDEGI

   ABCK

8 ABM

   ABCDEGIJ

   ABCK

9 ABM

   ABCKD

   ABCKL

10 ABMN

    ABMZ

→ Parcours en profondeur

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

1 A

2 AB

3 ABC

   ABM

4 ABM

   ABCK

   ABCD

5 ABMN

   ABMZ

   ABCK

   ABCD

Le parcours en profondeur, pour ne pas tourner en rond, doit interdire de passer par des sommets déjà utilisés.