Voir la source de Énigme des trois maisons

[[File:Water gaz electricity Dudeney.jpg|thumb|upright=1.6|Résoudre l'énigme consiste à relier chacune des trois maisons du bas à chaque usine du haut par un [[chemin (graphe)|chemin]]. Cette illustration est l'œuvre de [[Henry Dudeney]] qui présente cette énigme en 1917 dans son livre ''{{Lang|en|Amusements in mathematics}}''.]]

L''''énigme des trois maisons''', aussi appelée l''''énigme de l'eau, du gaz et de l'électricité''', est un [[jeu mathématique]] dont l'analyse utilise un théorème de [[topologie]] ou de [[théorie des graphes]]. Ce problème n'a pas de solution. [[Georges Perec]] le cite en 1978 dans son livre ''[[Je me souviens (Perec)|Je me souviens]]'' : {{Citation|Je me souviens des heures que j'ai passées, en classe de troisième, je crois, à essayer d'alimenter en eau, gaz et électricité, trois maisons, sans que les tuyaux se croisent (il n'y a pas de solution tant que l'on reste dans un espace à deux dimensions ; c'est l'un des exemples élémentaires de la topologie, comme les [[Problème des sept ponts de Königsberg|ponts de Königsberg]], ou le [[Théorème des quatre couleurs|coloriage des cartes]])}}<ref>[[Georges Perec]], ''Je me souviens'', (réédition de 1998) Souvenir {{n°|292}}, {{ISBN|2012354564}}</ref>{{,}}<ref group=Note>Mathématiquement, l'assertion de Georges Perec n'est pas totalement exacte : si les trois énoncés sont élémentaires, et si  la résolution de l'énigme des ponts de Königsberg est facile, celle de l'article l'est déjà moins et celle des quatre couleurs ne l'est plus du tout. De plus, sur un tore ou un ruban de Möbius, des surfaces de dimension deux, une solution existe.</ref>.

