LES GRAPHES PLANAIRES
Accueil Remonter LES PONTS DE KÖNIGSBERG LES GRAPHES PLANAIRES LE COLORIAGE DES CARTES POUR CONCLURE

 

 

    Nous avons vu que pour résoudre le problème des ponts de Königsberg, Euler avait utilisé la notion de graphe, c'est exactement le même procédé qui permet de résoudre le problème des maisons. Il y aura une solution, si le graphe associé aux maisons, peut être qualifié de planaire, c'est à dire si on peut le représenter dans un espace à deux dimensions, et que les arêtes ne se coupent pas en dehors de leurs extrémités.

    Et là ça va aller très vite, car encore une fois, je pense qu'on peut faire confiance à Kazimierz Kuratowski, lequel a démontré en 1930, qu'un graphe est planaire si et seulement si, il ne contient pas l'une des deux configurations suivantes :

  1. Trois sommets reliés chacun à trois sommets. (je vous l'avais dit que ça irait vite, un peu décevant non?)
  2. Cinq sommets tous reliés entre eux.

    Et bien voilà on ne peut pas relier les 3 maisons aux 3 bornes, sans croiser les tuyaux. Par contre il est fort possible que ce problème est été créé dans les années 30 suite à la découverte de Kuratowski, car curieusement, il s'agit exactement du cas particulier d'impossibilité que le mathématicien a mis en évidence dans son théorème, étrange coïncidence.

    Donc faites des économies de papier et arrêtez de dessiner des maisons et des tuyaux, ça ne marche pas.

    Je sens bien que je ne peux pas vous laisser comme ça, vous restez sur votre fin, tout ça pour ça, quelle déception. Rassurez vous, il y a quand même un truc, on a vu le coup de la représentation en 3D, (il est vrai que mon dessin n'est pas terrible, mais si certains d'entre vous font mieux, je suis preneur) mais ce n'est plus à deux dimensions et on ne respecte pas les contraintes de départ. Et bien il existe une possibilité! Non!? Si! Si! Et, bon c'est pas trop compliqué en fait.

    Supposons que les maisons soient sur un tore. Question : qu'est ce qu'un tore? Il s'agit de la surface engendrée par un cercle tournant autour d'une droite située dans son plan et ne passant pas par son centre. Suis-je clair? Pas vraiment n'est-ce pas? Prenons un exemple, une chambre à air est un tore, ça va mieux non?

 

VOICI UN TORE

ON Y POSE LES MAISONS DESSUS

       Et voilà, si vous posez vos maisons sur une chambre à air, ça marche! Moi ça m'en bouche un coin, pas vous?

    Allez, ce coup-ci, c'est vraiment pour finir, sinon on ne s'en sortira plus, (Il faut dire que la théorie des graphes s'est énormément développée, et qu'il existe aujourd'hui de nombreux ouvrages qui ne traitent que des graphes.) donc la question, est de savoir maintenant si l'on peut représenter un graphe à 5 sommet sur un tore? Rappelons que d'après Kuratowski, c'est impossible sur un espace à deux dimensions.

    Pour être plus clair, imaginons 5 maisons, qu'il faut relier entre-elles par une route, sans que celles-ci ne se croisent. Donc de chaque maison, il part 4 routes, vu?