problème des trois maisons

Imaginez trois maisons et, un peu plus loin, trois arrivées : eau, gaz et électricité. Chaque maison doit recevoir les trois services. Sur une feuille, cela oblige à tracer neuf raccordements, sans qu'un trait traverse un autre trait ni un point qui n'est pas son extrémité.

On peut courber, allonger et déplacer les traits autant que l'on veut : dans le plan, un croisement subsiste toujours. L'obstacle ne vient donc pas d'un manque d'adresse au dessin, mais de l'organisation même des six points et des neuf liaisons.

Le problème se modélise par un graphe : les trois maisons forment un premier groupe de sommets, les trois réseaux un second, et chaque raccordement devient une arête. Toute maison étant reliée à tout réseau, on obtient le graphe biparti complet K_3,3. Il possède six sommets et neuf arêtes. Aucune arête ne relie deux maisons ni deux réseaux.

Un graphe est planaire lorsqu'il admet au moins un dessin dans le plan où les arêtes ne se rencontrent qu'à une extrémité commune. Un dessin particulier avec des croisements ne suffit donc pas à conclure : il faut savoir si un autre placement des sommets et un autre tracé des arêtes peuvent tous les éviter. La forme ou la longueur des raccordements ne change pas la question.

Pour un graphe planaire simple et biparti comportant au moins trois sommets, si le nombre de sommets est noté n et le nombre d'arêtes m, l'absence de cycles de longueur trois impose le critère suivant : $m\le 2n-4m\; \backslash leq\; 2n-4$. Avec K_3,3, les valeurs n = 6 et m = 9 contredisent ce critère, puisque 9 est supérieur à 8. Le raccordement demandé est donc impossible dans le plan.

Reprenons les trois maisons et les trois réseaux. Les données sont six sommets répartis en deux groupes de trois, ainsi que neuf raccordements exigés. La figure matérialise ces neuf relations ; ses croisements visibles illustrent le problème, tandis que le calcul démontre qu'aucun autre tracé plan ne peut tous les supprimer.

1. Comptez les sommets : n = 3 + 3 = 6.
2. Comptez les arêtes : chacune des trois maisons demande trois raccordements, donc m = 3 × 3 = 9.
3. Appliquez la borne des graphes planaires simples et bipartis :

4. Or le raccordement en exige neuf : $9\nleqq 89\; \backslash nleq\; 8$. La condition nécessaire à un dessin planaire échoue. Le contrôle est refaisable directement : six sommets donnent au plus huit arêtes dans ce cadre, alors que la liste des besoins en contient neuf.

Devant une énigme de raccordements, remplacez chaque objet par un sommet et chaque liaison demandée par une arête. Cette modélisation est préférable aux essais successifs lorsque seuls les contacts comptent, et non la longueur ou la forme des tracés.

Pour contrôler un dessin proposé, suivez chaque arête d'une extrémité à l'autre. Une rencontre est autorisée à un sommet commun ; ailleurs, elle constitue un croisement. Si le dessin croise, tentez un autre tracé avant de conclure, car un mauvais dessin ne prouve pas qu'un graphe est non planaire.

Lorsque le graphe est simple et biparti, comptez ses sommets et ses arêtes. La borne m ≤ 2n − 4 peut alors écarter immédiatement la possibilité d'un dessin plan ; si elle est respectée, elle ne suffit pas à garantir la planarité et il faut poursuivre l'analyse.

Un graphe non planaire et un dessin qui se croise. Un dessin maladroit peut croiser même si le graphe est planaire. Pour trancher, il faut trouver un dessin sans croisement ou établir qu'aucun n'existe ; K_3,3 relève du second cas.

K_3,3 et K₃. K_3,3 relie chacun des trois sommets d'un groupe à chacun des trois sommets de l'autre, soit neuf arêtes. K₃ est seulement un triangle à trois sommets et trois arêtes, que l'on dessine sans croisement.

Le problème des trois maisons et celui des ponts de Königsberg. Le premier demande si toutes les arêtes peuvent être dessinées sans croisement. Le second porte sur un parcours des arêtes. Un tracé sans croisement et un parcours possible sont deux propriétés différentes.

Sortir du plan change la question. Un pont, un tunnel ou un raccordement passant dans une troisième dimension peut éviter une intersection apparente. Il ne résout pas l'énigme originale, qui interdit précisément ce changement de support.

Un raccordement ne traverse pas un autre sommet. Faire passer une conduite par une maison ou une source à laquelle elle n'est pas reliée crée une incidence supplémentaire. Le dessin ne représente alors plus K_3,3.

Retirer une exigence modifie le cas charnière. Avec les neuf raccordements, K_3,3 est non planaire. Si une seule des neuf arêtes est supprimée, le graphe restant peut être dessiné dans le plan ; ce succès ne vaut donc pas pour l'énoncé complet.

La borne fournit une obstruction, pas une réciproque. Dépasser 2n − 4 interdit la planarité d'un graphe simple biparti. Rester sous cette borne ne prouve pas à lui seul qu'un dessin sans croisement existe.

Le glossaire graphe planaire précise la propriété dont K_3,3 fournit ici un contre-exemple classique.

L'entrée graphe biparti développe la séparation des six sommets en deux groupes, au cœur de la modélisation des maisons et des réseaux.

La fiche ponts de Königsberg montre une autre énigme devenue question de graphes, mais centrée sur le parcours des arêtes.