Cette énigme est déjà posée par [[Henry Dudeney]] en [[1917 en science|1917]] dans son livre ''{{Lang|en|Amusements in mathematics}}''. Il précise qu'{{Citation|il existe une demi-douzaine d'énigmes vieilles comme le monde, qui réapparaissent perpétuellement<ref name=Dudley>Citations traduites de {{en}} [[Henry Dudeney|H. E. Dudeney]], ''[http://www.gutenberg.org/files/16713/16713-h/16713-h.htm#POINTS_AND_LINES_PROBLEMS Amusements in mathematics]'', pb 251</ref>}}. Celle de l'article en est une, qu'il appelle ''eau, gaz, et électricité''<ref name=Dudley/>. Elle a été popularisée par [[Martin Gardner]], qui la présente dans son ''Sixième livre de jeux mathématiques'' (1971)<ref>{{en}} M. Gardner, ''The Sixth Book of Mathematical Games from Scientific American'', University of Chicago Press, 1984 {{ISBN|978-022628250-3}}, {{p.|92-94}}</ref>.

Il existe deux approches pour démontrer l'inexistence d'une solution connectant chacune des trois maisons ''directement'' aux trois fournisseurs. La première approche montrant l'impossibilité utilise le [[théorème de Jordan]], indiquant que si l'on dessine une ''boucle'' dans un plan, le complémentaire de la ''boucle'', c'est-à-dire la partie non dessinée du plan, se compose de deux [[connexité par arcs|connexes par arcs]], l'un borné (l'intérieur de la boucle) et l'autre non (l'extérieur de la boucle). La seconde approche, plus générale, utilise la [[Théorème de Descartes-Euler|formule d'Euler]] pour les [[graphe planaire|graphes planaires]]. Elle est une étape dans la démonstration du théorème clé des graphes planaires, due à [[Kazimierz Kuratowski]].

== Énoncés ==
[[File:Enigme-des-3-maisons-(13).svg|thumb|Cette solution n'est pas acceptable : la canalisation orange en croise une autre.]]
Sous la forme d'historiette, l'énigme s'exprime de la manière suivante<ref>On trouve cette anecdote dans {{harvsp|Chomette||texte=T. Chomette, Graphes planaires}}.</ref> :
{{citation bloc|Un lotissement de trois maisons doit être équipé d'eau, de gaz et d'électricité. La règlementation interdit de croiser les canalisations pour des raisons de sécurité. Comment faut-il faire<ref>On trouve aussi cette anecdote dans des sites plus populaires : G. Villemin, ''[http://villemin.gerard.free.fr/Puzzle/EnigGraf.htm Les trois maisons]'', par le site : Nombres – Curiosités, théorie et usages.</ref> ?}}

L'historiette possède de nombreuses variantes<ref group=Note>Cette version possède l'avantage d'interdire la solution illustrée droite. C'est une solution où la canalisation alimentant en gaz la maison 2 traverse la maison 3. En mathématique, elle n'est pas acceptable, car aucun lien ne relie le nœud de la maison 2 au nœud du fournisseur gaz. Sous la forme de l'énigme, elle ne l'est généralement pas non plus, même si certains sites populaires comme ''[http://www.pedagonet.com/other/enig160a.htm Trois maisons sur Pedagonet]'' l'acceptent.</ref>. On trouve par exemple celle-ci : {{Citation|Il possède… 3 voitures, lesquelles doivent pouvoir se garer indifféremment sur les places de parking 1, 2 ou 3… Il voudrait tracer des routes reliant chaque voiture à chacun des emplacements (soit un total de 9 routes distinctes) afin que chaque véhicule puisse se rendre sur n'importe laquelle de ces places, mais, afin d'éviter les collisions, ces chemins ne doivent en aucun cas se couper, ni être confondus (même partiellement). Ces chemins peuvent passer derrière les parkings et les autos, et avoir n'importe quelle forme, mais ne doivent pas traverser les emplacements (ni bien sûr les autres véhicules)}}<ref>Cette citation est extraite du site [http://www.mathsaharry.com/enigme74.htm www.mathsaharry.com], énigme {{numéro|74}} par ''Math au matou''.</ref>.

Ce problème peut aussi être vu de façon abstraite comme un [[Théorie des graphes|graphe]], ce qui permet de l'étudier mathématiquement. Un graphe est composé d'un ensemble de points, appelés ''nœuds'' ou ''sommets'', dont certains sont reliés par des liens (également appelés ''arêtes''). Dans le cas de l'énigme, il existe deux ensembles de nœuds : l'ensemble ''M'' ayant trois nœuds pour les trois maisons (en bleu dans la figure ci-contre), et l'ensemble ''F'' ayant trois nœuds pour l'arrivée de gaz, d'eau et d'électricité (en rouge dans la figure ci-contre). L'énigme demande qu'il existe un lien entre chaque nœud de ''M'' et chaque nœud de ''F'', de façon telle que deux liens ne se croisent pas : une façon possible de disposer ces liens est montrée dans la figure ci-contre avec les liens en vert. Un graphe dans lequel tous les nœuds d'un ensemble de ''m'' éléments doivent être reliés à ceux d'un ensemble de ''n'' élément est appelé ''[[graphe biparti complet]]'', noté ''K''<sub>m,n</sub>. Un graphe dans lequel deux liens ne se croisent pas est appelé [[graphe planaire|planaire]]. La question devient : ''K''<sub>3,3</sub> est-il un graphe planaire ?

== Topologie géométrique ==
=== Préambule ===
[[File:Enigme-des-3-maisons-(14).jpg|left|thumb|Les deux canalisations sont ''équivalentes''.]]
[[File:Enigme-des-3-maisons-(15).jpg|thumb|Le nombre de combinaisons à tester n'est pas fini.]]
Une première démarche, pour élucider l'énigme, consiste à ''faire des essais''. Elle débouche sur un double constat. Rapidement, celui qui cherche à résoudre l'énigme y arrive ''presque'', c'est-à-dire qu'il parvient à poser huit canalisations, mais la dernière résiste. Le deuxième constat est qu'il existe beaucoup de possibilités différentes à tester.

Intuitivement, il semble évident que certaines d'entre elles sont équivalentes. Deux tentatives telles qu'il est possible de déformer continument les canalisations pour passer de la première à la seconde correspondent en fait à la même tentative. Cette équivalence porte un nom en mathématique, elle s'appelle l'[[homotopie]]. Il s'avère que cette notion, difficile à formaliser précisément, n'est guère nécessaire pour résoudre l'énigme<ref>La démonstration usuelle n'en fait pas usage (voir {{harvsp|Chomette|texte=T. Chomette, Graphes planaires}}).</ref>. Malgré cette remarque, il reste encore une grande quantité de tentatives possibles. La canalisation reliant la première maison au gaz (en suivant l'ordre proposé dans l'illustration du paragraphe ''Énoncés'') peut passer entre l'eau et l'électricité, mais aussi passer entre la première maison et le fournisseur d'eau, ou encore passer par en dessous et contourner par le bas les deuxième et troisième maisons.

Un rapide examen permet de conclure qu'il existe une infinité de possibilités. La canalisation qui relie la première maison et l'électricité peut commencer par faire ''n'' fois le tour des trois maisons puis rejoindre l'électricité. Ces ''n'' tours n'offrent aucun espoir de solution, mais, au premier regard, il ne semble pas simple de trouver un bon critère permettant d'éliminer les tentatives inutiles, ce qui rend l'énigme un peu déroutante. Passer en revue une infinité de possibilités n'est guère praticable<ref group=Note>Il existe deux manières de définir l'homotopie dans le cas de l'article. On peut appliquer le concept aux chemins, deux chemins sont homotopes si l'on peut continument ''déformer'' le premier pour le superposer au second. On peut aussi appliquer le concept au graphe, ce qui revient à pouvoir aussi ''déplacer'' continument les points du graphe. La convention choisie dans ce paragraphe est de n'appliquer l'homotopie qu'aux chemins. Sinon, il n'existe qu'un nombre fini de graphes homotopes.</ref>.

Toutes les tentatives de cette nature débouchent au mieux par la pose de huit canalisations, puis il devient impossible d'aller plus loin. Ce point commun peut laisser penser que la bonne démarche consiste à procéder d'un raisonnement différent. Cette ''bonne démarche'' se fonde sur un concept et un théorème suffisamment intuitif pour qu'une démonstration ne soit pas jugée envisageable<ref>C'est le mathématicien [[Bernard Bolzano]] qui se pose le premier la question : J. Sebestik, ''Logique et mathématique chez Bernard Bolzano'', Vrin, 2002 {{ISBN|978-271161067-9}}, {{p.|26}}.</ref> avant le {{s-|XIX}}. Une réflexion plus approfondie montre qu'il n'en est rien et qu'ils suffisent à bâtir une preuve aisément compréhensible de l'inexistence d'une solution.

=== Ensemble connexe par arcs ===
{{Article détaillé|Connexité par arcs}}
[[File:Ensemble-non-connexe.jpg|thumb|Un archipel forme un ensemble non '''connexe par arc'''. Il n'est pas possible d'aller à pied sec d'une île à l'autre. Chaque île est une '''composante connexe par arc'''.]]
Le concept clé de la démonstration est la connexité. Une illustration du concept est donné par l'archipel des Canaries dans l'image ci-contre. Une île est ''connexe par arcs'', c'est-à-dire que pour tout couple de points de l'île, il existe un chemin allant d'un point à l'autre sans quitter l'île. En revanche, la réunion de deux îles n'est pas connexe par arcs : il n'existe pas de chemins permettant de se rendre entre deux points sans se mouiller, s'ils sont sur deux îles différentes. Une île est une ''composante connexe par arcs'' : c'est un ensemble maximal de points entre lesquels il existe un chemin. Un archipel consiste ainsi en plusieurs ''composantes connexes par arcs'', soit 5 dans l'image ci-contre.

En termes [[mathématiques]], si ''A'' est un ensemble muni d'une [[topologie]] et si, pour deux points quelconque de ''A'', il existe un chemin dans ''A'' qui relie les deux points, ''A'' est dit [[Connexité par arcs|connexe par arcs]].

Un second concept est celui de [[frontière (topologie)|frontière]]. Sur l'exemple de l'archipel, la frontière correspond au littoral, c'est-à-dire à l'ensemble des points qui touchent en même temps une île et la mer. En termes plus mathématiques, un point est à la frontière d'un ensemble ''E'' lorsqu'un [[disque (géométrie)|disque]] centré en ce point et de rayon strictement positif, touche à la fois l'ensemble ''E'' et son complémentaire.

=== Théorème de Jordan ===
{{Article détaillé|Théorème de Jordan}}
[[File:Enigme-des-3-maisons-(3).jpg|thumb|La courbe de Jordan (en noir) divise le plan en deux régions : un « intérieur » (en bleu) et un « extérieur » (en rose).]]
Le théorème clé de la démonstration est encore plus déroutant de simplicité apparente. En substance, il indique qu'il n'est pas possible d'aller de la [[Suisse]] à la France sans traverser la frontière. Pour l'énoncer en termes plus mathématiques, un peu de vocabulaire n'est pas inutile.

Pour établir la démonstration, il faut introduire la notion de [[Théorème de Jordan|courbe de Jordan]], aussi appelée ''lacet simple''. Cette courbe est une ligne continue dans le plan, qui ne se croise pas. Dans la figure de droite, la frontière en noir est un exemple d'une courbe de Jordan. Un cercle est aussi une courbe de Jordan, puisqu'il s'agit toujours d'une ligne continue sans croisement. En revanche, un 8 ne l'est pas puisqu'il y a croisement au centre du 8.

Le théorème de Jordan traite du [[Complémentaire (théorie des ensembles)|complémentaire]] d'une courbe de Jordan ''S''. Le théorème considère la partie du plan qui ne contient pas ''S''. Il indique que ce complémentaire contient deux composantes connexes par arcs, dont la frontière est la courbe ''S''. Sur l'exemple ci-contre, une composante est en bleu tandis que l'autre est en rouge, et la frontière est en noir. Bien que le résultat semble intuitivement évident, sa démonstration ne l'est pas. En effet, il a fallu plus d'un demi-siècle pour l'obtenir. L'élément clé du théorème réside dans la définition de connexité de la section précédente : considérons un point ''a'' dans la zone bleue et un point ''b'' dans la rouge. Si l'on souhaite se rendre de ''a'' à ''b'', il est nécessaire de sortir de la zone bleue, et une frontière est traversée. De même façon, la France peut correspondre à une composante connexe par arcs, la Suisse à une autre, et il n'est pas possible d'aller d'une ville en Suisse à une ville en France sans traverser la frontière. Raisonner en termes de composantes connexes par arcs et de frontière, ou encore d'îles et de littoral permet d'éviter la complexité [[combinatoire]].

=== Placement des six premières canalisations ===
[[File:Enigme-des-3-maisons-(2).jpg|left|thumb|Le théorème de Jordan est utilisable pour résoudre l'énigme de l'article.]]
[[File:Enigme-des-3-maisons-(4).jpg|thumb|En termes de connexité et de frontière, les deux composantes connexes par arcs du plan sont analogues à la figure.]]
Poser une canalisation revient à interdire une zone de l'espace. Si un jeu de canalisation forme une boucle, les idées précédentes sont applicables. On peut, en dessinant la solution sur une feuille de papier, découper les deux zones séparées, bien les éloigner et tenter de résoudre l'énigme sur les différentes ''îles'' ainsi obtenues.

Le principe du raisonnement est [[Raisonnement par l'absurde|par l'absurde]]. On suppose qu'il existe une solution, on montre que cette existence contredit le théorème de Jordan. On en déduit qu'elle ne peut exister car le théorème de Jordan n'est jamais contredit. On utilise les notations suivantes : M<sub>1</sub>, M<sub>2</sub>, M<sub>3</sub> désignent les trois maisons, ''F''<sub>1</sub> le fournisseur d'eau, ''F''<sub>2</sub> celui d'électricité et ''F''<sub>3</sub> celui de gaz.

Le premier objectif consiste à séparer l'espace en deux composantes connexes par arcs, c'est-à-dire à créer deux îles distinctes. Comme on suppose qu'une solution existe, il est possible de considérer la canalisation reliant M<sub>1</sub> à F<sub>1</sub>, à laquelle on adjoint celle reliant F<sub>1</sub> à M<sub>2</sub>, à laquelle on adjoint celle reliant M<sub>2</sub> à F<sub>2</sub>, adjointe à F<sub>2</sub> à M<sub>3</sub>, puis M<sub>3</sub> à F<sub>3</sub>, puis F<sub>3</sub> à M<sub>1</sub>. Elles sont illustrées sur la figure de gauche. On obtient une courbe de Jordan contenant, dans l'ordre, les points M<sub>1</sub>, F<sub>1</sub>, M<sub>2</sub>, F<sub>2</sub>, M<sub>3</sub>, F<sub>3</sub> puis à nouveau M<sub>1</sub>. Si rien ne nous assure que la configuration solution de l'énigme (que l'on suppose exister) est effectivement celle de gauche, nous savons au moins une chose : ces canalisations forment une courbe de Jordan contenant dans l'ordre précédent, les trois maisons et les trois fournisseurs.

[[Image:Projection azimutale stereographique.jpg|thumb]]
Cette courbe divise le plan en deux composantes connexes par arcs, que l'on peut considérer comme deux îles éloignées. Chacune de ces deux composantes connexes par arcs possède une frontière contenant toutes les maisons et tous les fournisseurs. Chacune de ces deux composantes connexes par arcs est analogue à la figure de droite. ''Analogue'' signifie ici que les ensembles sont connexes par arcs et de même frontière.

Si le résultat ne semble pas choquant pour la composante bleue, il peut paraître plus surprenant pour la rose. La composante rose correspond plus à un continent infiniment vaste percé par une mer intérieure qu'à une île. Comme les deux éléments clés sont la connexité et la frontière, cela n'a guère d'importance. Pour s'en persuader, on peut imaginer cette transformation du plan appelée [[Inversion (géométrie)|inversion]], qui laisse invariant le cercle, transforme l'intérieur en extérieur et vice-versa. Cette transformation ne traite pas le centre du cercle. Mais, pour l'énigme, ajouter un [[point isolé]] ne change rien quant à l'existence ou non d'une solution. Il est aisé de le contourner, par la droite ou la gauche. Une autre manière de voir les choses est d'imaginer résoudre l'énigme sur la sphère et non pas le plan. En plaçant la courbe de Jordan sur l'équateur, la similitude entre les deux îles devient évidente. La figure en bas à droite montre qu'une sphère sans son pôle nord peut être vue, à l'aide d'une [[projection stéréographique]], comme un plan. Les deux énigmes sur un plan ou une sphère sont donc équivalentes.

=== Conclusion ===
[[File:Enigme-des-3-maisons-(5).jpg|500px|thumb|center|Après avoir posé la huitième canalisation, le plan est divisé en quatre composantes connexes par arcs.]]
À partir de maintenant, la pose de toute nouvelle canalisation se traduit par un ''coup de ciseau'' qui engendre une nouvelle île. Cette fragmentation de l'espace est à l'origine de l'impossibilité. L'intérêt d'une telle démarche est qu'elle évite toute combinatoire. Comme le montre le paragraphe précédent, prise dans le bon ordre, les six premières poses sont, d'un certain point de vue, ''forcées''. Quelle que soit la manière dont on s'y prend, la pose des six premières canalisations débouche toujours sur la même configuration topologique. À condition de décomposer l'espace en îles telles que le littoral contiennent les nœuds (maisons et fournisseurs), il est possible de se limiter à l'étude d'une unique configuration, pour la suite du raisonnement.

La canalisation fournissant en électricité la première maison est dans l'une des deux composantes connexes par arcs du paragraphe précédent. Notons là ''A''. Cette composante ''A'' contient une ligne reliant ''M''<sub>1</sub> à ''F''<sub>2</sub>, située à l'''[[intérieur (topologie)|intérieur]]'' de ''A'' composée de points soit tous roses soit tous bleus, mais jamais vert. On obtient une nouvelle courbe de Jordan composée de la ligne ''M''<sub>1</sub>''F''<sub>2</sub>, puis des lignes ''F''<sub>2</sub>''M''<sub>3</sub>''F''<sub>3</sub>''M''<sub>1</sub>. Finalement, on obtient la ligne ''M''<sub>1</sub>''F''<sub>2</sub>''M''<sub>3</sub>''F''<sub>3</sub>''M''<sub>1</sub>. Elle définit une nouvelle composante connexe par arcs, notée ''A''<sub>1</sub>. On peut se demander si cette nouvelle île contient les points ''F''<sub>1</sub> et ''M''<sub>2</sub>. On sait déjà qu'ils ne sont pas sur la ligne ''F''<sub>2</sub>''M''<sub>3</sub>''F''<sub>3</sub>''M''<sub>1</sub>. Ils ne peuvent pas non plus se situer sur la ligne ''M''<sub>1</sub>''F''<sub>2</sub> car cette ligne se situe à l'intérieur de ''A'', c'est-à-dire dans l'île ''A'' et non pas sur le littoral, or les points ''F''<sub>1</sub> et ''M''<sub>2</sub> ne sont pas situés sur l'île à proprement parler mais sur la frontière. La même raison indique qu'ils ne peuvent pas non plus se situer à l'intérieur de ''A''<sub>1</sub>. On obtient de même une île ''A''<sub>2</sub>, dont la frontière est formée des canalisations reliant : ''M''<sub>1</sub>''F''<sub>1</sub>''M''<sub>2</sub>''F''<sub>2</sub>''M''<sub>1</sub>. Le théorème de Jordan nous assure encore que ces deux zones sont bien des îles distinctes, c'est-à-dire des composantes connexes par arcs disjointes.

L'espace est maintenant fragmenté en trois îles, dont deux ne contiennent plus que quatre nœuds. Posons maintenant la canalisation qui relie la deuxième maison au gaz. Elle est située dans l'une des trois composantes connexes par arcs. Cette composante connexe par arcs possède une frontière contenant à la fois ''M''<sub>2</sub> et ''F''<sub>3</sub>. Ni ''A''<sub>1</sub> ni ''A''<sub>2</sub> ne possède cette propriété. C'est donc la composante connexe par arcs qui n'a pas été découpée par la canalisation reliant ''M''<sub>1</sub> à ''F''<sub>2</sub> qui contient cette canalisation. Une fois encore, avec le point de vue adopté, ''le coup est forcé''. Si l'on note ''B''<sub>1</sub> et ''B''<sub>2</sub> ces deux nouvelles composantes connexes par arcs, elles ont toutes deux comme frontière une courbe de Jordan et leurs frontières passent, pour ''B''<sub>1</sub> par les points ''M''<sub>1</sub>''F''<sub>1</sub>''M''<sub>2</sub>''F''<sub>3</sub>''M''<sub>1</sub> et pour ''B''<sub>2</sub> par ''M''<sub>2</sub>''F''<sub>2</sub>''M''<sub>3</sub>''F''<sub>3</sub>''M''<sub>2</sub>.

L'espace est maintenant fragmenté en quatre îles, les fournisseurs et les maisons se trouvent toutes sur le littoral et aucune île n'en contient plus de quatre. De plus, on connaît, pour chaque île la nature exacte des fournisseurs et des maisons présentes sur le littoral. Il s'agit maintenant de relier la troisième maison à l'eau. Un rapide passage en revue des différentes frontières montre qu'aucune d'elles ne contient à la fois la troisième maison ''M''<sub>3</sub> et l'eau ''F''<sub>1</sub>.

Cette dernière canalisation parcourt au moins deux composantes connexes par arcs (c'est-à-dire passe d'une île à l'autre sans passer par la mer). Ce résultat est en contradiction avec le théorème de Jordan. Elle termine la démonstration par l'absurde<ref>Cette démonstration s'inspire de {{en}} T. Nishizeki et M. S. Rahman, ''Planar Graph Drawing'', World Scientific Publishing, 2004 {{ISBN|978-981256033-9}}, p. 24.{{refins}}.</ref>.

== Théorie des graphes ==
{{Article détaillé|Graphe planaire}}
[[File:Enigme-des-3-maisons-(6).jpg|left|thumb|La solution en dimension trois existe. Elle ressemble à un tétraèdre auquel on a ajouté deux nœuds et une arète. Les points verts sont les maisons et les jaunes les fournisseurs.]]
Cette énigme entre dans la branche mathématique appelée [[théorie des graphes]] et peut se traiter par la [[Théorème de Descartes-Euler|formule d'Euler]]. Cette formule est un ingrédient de la démonstration du théorème fondamental des graphes planaires. Un graphe est un ensemble de ''points'', parfois appelés ''nœuds'' ou ''sommets'', reliés entre eux par des ''arêtes'' ou des ''liens''<ref>Le vocabulaire est défini dans {{harvsp|Chomette||texte=T. Chomette, ''Graphes planaires''|p=1}}.</ref>. Un graphe est dit « planaire » s'il est possible de le représenter dans un plan. Deux liens ne peuvent se croiser qu'à l'emplacement d'un nœud. Tous les graphes ne sont pas planaires, cette énigme fournit un [[contre-exemple]]. L'origine de l'étude des graphes planaires provient d'un désir de démonstration du [[théorème des quatre couleurs]] au milieu du {{s-|XIX|e}}<ref>Les détails de l'origine de cette question sont traités dans l'article : J. Mayer, [http://archive.numdam.org/ARCHIVE/CSHM/CSHM_1982__3_/CSHM_1982__3__43_0/CSHM_1982__3__43_0.pdf « Le théorème des quatre couleurs : notice historique et aperçu technique »], ''[[Cahiers du séminaire d'histoire des mathématiques]]'', t. 3, 1982, p. 43-62.</ref>. Le théorème clé est l'œuvre de [[Kazimierz Kuratowski]] et date de 1930 : il caractérise, parmi les graphes, ceux qui sont planaires, et s'applique donc au cas particulier de l'énigme<ref>[[Kazimierz Kuratowski|K. Kuratowski]], [http://matwbn.icm.edu.pl/ksiazki/fm/fm15/fm15126.pdf « Sur le problème des courbes gauches en topologie »], ''[[Fundamenta Mathematicae|Fund. Math.]]'', vol. 15, 1930, p. 271-283.</ref>.

Pour comprendre les raisonnements de la théorie des graphes, une définition est utile. Une ''face'' d'un graphe planaire est une composante connexe par arcs du complémentaire du graphe dans le plan. Chaque face possède une frontière composée par des arêtes, le nombre de ces arêtes est appelé le degré d'une face. Si ''f'' désigne le nombre de faces du graphe, ''n'' son nombre de nœuds et ''a'' le nombre d'arêtes, la formule d'Euler affirme que, pour un graphe planaire connexe non vide<ref group=Note>Cette formule est démontrée dans l'article [[Graphe planaire]].</ref> :
<center><math>n-a+f=2</math>.</center>

(Un graphe est connexe s'il existe toujours un ensemble d'arêtes permettant d'aller d'un nœud à un autre.)
Par ailleurs, un rapide calcul montre que la somme des degrés des différentes faces est égale à deux fois le nombre d'arêtes dans un graphe [[coplanaire]]. Or dans la situation des trois maisons, toute courbe de Jordan délimitant une face passe par au moins quatre points du graphe, donc toute face du graphe est de degré au moins 4. En effet, il n'existe aucune canalisation reliant une maison à elle-même, donc le degré un n'est pas possible. Il n'existe pas deux canalisations reliant une même maison à un même fournisseur, le degré deux est encore impossible. Le degré trois suppose que, soit deux maisons, soit deux fournisseurs sont liés par une canalisation, ce qui est toujours impossible. Ceci donne la majoration :
<center><math>4f\le2a\quad\text{donc}\quad2f\le a</math>.</center>

En appliquant cette majoration à la formule d'Euler on obtient :
<center><math>a \le 2n - 4</math>.</center>

Or il existe neuf arêtes, trois par maison et six nœuds dont trois sont des maisons et trois des fournisseurs. La majoration aboutit alors dans le cas d'un graphe planaire à une contradiction : neuf est plus petit que huit. Cette contradiction montre que le graphe recherché ne peut être planaire<ref>On trouve ce raisonnement dans {{harvsp|Chomette||texte=T. Chomette, ''Graphes planaires''|p=7}}.</ref>.

== Solutions avec d'autres géométries ==
=== Ruban de Möbius ===
[[File:Enigme-des-3-maisons-(7).jpg|left|thumb|Sur un [[ruban de Möbius]], une solution existe.]]
[[File:Enigme-des-3-maisons-(8).jpg|right|180px]]
L'impossibilité de résoudre l'énigme est une conséquence du théorème de Jordan. Une géométrie pour laquelle une solution existe doit donc admettre des courbes de Jordan qui ne divisent pas l'espace en deux composantes connexes par arcs. Comme le montre le paragraphe intitulé ''Topologie géométrique'', la recherche d'une solution sur une [[sphère]] est vaine, une méthode rapide pour s'en convaincre est de remarquer que le théorème de Jordan est valide sur cette géométrie.

En revanche, le théorème ne s'applique pas si l'espace n'est pas [[Orientation (mathématiques)|orientable]]. Dans un espace non orientable, le côté droit de certaines courbes finit par devenir le côté gauche. Autrement dit, le concept de droite et de gauche n'a pas de sens sur un tel espace. Tel est le cas sur un [[ruban de Möbius]]<ref>{{ouvrage|auteur1=Richard K. Guy|auteur2=Robert E. Woodrow|langue=en|titre=The Lighter Side of Mathematics|sous-titre=Proceedings of the Eugene Strens Memorial Conference on Recreational Mathematics and Its History|édition=American Mathematical Society|année=1994|page=292|présentation en ligne=https://books.google.fr/books?id=FsH2DwAAQBAJ&pg=PA292&redir_esc=y#v=onepage&q&f=false}}</ref>. La ligne à égale distance des deux bords possède cette propriété. Placer les trois maisons et les trois fournisseurs sur une telle ligne, à l'image de la figure de gauche, est judicieux<ref group=Note> Pour mieux modéliser la ''surface'', il est judicieux de la réaliser à l'aide d'un papier transparent, type papier calque.</ref>. Les six premières canalisations n'ont alors pas ''coupé'' la géométrie en deux composantes connexes par arcs.

Pour comprendre ce qu'il advient une fois ces six premières canalisations posées, le plus simple est de construire un ruban de Möbius, de dessiner les différents nœuds et de ''couper'' effectivement le ruban. On obtient la figure en haut à droite (on n'a pas représenté la double torsion induite par le découpage dans la mesure où celle-ci ne change pas la résolution de l'énigme). Le ruban devient un unique nouveau ruban, deux fois plus long et deux fois moins large. Une des frontières du ruban contient maintenant deux séries des six nœuds à la suite l'une de l'autre.

Pour une raison de simplicité, il est plus simple de ''déformer'' le cylindre obtenu. On ''resserre'' la frontière ne contenant pas les nœuds jusqu'à ce que cette frontière soit réduite à un point, on ajoute alors ce point (on a vu précédemment que cela ne change rien à la résolution de l'énigme) pour obtenir un [[cône (géométrie)|cône]]. Aplatir ce cône, ce qui ne change encore rien à l'existence ou l'absence de solution, donne la figure en bas à droite<ref group=Note>Ces différentes transformations correspondent à ce que l'on appelle en mathématiques des [[homéomorphisme]]s. On démontre rigoureusement qu'appliquer un homéomorphisme à un espace ne modifie pas la nature de la question.</ref>. Il devient aisé de trouver comment placer les trois dernières canalisations. La solution en bas à droite est celle qui est illustrée à gauche, une fois réalisées les transformations inverses{{refinc|<ref>Les éléments pour résoudre cette énigme sur un ruban de Möbius sont donnés et la question est proposée sous forme d'exercice : M. Habib, ''[http://www.liafa.jussieu.fr/~habib/Documents/cachangraphes.pdf Notes de cours algorithmique de graphes]'', Magistère informatique Cachan.</ref>}}.

=== Tore ===
[[File:Enigme-des-3-maisons-(9).jpg|left|thumb|Le tore ne vérifie pas le théorème de Jordan. La courbe de Jordan verte ne divise pas le tore en deux composantes connexes par arcs.]]
[[File:Enigme-des-3-maisons-(10).jpg|right|180px]]
Le ruban de Möbius est un exemple de surface qui ne satisfait pas le théorème de Jordan car il n'est pas orientable. D'autres surfaces sont orientables et ne satisfont néanmoins pas le théorème. C'est le cas du [[tore]]. Il existe cette fois, non pas un, mais deux types de courbes de Jordan dont le complémentaire est connexe par arcs. Pour cette raison, il est possible de résoudre l'énigme<ref>Ce contournement est fréquent, même dans les sites populaires, comme celui du professeur de mathématiques L. Lafaye, ''[http://lionel.lafaye.free.fr/nouvellepage10.htm Notions de graphes]''.</ref>, même avec quatre maisons et quatre fournisseurs. Le fait de considérer une géométrie contenant un ''trou'', comme le tore autorise la représentation de graphe non planaire. Tout graphe se représente sur une surface ayant un ''nombre de trous'', encore appelé ''[[genre (mathématiques)|genre]]'' de la surface<ref name=Harary_Hill>{{en}} F. Harary A. Hill, ''On the number of crossings in the complete graph'', Proc. Edimburgh Math. Soc., '''13''' (1963), p. 333-338</ref>, suffisamment élevé. Sur une telle surface, et à condition de s'y prendre convenablement, il existe deux courbes de Jordan qui ne créent pas de nouvelles faces, l'équation d'Euler s'écrit alors ''n''&nbsp;-&nbsp;''a''&nbsp;+&nbsp;''f''&nbsp;=&nbsp;0. S'il existe quatre maisons et quatre fournisseurs, le graphe est composée de huit nœuds et seize arêtes, ce qui implique l'existence de huit faces. Le nombre moyen d'arêtes par face est le double du nombre d'arêtes, on trouve donc comme valeur moyenne quatre. Comme c'est aussi le nombre minimal d'arêtes pour une face, la solution ne comporte que des faces à quatre arêtes.

La première courbe de Jordan est illustrée sur la figure en haut à gauche. Comme pour le ruban de Möbius, on obtient un cylindre, illustré à droite. Cette fois-ci, les nœuds ne se trouvent pas tous en haut mais une série est sur la frontière haute et une sur la frontière basse. La technique précédente, pour transformer le cylindre en disque reviendrait à identifier les différents nœuds en un unique point, ce qui n'est pas acceptable. En revanche, il est possible d'établir un lien entre le nœud ''M''<sub>1</sub> situé en bas (avec les notations précédentes ''M''<sub>1</sub> correspond à la première maison. Les maisons sont illustrées en bleu sur les figures) et le nœud ''F''<sub>2</sub> (qui désigne le deuxième fournisseur. Les fournisseurs sont illustrés en rouge sur les figures). Ce lien est illustré en vert sur la figure en haut à droite. On obtient alors une figure comparable à un disque. Ce disque, illustré en bas à droite, comporte dix-huit nœuds. Chaque nœud est représenté deux fois, à l'exception des nœuds ''M''<sub>1</sub> et ''F''<sub>2</sub> qui le sont trois fois. La zone supérieure est représentée en gris clair et celle inférieure en gris foncé. Sous cette forme de disque, trouver la bonne configuration est aisée<ref name=Harary_Hill/>.

On peut se demander si une solution existe pour cinq fournisseurs et cinq maisons. Le même calcul montre que le nombre moyen d'arêtes par face est égal à dix tiers, soit strictement inférieur à quatre. Or quatre est le minimum d'arêtes pour construire une face pour cette énigme. La recherche d'une solution est donc vaine.
{{Démonstration|titre=Construction de la solution|contenu=
Un raisonnement simple permet de déterminer la bonne configuration et sans tâtonnement. La première courbe de Jordan fournit huit liens. Le neuvième lien transforme la question en un problème plan. Il reste encore sept liens à placer et l'on sait déjà que chaque face (c'est-à-dire chaque composante connexe par arcs du complémentaire) est bordée par exactement quatre liens.

Sous sa forme de disque, on dispose de dix-huit nœuds, qui sont des répétitions des huit nœuds présents sous la forme du tore. Ils sont répétés deux fois, à l'exception des nœuds ''M''<sub>1</sub> et ''F''<sub>2</sub> qui sont répétés trois fois. Sous la forme du disque, l'ajout d'un lien, pour créer des faces contenant quatre liens, se traduit par la pose d'une canalisation qui ''saute'' deux nœuds pour se connecter au suivant. Comme, in fine, ce sont les seuls faces qui existent, il est inutile de rechercher d'autres types de pose de canalisation. Placer un lien rend alors inaccessible, sous la forme du disque, les deux nœuds qu'il enserre.

::* '''Liens dix à douze :'''
:Les nœuds ''M''<sub>1</sub> et ''F''<sub>2</sub> disposent de deux spécificités, non seulement ils sont présents trois fois sous la forme de disque, mais, sous la forme torique, ils disposent déjà de trois liens sur quatre. Il est possible, sans dommage, d'enserrer par au moins deux liens ces deux nœuds. Il en restera toujours une instance pour fournir les liens encore manquants. Il existe sur le disque deux séries de nœuds ''M''<sub>1</sub> et ''F''<sub>2</sub> adjacents. Celle du haut sur la figure représentant le disque avec les dix-huit nœuds conduit à la création d'un lien ''M''<sub>2</sub>''F''<sub>1</sub> inutile car déjà existant. Celle du bas permet de créer le lien manquant ''M''<sub>4</sub>''F''<sub>3</sub>, c'est celui-ci qu'il faut choisir pour dixième lien.

:Les nœuds ''M''<sub>4</sub> et ''F''<sub>3</sub> sont maintenant présents deux fois sur le disque et disposent de trois liens sur quatre dans le tore. On peut donc enserrer une instance de chacun de ces deux nœuds ''M''<sub>4</sub> et ''F''<sub>3</sub> sans dommage. Il est encore possible d'enserrer une instance des nœuds ''M''<sub>1</sub> et ''F''<sub>2</sub> car il reste deux instances disponibles alors qu'un unique lien est manquant pour chacun de ces deux nœuds. On en déduit les deux autres liens, illustrés sur le disque à dix-huit nœuds, en vert. Ce sont les liens onze et douze.

::* '''Quatre derniers liens'''
[[File:Enigme-des-3-maisons-(11).jpg|right|200px]]
:Pour y voir plus clair, le plus simple est de dessiner ce qu'il reste de la plus grande composante connexe par arcs après la pose des douze premières canalisations, illustrée sur la figure de droite. Chaque nœud (vu du point de vue du tore) dispose maintenant de trois liens et il ne manque plus qu'un lien par nœud, or quatre nœuds sont encore représentés deux fois : ''F''<sub>1</sub>, ''M''<sub>2</sub>, ''F''<sub>3</sub> et ''M''<sub>4</sub>. Ce sont donc ces liens qu'il faut enserrer. Il existe deux manières d'enserrer les liens ''F''<sub>1</sub> et ''M''<sub>2</sub>. Les deux débouchent chacune sur une solution acceptable. On choisit de poser la canalisation ''M''<sub>1</sub>''F''<sub>3</sub> en haut à droite, qui devient à treizième. Il n'existe alors plus qu'une solution pour enserrer les liens ''F''<sub>3</sub>''M''<sub>4</sub>, la quatorzième canalisation relie ''M''<sub>3</sub> à ''F''<sub>1</sub>. Les deux dernières sont évidentes et illustrées sur la figure de droite.
[[File:Enigme-des-3-maisons-(12).jpg|thumb|400px|left|Pour obtenir le tore à partir des figures, il suffit de ''coller'' l'arête inférieure du rectangle sur son arête supérieure, puis de ''coller'' l'arête de droite, qui est devenue un cercle sur celle de gauche. Les côtés supérieurs et inférieurs du deuxième tore correspondent au cercle de plus petit diamètre du tore.]]
Il reste encore à ''remonter'' la solution sur le tore. La convention choisie consiste à représenter un ''côté'' de la première courbe de Jordan en gris foncé et l'autre en gris clair. Les canalisations qui restent proches de la première courbe de Jordan restent sur la même couleur, les autres sont celles ''qui font le tour du tore'', à l'image de la neuvième canalisation. On obtient la première figure de gauche.

Cette solution n'est encore guère satisfaisante pour comprendre véritablement comment s'organisent les canalisations sur le tore. La représentation géométrique est plus simple en positionnant les nœuds de manière plus ''géométrique''. Posons le tore à plat sur un plan horizontal. Sur le cercle de plus haute altitude, plaçons 4 nœuds sur deux diagonales orthogonales, de manière qu'une diagonale supporte deux maisons et l'autre deux fournisseurs. Le cercle correspond aux quatre premières canalisations. Sur le cercle de plus basse altitude, on agit de même, puis on pivote les quatre nouveaux nœuds d'un quart de tour, le cercle de basse altitude correspond à quatre canalisations supplémentaires. En reliant par l'intérieur un nœud au nœud situé exactement au-dessous, on obtient encore quatre canalisations. Pour les quatre dernières, imaginons que les canalisations soient élastiques, on relie, à l'aide de quatre canalisations les quatre nœuds supérieurs aux quatre nœuds inférieurs en passant par l'extérieur, puis une rotation d'un demi-tour est appliquée aux extrémités inférieures des quatre derniers nœuds. Cette configuration est représentée sur la figure la plus basse. Les huit faces, seize arêtes et huit nœuds sont plus aisément visibles. Les huit liens sombres correspondent à la première courbe de Jordan.
}}

== Notes et références ==
[[File:Enigme-des-3-maisons-(1).jpg|thumb|Cette solution n'est généralement pas considérée comme acceptable. Elle est vraie si les maisons et usines sont des surfaces et non des points, autrement dit, si le problème est mal énoncé.]]

=== Notes ===
{{références|groupe=Note}}

=== Références ===
{{Références}}

== Voir aussi ==

=== Bibliographie ===
* {{Ouvrage|prénom1=T.|nom1=Chomette|année=<!--?-->|url=http://www.dma.ens.fr/culturemath/maths/pdf/combi/planaire.pdf |format électronique=Pdf |titre=Graphes planaires|éditeur=cultureMATH}}
* {{en}} J. L. Gross et T. W. Tucker, ''Topological Graph Theory'', Courier [[Dover Publications]], 2001 {{ISBN|978-048641741-7}}.
* J.-C. Novelli, ''Quand les chemins ne se croisent pas'', Les Graphes, de la [[théorie des jeux]] à l'intelligence artificielle (Bases pour terminale ES. Approfondissements), numéro hors série du journal ''Tangente'', 2002 {{ISBN|978-290973785-0}}.

=== Articles connexes ===
* [[Graphe planaire#Caract.C3.A9risation de Kuratowski et de Wagner|Théorème de Kuratowski]] (caractérisant les [[graphe planaire|graphes planaires]])
* [[Théorème de Robertson-Seymour]] (une vaste généralisation du théorème précédent)

=== Liens externes ===
* {{MathWorld|nom_url=UtilityGraph|titre=Utility Graph}}

{{Portail|géométrie|logique}}

[[Catégorie:Jeu mathématique]]
[[Catégorie:Casse-tête]]
[[Catégorie:Topologie]]
[[Catégorie:Théorie des graphes]]