3. Problèmes d'Euler et de Hamilton
« Des problèmes où l'on se fait tout petit pour se promener le long des arêtes d'un graphe. »
• Le problème d'Euler
Ce problème classique de cheminement le long des ponts de Königsberg, ville de l'ancienne Prusse-Orientale, souleva l'intérêt du célèbre mathématicien suisse Leonhard Euler. On parlait alors beaucoup du problème des ponts. Le plan de la ville (aujourd'hui Kaliningrad, en Russie) peut être schématisé comme sur la figure et le problème posé par les oisifs prussiens était le suivant : peut-on se promener dans Königsberg en passant une fois et une seule par chaque pont et en revenant au point de départ ?
Ce problème devient un problème de graphes dans la représentation de la figure. Il faut alors trouver un cheminement qui passe par toutes les arêtes du graphe une fois et une seule et qui revienne à son point de départ. Un tel cheminement est appelé de nos jours un cycle eulérien, notion qui se formalise aisément.
Euler démontra simplement que ce problème était insoluble et, plus généralement, que pour qu'il existe dans un graphe G un cycle eulérien, il faut et il suffit que le nombre des arêtes de G en chacun de ses sommets soit pair.
[…]… pour nos abonnés, l'article se prolonge sur 5 pages…
