-
Les 7 ponts
La ville de Königsberg (aujourd'hui Kaliningrad) est construite autour de deux îles reliées entre elles par un pont et six ponts relient le continent à l'une ou l'autre des deux îles. Le problème consiste à déterminer s'il existe ou non une promenade dans les rues de Königsberg permettant, à partir d'un point de départ au choix, de passer une et une seule fois par chaque pont, et de revenir à son point de départ, étant entendu qu'on ne peut traverser le fleuve qu'en passant sur les ponts.
Quel trajet permet de passer une et une seule fois sur chaque pont ?
-
Commentaires
1DirkJeudi 17 Juin 2010 à 16:56La personne qui sait fair cela, est très, très fort! J'ai des doutes.Répondre2Poupon La Peste
Vendredi 18 Juin 2010 à 12:09En fait, c'est impossible, et le mathématicien Euler l'a démontré, avec la théorie des graphes.
En résumé, on représente chaque pont par une arête et les deux îles et les deux berges par un noeud. Et on compte le nombre de ponts qui part de chaque noeud. Ici tous les noeuds ont 3 arêtes, sauf l'île qui en a 5.
On dit que le degré d'un noeud est le nombre d'arêtes qui y arrivent.
La théorie des graphes dit qu'il y a un chaîne eulérienne (c'est-à-dire une chaîne passant par toutes les arêtes du graphe une et une seule fois), uniquement si le graphe associé au problème possède 0 ou 2 sommets de degré impair.
Et comme dans notre ville, il y a 4 noeuds de degré impair, c'est impossible de faire une promenade qui passe exactement une et une seule fois par chaque pont.
Suivre le flux RSS des commentaires
Ajouter un commentaire
Créer mon blog