Les graphes

 

 

 

Un graphe est contitué par un ensemble d'objet ( représenté par des sommets) reliés entre eux par des liens les arretes du graphe

Un graphe permet de representer le réseaux ferrovière le réseau internet un labyrinthe ou certains problème de choix de chemin

I]L'exemple du Berger

​

Un Berger a un chou, une chèvre et un loup .

Le loup mange la chèvre et la chèvre mange le chou si le berger n'est pas la.

Le berger doit traverser une rivière mais ne peut transporter que un seul à la fois.

Par quel moyen allons nous résoudre ce problème ?

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Il y a 16 situations possibles

Chaque états sera simplement décrit sur chaque personnage sur la rive de depart

 

Liste des états interdits :

-L C

-C Cx

-B Cx

-B L

 

4 situations interdites.

 

 

 

 

 

 

​

​

​

​

​

1: traversée B C

2: retour B

3: traversée B L

4: retour B C

5: traversée B Cx

6: retour B

7: traversée B C

 

II] Comment sortir d'un labyrinthe

 

Les intersections sont les sommets du graphe et sont repere par des lettres, les couloirs sont les arrêtes

 

Chemin possible :

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Parcours en largeur :

1-A

2-AB

3-ABC

ABM

4-ABCD

ABCK

ABM

5-ABCD

ABCK

ABMN

ABMZ → solution

 

Le parcour en largeur permet de trouver le chemin le plus court pour sortir du labyrinthe.

 

Parcours en profondeur :

1-A

2-AB

3-ABC

ABM

4-ABCD

ABCK

ABM

5-ABCDE

ABCDK

ABCK

ABM

6-ABCDEF

ABCDEG

ABCK

ABM

7-ABCDEJH

ABCDEGI

ABCK

ABM

8-ABCDEGIJ

ABCK

ABM

9-ABCKD

ABCKL

ABM

10-ADMN

ADMZ → solution