LES GRAPHES

        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.

I.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/chevre

• loup/chevre

• loup/berger

• choux/berger

• choux/chevre/loup

• berger

=> B/Cx/C/L---transport chevre---Cx/L---retour berger---B/Cx/L---transport loup---Cx---B/C/Cx---C---B/C---O

II.Sortir d'un labyrinthe

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

 Entrée A, sortie Z.                                            

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

      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