Trois couples se construisent chacun un chalet sur un terrain en copropriété. Ils doivent chacun brancher leur chalet à la prise d’eau, à la prise d’électricité et à l’égout municipal. Ils s’aperçoivent qu’ils ne peuvent le faire sans que les branchements se croisent. Effectivement, ce n’est pas possible dans l’univers où nous vivons. Mais c’est possible dans d’autres univers.
Dans un premier temps, le chalet rouge est branché à l’eau et l’électricité, le chalet vert, à l’eau et à l’égout, et le chalet bleu, à l’électricité et à l’égout. Si l’on suit ces branchements, ils forment une courbe fermée comme sur la figure.
Cette courbe fermée a un intérieur et un extérieur. Branchons maintenant le chalet rouge à l’égout. On a deux choix, soit le branchement se fait à l’intérieur de la courbe fermée, soit il se fait à l’extérieur. Prenons le premier cas.
Maintenant, pour brancher le chalet vert à l’électricité, on n’a pas de choix : il faut le faire par l’extérieur.
Mais, maintenant il n’est plus possible de brancher le chalet bleu à l’eau, ni par l’intérieur, ni par l’extérieur, sans croiser un branchement existant. Le deuxième cas aurait abouti à la même conclusion. Si vous n’êtes pas convaincu, essayez-le !
Modélisation par un graphe
On construit un graphe à six sommets divisés en deux sous-groupes :
- les trois chalets d’une part,
- les prises d’eau, d’électricité et l’égout d’autre part.
Les arêtes du graphe sont les branchements. On n’a aucune arête entre deux sommets d’un même groupe. Ce graphe a la particularité qu’il n’a aucune arête entre deux sommets d’un même sous-groupe : un tel graphe est dit biparti. On a une arête entre chaque sommet du premier groupe et chaque sommet du deuxième graphe: ce graphe est appelé \(K_{3,3}\) parce que chaque sous-groupe contient trois sommets. Il est connu que le graphe \(K_{3,3}\) ne peut être dessiné dans un plan sans que des arêtes se croisent. On dit que \(K_{3,3}\) n’est pas planaire.
Un graphe est complet si chaque sommet est relié à tous les autres sommets par une arête. Le graphe complet à \(k\) sommets est appelé \(K_k\). Il est facile de vérifier que \(K_2, K_3\) et \(K_4\) sont planaires. Par contre, \(K_5\) n’est pas planaire.
La question de savoir si un graphe est planaire est importante pour l’impression de circuits électroniques sur une carte de circuit imprimé. Les connexions ne doivent pas se croiser si l’on veut éviter les court-circuits. Un des grands résultats de théorie des graphes dit que tout graphe non planaire contient une copie de \(K_{3,3}\) ou de \(K_5\).
Migrer sur un ruban de Möbius
Nos trois couples décident alors de déménager sur un ruban de Möbius. Un tel ruban se construit en prenant une bande de papier et en traçant la ligne milieu de la bande. En recollant les deux extrémités avec un demi-tour, cette droite donne une courbe fermée.
Comme précédemment, on peut placer six branchements sur la ligne milieu, et on peut rajouter deux autres branchements.
Voici ce que cela donne sur la bande de Möbius.
Et maintenant, il nous manque un branchement entre le chalet rouge et l’égout.
En voici un en trait rouge !
Et un deuxième !
Voici ce que cela donne en trois dimensions.
Remarquons que dans ce nouvel univers, la courbe n’a plus qu’un seul côté. C’est pour cela qu’on peut passer sans problème le dernier branchement.
On peut aussi migrer sur un tore
En mathématiques, ce qu’on appelle un tore est la surface d’un beigne avec un trou. Abstraitement, on le représente par un carré ou un rectangle, dans lequel on colle les côtés horizontaux, ce qui donne un cylindre, et ensuite les côtés verticaux.
Pour la suite, on va plutôt utiliser un rectangle. La ligne horizontale des six branchements
représente un cercle sur le tore ci-contre. Et maintenant, il faut rajouter les trois autres branchements. Les voici.
Et voici, à droite, ce que cela donne sur le tore.
Alors, sur quel univers choisirez-vous de vous établir ?
