graphes

Les graphes sont utilisés dans de nombreux domaines: les réseaux de télécommunications, les bases de données relationnelles, les circuits électriques.
Historiquement, on considère généralement que la théorie des graphes a eu comme point de départ le célèbre problème des ponts de Königsberg, résolu en 1736 par Léonhard EULER (1707-1783).
Voici un énoncé du problème des ponts de Königsberg, ville situé à l’époque en Russie :
« Est-il possible de partir d’un endroit de la ville de Königsberg et d’y revenir après avoir fait une promenade empruntant une fois et une seule chacun des sept ponts de la ville ? »
Euler modélisa cette situation par un graphe.

Un autre probléme connu est celui du fermier devant faire passer une chèvre, un loup et un chou sur l’autre rive d’un fleuve, ne pouvant charger qu’un passager à la fois, et ne pouvant laisser sur une même rive le loup et la chèvre ou la chèvre et le chou.

Nous allons écrire la structure de donnée Graphe et donner les algorithmes usuels comme les parcours en profondeur ou en largeur.