• 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 ?    
    « Parc JosaphatBrocante de printemps 2010 »

  • Commentaires

    1
    Dirk
    Jeudi 17 Juin 2010 à 16:56
    La personne qui sait fair cela, est très, très fort! J'ai des doutes.
    2
    Poupon La Peste Profil de Poupon La Peste
    Vendredi 18 Juin 2010 à 12:09
    En 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

    Nom / Pseudo :

    E-mail (facultatif) :

    Site Web (facultatif) :

    Commentaire :