Gribouillages
Munissez-vous d'un stylo et d'un bout de papier, nous allons (re)découvrir ensemble un très chouette théorème dû à Euler (ou à Descartes, l'Histoire n'a pas encore bien statué sur la question) : la formule de (Descartes-)Euler ! On peut même faire passer ça pour un tour de magie auprès des jeunes générations. J'en ai déjà parlé à de multiples reprises sur ce blog, mais un beau théorème comme celui-ci devait d'avoir un article pour lui tout seul. Aujourd'hui, ça sera son grand jour !
Mais avant ça, j'aimerais poser une énigme qui n'a rien à voir (ou pas) : l'énigme des 3 maisons (alias énigme de l'eau, du gaz et de l'électricité). Dans une petite bourgade, 3 familles fraichement propriétaires désirent se raccorder en eau, en électricité et en fibre optique, directement sur les 3 usines voisines. Les 3 familles se détestant profondément, elles ne souhaitent pour rien au monde que les raccordement se chevauchent... Comment Julien Courbet va résoudre ce problème de voisinage ?
Comment raccorder chaque maison à chaque usine sans qu'aucun des chemins ne se croisent ?
Le temps de cette petite énigme, j'espère que vous avez eu le temps de vous saisir d'un crayon de bois et d'un vieux post-it, car c'est maintenant qu'il faut le gribouiller. N'importe comment. La seule chose qui importe, c'est que le gribouillage soit en un seul morceau (connexe). Par exemple, vous pouvez faire un truc comme ça :
Ceci n'est rien d'autre qu'un gribouillage rouge
C'est maintenant qu'on va faire des maths ! Dans ce gribouillage, on peut repérer des "sommets" (les points d'intersection et les extrémités), des "arrêtes" (ce qui relie deux sommets) et des "faces" (les cellules, délimitées par des arrêtes. Au passage, l'extérieur de la figure est une face). Comptez-les ! (Et notez S le nombre de sommets, A le nombre d'arêtes et F le nombre de faces)
Moi, je compte S=26 sommets (bleus), A=49 arrêtes (rouges) et F=25 faces (verts)
Attention, tour de magie qui n'impressionnera personne. Je suis sûr que si vous effectuez l'opération S-A+F, vous trouverez... 2 ! (Ça marche même dans mon exemple : 26-49+25 = 2)
S - A + F = 2
Hey, ça me rappelle un truc avec les polyèdres, non ?...
Toutafé ! La formule "nombre de sommets - nombre d'arêtes + nombre de face = 2" est surtout connue pour fonctionner sur les polyèdres (sur certains polyèdres, pour être plus précis). Prenons par exemple un triacontaèdre rhombique (plus connu chez les rôlistes par le nom de "dé à 30 faces");
Un triacontaèdre rhombique, formé par 30 losanges. Qui tourne.
En comptant minutieusement, on dénombre 32 sommets, 60 arrêtes et 30 faces : 32-60+30=2, tout va bien.
Mais si ça marche sur les gribouillages et sur les polyèdres, c'est qu'il y a un lien... Non ?!...
Toutafé ! Pour être plus précis, si ça marche sur les polyèdres, c'est parce que ça marche sur les gribouillages. Mais je vais arrêter de dire gribouillage et plutôt dire "graphe planaire", ça fait plus sérieux. (un graphe est ce que l'on obtient quand on relie des sommets par des arêtes. Il est planaire quand les arrêtes ne se croisent pas.)
Petite interlude historique. Quand Euler découvre cette propriété des polyèdres vers 1750, il s'empresse de le raconter par lettre à son ami Goldbach. A ce stade là, aucune démonstration n'existe encore. Il faudra attendre 1810 pour qu'une première démonstration apparaisse, celle de Cauchy. Tout un tas de démonstrations ont suivi, avec plus ou moins de renommée. En fait, la propriété découverte par Euler existait déjà depuis plus d'un siècle, dans des notes prises par Descartes (lesquelles notes n'ont été redécouvertes qu'en 1860, ce qui explique que Euler n'en ait jamais entendu parler).
Il y a plusieurs façons de passer de la 3D à la 2D. La méthode la plus simple, c'est celle qui intervient dans la démonstration de Cauchy. On part d'un polyèdre, et on lui retire l'une de ses faces (ce qui change son nombre F de faces, mais on va s'arranger avec ça à la fin). On peut toujours élargir le trou formé par la face qui manque, ça ne va pas changer S-A+F. Quand le trou est suffisamment écarté, on peut aplatir le polyèdre sur la face manquante. Les faces, arrêtes et sommets du polyèdre deviennent alors celle d'un graphe planaire. La face que l'on a supprimé au début devient la face extérieure du graphe planaire. Il n'y a plus qu'à démontrer le théorème sur le graphe planaire que l'on obtient.
1 - Exemple avec un cube :
2 - On enlève la face arrière
3 - On l'élargit un peu
4 - On aplatit le tout
Autre façon de procéder, toujours en partant de la figure 3D : on peut gonfler le polyèdre comme un ballon ! On obtient alors une sphère sur laquelle sont dessinées des segments sphériques. Par une projection stéréographique, on peut transformer cette sphère en le plan, ce qui permet à nouveau d'obtenir une version plane du polyèdre initial. Mais comme c'est difficile à dessiner et que je manque de temps et/ou de logiciel adapté, je n'en dirai pas plus sur cette méthode.
Bref, y'a plus qu'à démontrer la formule d'Euler sur les graphes planaires...
Chouette, une démonstration !
La formule d'Euler fait partie de ces théorèmes multipliant les démonstrations différentes. Il y a notamment celle de Cauchy, qui fait appel à la récurrence et à des triangulations.C'est la plus intuitive de toutes. Il y a aussi celle que l'on trouve dans le bouquin d'Audin (je ne connais pas l'origine de cette démo), qui utilise la formule de Girard, et encore des triangulations. Sauf que les démonstrations par triangulation, il commence à en avoir un peu trop sur ce blog (voir là ou là, par exemple). Voici donc une démonstration de la formule d'Euler sur les graphes planaires, sans triangulation, ni récurrence ! (Pour être précis, c'est celle de l'allemand von Staudt)
Considérons donc un graphe planaire G. Par exemple, celui-ci.
Le graphe G
De ce graphe, on va extraire un sous-arbre couvrant T (T est le plus grand sous-graphe de G qui ne possède aucune boucle. On peut l'obtenir en supprimant progressivement les boucles du graphe original). On va aussi considérer le graphe dual G' de G (on l'obtient en plaçant un sommet sur chaque face de G, et on relie deux sommets dans G' si les faces correspondantes dans G sont adjacentes), et on considère l'arbre couvrant T' qui correspondant aux arrêtes oubliées par T'. (c'est un arbre couvrant : A n'ayant pas de boucle, il relie toutes les faces, et si A' avait une boucle, A ne serait pas un arbre couvrant)
En bleu, le graphe G ; en traits plein bleu l'arbre couvrant T
En vert, le graphe G' ; en traits plein verts l'arbre couvrant T'
On va appeler S, A et F le nombre respectif de sommets, arrêtes et faces de G, on appelle a le nombre d'arêtes de T et a' le nombre d'arêtes qui sont dans G sans être dans T (par construction, c'est le nombre d'arêtes de T'). On regarde ce que ça donne sur T et T' :
T possède 1 face, S sommets et a=S-1 arrêtes (si un arbre a n arêtes, il aura n+1 sommets).
T' possède 1 face, F sommets (c'est le dual de G) et a'=F-1 arêtes
Puisque A=a+a', on trouve donc que A=S-1+F-1. Autrement dit... S-A+F=2 !
CQVSAD(BAC)
Ce que Von Staudt a démontré (bien après Cauchy)
Trois maisons, trois services publics...
Revenons à notre énigme des trois maisons, que l'on attribue au poseur de casse-tête Henry Dudeney (en 1917). Posé dans le langage de la théorie des graphes, l'énigme consiste à rendre planaire le graphe appelé K3,3 :
Le graphe K3,3
On a 9 arêtes et 6 sommets. C'est là que l'on peut faire intervenir la formule d'Euler : si une solution existe, elle délimitera 5 faces. D'un autre côté, le nombre moyen d'arêtes par faces est donné par Fm=2A/F (car chaque arrête intervient dans la délimitation de exactement 2 faces). Dans le cas de K3,3, on trouve Fm = 18/5 =3.6 . Sauf que, au minimum, les cycles (qui délimitent les faces) ont une longueur de 4 arêtes : il est impossible d'obtenir une version planaire du graphe K3,3, et les trois voisins ne pourront jamais se mettre d'accord...
On peut aussi montrer que le problème n'a pas de solutions en utilisant des arguments plus topologiques, mais ce n'est pas l'objet de l'article d'aujourd'hui. En parlant de topologie, on pourrait aussi parler de ce que devient la formule d'Euler quand on l'utilise dans d'autre espace topologie (genre un tore, ou un espace de dimension quelconque...), mais j'ai un peu la flemme d'en dire plus...
Sources :
- Wikipédia, pour l'illustration du triacontaèdre rhombique, et de quelques infos à droite à gauche. On peut aussi consulter l'article sur la formule d'Euler pour voir la démonstration de Cauchy.
- Raisonnements divins, par Martin Aigner, Günter M. Ziegler, pour la démonstration de Von Staudt, et celle du problème des trois maisons.
- Géométrie, de Michèle Audin, pour la démonstration sur les polyèdres sans passer par les graphes