La représentation de certaines données peut nécessiter des structures plus complexes que des tableaux ou des listes. Parmi ces représentations, on peut trouver les graphes qui permettent, entre autres, de représenter des chemins.
Dans cet article, je vous propose d'aborder la théorie des graphes comme une sorte de retour aux sources en s'attachant à la représentation et aux parcours de chemins. Pourquoi un retour aux sources ? Simplement parce que l'on situe la naissance de la théorie des graphes en 1736 avec la présentation du problème des ponts de Königsberg par le mathématicien Leonhard Euler [1]. Ce problème se base sur la géographie de la ville de Königsberg traversée par la rivière Pregel et qui comporte deux îles. Pour accéder à ces îles, sept ponts étaient alors disponibles comme le montre la figure 1 issue des travaux de Édouard Lucas [2] : l'île Kneiphof est notée A, B et C sont les berges, D est une seconde île et a, b, c, d, e, f et g sont les ponts permettant d'accéder ou de partir de A et D. La question que se posait Euler était la suivante : quel chemin emprunter pour partir d'un point A, B, C ou D, traverser chaque pont une fois et une seule et revenir à son point de...
- Accédez à tous les contenus de Connect en illimité
- Découvrez des listes de lecture et des contenus Premium
- Consultez les nouveaux articles en avant-première