Devinette multicolore

Piste verte Le 4 février 2010  - Ecrit par  Charles Boubel Voir les commentaires (1)

Voici des photos, sous plusieurs angles, d’un anneau de bois que j’ai peint. Saurez-vous trouver ce que ce coloriage a de particulier ? Bien sûr, le mieux serait de tenir l’objet en main, ce qu’ont pu faire les visiteurs de la fête de la science 2008 à Strasbourg, pour laquelle j’ai réalisé [1] cet objet. La réponse est donnée après les photos.

Un indice : cliquer pour déplier.

Combien y a-t-il de zones colorées ? Quelles sont les zones frontalières d’une zone de couleur donnée ?

Un indice plus précis : cliquer pour déplier.

Sur l’avant-dernière photo, on voit toutes les zones que touche la zone rouge  : lesquelles sont-elles ? Sur la dernière photo, on voit toutes les zones touchées par la zone blanche : lesquelles ? Semblablement, observez la zone bleue et la zone verte sur la cinquième photo à partir de la fin. Vous pouvez enfin vérifier le même phénomène pour toutes les zones.

On peut aussi tourner autour de l’anneau posé sur une table, sur une de ses faces :

et posé sur l’autre de ses faces :

Après cette visite, vous avez deviné je pense. La surface de l’anneau est partagée en sept zones de sept couleurs différentes, et chaque zone touche toutes les autres. Ce présent billet est donc un écho à un précédent article de ce site. Cet article évoquait le célèbre théorème des quatre couleurs :

  • On remarque facilement que certaines cartes nécessitent quatre couleurs pour que deux pays voisins soient toujours de couleur différente. Regardez par exemple une carte représentant l’Allemagne, la Belgique, le Luxembourg et la France. Chaque pays touche les trois autres, il faut au moins quatre couleurs.
  • Dans l’autre sens, et c’est très difficile à montrer, n’importe quelle carte dessinée sur une sphère ou sur un plan peut être coloriée avec seulement quatre couleurs, de sorte que deux pays voisins soient toujours de couleur différente.

La surface de l’anneau présentée ici montre donc que, si quatre couleurs suffisent toujours pour colorier les cartes dessinées sur une sphère ou un plan, ce n’est plus forcément vrai pour des cartes tracées sur d’autres surfaces. La surface d’un anneau s’appelle un tore :

  • Comme ici chacune des sept zones touche toutes les autres, sept couleurs au moins sont nécessaires pour colorier cette carte tracée sur le tore.
  • On peut montrer par ailleurs, mais c’est difficile, que n’importe quelle carte dessinée sur un tore peut être coloriée avec seulement sept couleurs. Un « théorème des sept couleurs » est vrai pour le tore.

La géopolitique terrestre n’est pas simple, mais estimons-nous heureux de ne pas habiter une planète torique, où les problèmes de voisinage peuvent être encore plus complexes !

On peut continuer à se poser la même question pour toute sorte de surfaces. Par exemple, on appelle « surface compacte orientable de genre 2 » la surface d’une « bouée à deux places, » comme sur le dessin qui suit. On appelle « surface compacte orientable de genre 3 » celle d’une « bouée à trois places », etc.

Pour la surface de genre deux, il faut et il suffit de disposer de huit couleurs pour colorier n’importe quelle carte. Pour celle de genre trois, il faut et il suffit d’utiliser neuf couleurs.

J’ai trouvé cette information ... sur wikipedia [2] : remplacez le genre g par 2, puis par 3, dans la deuxième formule du paragraphe Généralisations du théorème des quatre couleurs. Le crochet ouvert en haut qui entoure l’expression signifie « partie entière » : on oublie ce qui est après la virgule.

Combien de couleurs pour des bouées à beaucoup de places (surfaces de grand genre) ? Cliquer pour déplier.

J’ai représenté ci-dessous la fonction trouvée sur wikipedia : le nombre de couleurs nécessaires pour être sûr de pouvoir colorier n’importe quelle carte, en fonction de la surface considérée. Plus exactement, les abscisses indiquent le genre de la surface (compacte, orientable), c’est-à-dire le nombre de places dans la bouée, dans le vocabulaire introduit précédemment.

Vous retrouvez les premières valeurs : la bouée à zéro place est la sphère. Le point se situe à la hauteur 4 : c’est le théorème des quatre couleurs, pour la sphère. Une bouée à une place est un tore. Le point est à la hauteur 7. Pour la surface de genre deux, autrement dit bouée à deux places, on retrouve la valeur 8, etc. Vous voyez le nombre de couleurs nécessaires augmenter avec le genre de la surface, mais de moins en moins vite. Pour le genre 10000 par exemple, on trouve 349 couleurs.

Enfin, Jérôme Germoni me signale une version polyédrale du coloriage du tore présenté dans cette article, sur l’excellent site mathcurve. Ce « polyèdre de Szillassi », du nom du mathématicien hongrois qui l’a conçu, est en forme de tore, et il comporte sept faces qui se touchent toutes mutuellement.

Les coulisses de la conception de ce tore

Pour ceux qui veulent aller un peu plus loin, voici comment j’ai partagé le tore en sept zones. Je n’ai pas procédé au hasard. Essayez donc de trouver cinq zones toutes mutuellement voisines, puis six, à tâtons : ce n’est pas facile. Cette construction est l’occasion de découvrir, en images, la manière classique pour les mathématiciens de concevoir le tore, surface extrêmement usuelle et riche de propriétés particulières.

Trois idées se cachent derrière l’établissement de la carte :

  1. un tore, c’est une Pac planète,
  2. chaque carte est codée par un ensemble de points reliés par des traits (on dit un graphe),
  3. on peut obtenir un dessin (un graphe) bien régulier en utilisant des « droites » du tore, vu comme au point 1.

1. Un tore, c’est la planète de Pac Man, ou « Pac planète ».

Difficile de faire de la géométrie sur un tore vous ne trouvez pas ? Un tore est rond et tordu, il a toujours une face cachée quel que soit le point de vue ... Dans cette partie, on va le déplier, comme on étalerait le patron d’un vêtement. On y verra alors plus clair pour la suite.

J’emprunte l’expression de Pac planète à Matthieu Gendulphe, qui l’utilisait pour de la vulgarisation lors de sa thèse à Bordeaux [3]

Les lecteurs de plus de trente ans se souviennent du célèbre Pac Man, ancêtre des jeux vidéo. Ce personnage habite un labyrinthe carré. S’il sort par la sortie du côté droit, il réapparaît instantanément dans l’entrée côté gauche, et vice-versa. Ici, on
imaginera aussi que Pac Man peut sortir par le haut, ce qui n’était pas prévu dans le jeu, en réapparaissant alors instantanément en bas et vice-versa.

Bref, Pac Man habite un tore. En effet, un tore est un carré dont les côtés gauche et droit, d’une part, et haut et bas, d’autre part, sont identifiés l’un à l’autre, ou collés l’un à l’autre si vous préférez. Je vais trop vite ? Reprenons cette affirmation image par image.

Voici comment transformer un tore en un carré. Découpez un tore le long d’un petit cercle comme sur le dessin de gauche. Vous obtenez un cylindre. Le cercle de découpe, marqué d’un chevron « > », se dédouble et apparaît à chaque extrémité du cylindre. Découpez alors ce cylindre le long d’un segment reliant ses extrémités. Vous obtenez alors un carré, où la deuxième ligne de découpe, dédoublée également, constitue les côtés haut et bas, marqués d’un double chevron « >> ». La première ligne de découpe, dédoublée, devient les côtés droit et gauche du carré.

En parcourant les étapes ci-dessus de droite à gauche, on reconstitue, par collage, un tore à partir d’un carré. Recollez les côtés haut et bas, voici un cylindre. Recollez alors les extrémités droite et gauche du cylindre, vous retrouvez un tore. Autrement dit, par ces deux collages, ou coutures, successives, vous avez habillé un tore à partir d’un patron carré.
Or, les côtés droit et gauche d’une part, et haut et bas d’autre part, du carré de Pac Man communiquent magiquement. Cette magie s’explique sans difficulté si on imagine que ce carré habille en fait un tore, selon la manipulation ci-dessus. Les côtés droit et gauche du Pac-carré sont en fait deux images d’un même cercle du tore sur lequel vit Pac Man. Idem pour les côtés haut et bas.

Pour concevoir ma carte, il me suffit donc de la tracer sur un carré, de sorte que ses côtés droit et gauche, d’une part, et haut et bas, d’autre part, se recollent de manière cohérente. C’est ce que j’ai fait :

Vérifiez que je ne mens pas ! Le collage haut-bas est cohérent : de gauche à droite apparaissent un peu d’orange, beaucoup de vert, puis de jaune, puis un peu de bleu. Je peux reconstituer un cylindre par collage, en recollant haut et bas. Chaque couleur sera recollée contre sa semblable. De même, on peut recoller droite et gauche.

Une fois ce patron établi, je l’ai donc reporté à l’aide d’un rapporteur sur mon tore en bois. J’ai reporté les points importants, puis les ai reliés, obtenant des zones hexagonales. Les côtés verticaux du patron correspondent à un petit cercle dessiné sur le tore en bois, comme sur la figure précédente. J’ai enfin peint les zones. Observez le patron : quels sont les voisines de la zone violette ? Celles de la zone orange ?

Voisines de la zone orange : réponse, cliquer pour déplier.

Suivons le bord de la zone orange. Partons par exemple du point de rencontre des zones blanche, violette et orange, à peu près à mi hauteur, vers la gauche. Tournons dans le sens des aiguilles d’une montre. On longe la zone violette, première voisine. Verticalement, on longe ensuite la zone rouge, deuxième voisine, puis toujours en descendant, la zone verte, troisième voisine. On se heurte au côté du bas du patron, mais sur le tore, ce n’est pas un obstacle. C’est une simple ligne de couture du patron, nous amenant en haut du patron, en face. Le côtoiement de la zone verte s’y poursuit. On tourne alors, remontant et longeant la zone bleue, quatrième voisine. On croise alors un angle du carré, c’est-à-dire, sur le tore, l’endroit où les deux coutures du patron se croisent. Comme on est en train de monter vers la gauche, on se retrouve ... à l’angle en bas à droite du patron (imaginez comment les quatre coins du carré sont cousus ensemble). On y longe toujours la zone bleue. On rencontre un nouvel angle et on longe la frontière, verticale, avec la zone jaune, cinquième voisine. Un dernier angle nous amène à longer la zone blanche, sixième voisine. Ce parcours nous refait traverser une couture du patron : son côté droit. On se retrouve à gauche, continuant de monter vers la droite pour retourver le point de départ.

La zone orange a six voisines, c’est-à-dire voisine toutes les autres zones.

Nous voici familiers avec la version « carrée » du tore. Il me reste à expliquer comment je suis parvenu au coloriage ci-dessus de cette version carrée du tore. C’est l’objet des deux parties suivantes.

2. Chaque carte est codée par un graphe.

Encore une fois, on va simplifier le problème : la forme des régions n’est pas si importante, ce qui compte, c’est le contact entre elles. Nous allons modéliser ce contact le plus simplement possible.

Cette partie se comprend encore essentiellement par des dessins. Si vous dessinez une carte partageant une surface en différentes zones, vous pouvez alors tracer sur la surface le graphe dual de cette carte. Attention, le mot graphe a (au moins) deux sens en mathématiques. Il signifie ici « ensemble de points dont certains sont reliés entre eux par des traits », et pas « représentation graphique d’une fonction ».

Vous symbolisez chaque zone par un point (un « sommet » du graphe) que vous placez dans la zone. Ensuite, vous reliez deux points s’ils sont situés dans des zones ayant une frontière commune. Il suffit pour cela de tracer une route du premier point au deuxième (une « arête » du graphe), traversant la frontière commune. Une moitié de la route est intégralement située dans la première zone, l’autre, dans la deuxième. De la sorte, on peut s’arranger pour qu’aucune des routes tracées, les arêtes, n’en rencontre une autre, excepté aux sommets. Voici, par exemple, une carte partageant la sphère en quatre zones « triangulaires ». On remarque d’ailleurs que ces zones ont une frontière commune avec chacune des trois autres.

Voici alors, tracé en trait fin sur la sphère, le graphe dual de cette carte. Ici, chaque sommet est relié à tous les autres car chaque région touche toutes les autres. J’ai en outre représenté, à côté, ce graphe dual de façon abstraite. Ce sont quatre « sommets », tous reliés entre eux par des « arêtes »

Pour le plaisir de la géographie, et pour être sûr d’être totalement clair, je présente un autre exemple. Voici la carte des 27 Etats membres de l’Union Européenne en 2009, sans leurs îles et sans Gibraltar, pour simplifier.

Construisons son « graphe dual ». On symbolise chaque Etat par un point — un « sommet » du graphe, placé n’importe où sur son territoire. Ensuite, on relie deux sommets par un trait — une « arête » du graphe — si les deux Etats symbolisés ont une frontière terrestre commune. On peut le faire de sorte qu’aucune arête n’en croise une autre, excepté aux sommets du graphe.

Voici enfin le graphe seul. On a oublié la carte. La seule information conservée est donc : qui a une frontière avec qui (pour bien faire, il aurait certes fallu étiqueter les sommets). On voit ainsi que l’Allemagne est l’Etat de l’Union ayant le plus d’Etats membres voisins : huit. Ensuite vient l’Autriche avec six. Malte et Chypre, elles, n’en ont pas.

Cette construction peut s’effectuer dans l’autre sens. A partir d’un graphe tracé sur une surface, sans croisement d’arêtes, construisons une carte dont ce graphe est le graphe dual. Voici deux exemples de graphes, tracés sur le plan.

Le premier graphe est autorisé, mais pas le deuxième : en bas, deux arêtes se croisent en un point qui n’est pas un sommet. Oublions ce dernier.

On peut alors noyer chaque sommet du premier graphe dans une zone de couleur, englobant toutes les demi-arêtes qui partent de lui. Ces zones ont alors une frontière commune exactement quand les sommets correspondants sont reliés par des arêtes.

Petite devinette ayant un air de famille avec ce qui va suivre. Quelle carte bien connue a-t-elle pour graphe dual le graphe suivant, qu’on imagine se poursuivant indéfiniment ?

Réponse, cliquer pour déplier.

Le graphe indique que chaque zone a six voisines. Une carte qui convient aura donc des zones hexagonales, chacune voisinant six congénères. Une solution est par exemple la carte du pavage hexagonal, en nid d’abeille, bien connu :

J’ai colorié ce pavage avec quatre couleurs, comme c’est toujours possible dans le plan.

Vous voici familiers des graphes duaux des cartes. Revenons à notre mouton. Le problème « trouver une carte partageant le tore en sept régions se touchant toutes mutuellement » revient au même que « dessiner sur le tore un graphe à sept sommets, chacun relié à tous les autres, sans que les arêtes se croisent ». Cette nouvelle formulation oublie la forme des zones pour ne retenir que l’unique donnée qui nous intéresse : qui touche qui. C’est une étape très courante d’un raisonnement mathématique : distinguer ce qui est important de ce qui ne l’est pas, pour résoudre une question, et coder ce qui est important de la manière la plus simple possible.

Voici donc le graphe que j’ai tracé sur un tore. Bien sûr, j’ai considéré que le tore est un carré dont les côtés opposés sont identifiés.

Les sommets sont les points gris. Un des sommets, situé aux angles du carré, est visible sous forme de quatre quartiers, qui se recollent en un point entier lorsqu’on reconstitue le tore. Vous voyez donc sept sommets, chacun relié à tous les autres par des arêtes qui ne se croisent pas. Il me restait à noyer chaque sommet dans une zone de couleur, hexagonale, pour obtenir la carte recherchée. Sur la photo ci-dessous, les sommets sont simplement les croisements d’arêtes. Le carré symbolisant le tore est légèrement décalé par rapport à la figure ci-dessus : le sommet précédemment placé dans les angles du carré est cette fois situé au milieu des côtés gauche et droit.

Vous savez à présent comment j’ai peint le tore. Mais sur le fond, il reste une question : la partie qui précède nous a ramené au problème « dessiner sur le tore un graphe à sept sommets, chacun relié à tous les autres, sans que les arêtes se croisent ». Comment faire ? En tâtonnant, ce n’est pas si facile.

En fait, j’avais déjà rencontré un coloriage du tore à 7 zones toutes mutuellement voisines et me souvenais du principe. Cependant, ce dessin était irrégulier, et je voulais peindre une version bien régulière :

  • avec des hexagones, car chaque zone a six voisines,
  • avec des hexagones tous semblables, comme dans le nid d’abeille plus haut.

Pour cela, il me fallait construire une version bien régulière du graphe. Seule cette version me ferait mieux comprendre comment il « fonctionne ». Je l’ai fabriqué à partir de lacets « rectilignes ».

3. On peut obtenir un graphe bien régulier en utilisant des « droites » du tore

Souvenez-vous du graphe du plan à maille triangulaire un peu plus haut, celui qui est dual du nid d’abeilles (imaginez le graphe continuant indéfiniment) :

Chaque sommet a six voisins : six arêtes partent de chaque sommet. Par ailleurs il est bien régulier en ce sens que les arêtes successives s’enchaînent, pour former des droites, selon trois directions : des droites horizontales, des droites inclinées « montantes » et des droites inclinées « descendantes ».

J’aimerais dessiner quelque chose de semblable sur le tore, avec cette fois exactement sept sommets (il n’est pas dit a priori que ce soit possible). Autrement dit, j’aimerais trouver trois droites sur le tore, qui se croisent les trois ensemble à chaque carrefour. Si un carrefour voit passer trois droites, c’est donc que six arêtes en partent : on peut en effet emprunter chaque droite dans deux sens, en partant du carrefour. Chaque carrefour aurait donc six voisins. Si j’y arrive, et que je forme sept carrefours, j’aurai donc gagné. Ah, un détail : qu’est-ce qu’une « droite » sur le tore ? C’est simplement un trait rectiligne ... quand on le voit sur le carré représentant le tore.

Utilisant mes souvenirs, j’ai alors considéré les trois « droites » A, B et C suivantes :

Notez comme d’habitude que ces droites sont cohérentes avec les recollements haut-bas et droite-gauche du carré. Suivez le trajet de chacune ... vous allez toujours tout droit et finissez par revenir au point de départ. On remarque alors que les droites A et B se croisent exactement 7 fois, et que la droite C coupe elle-même A et B exactement en ces sept points. On a gagné : en décrétant que ces points d’intersection sont les sommets d’un graphe, et que les portions de droites entre les sommets sont les arêtes du graphe, on obtient, comme voulu, un graphe à sept sommets, six arêtes s’échappant de chaque sommet pour le joindre aux six autres.

Le voyage est terminé, vous connaissez les coulisses de la conception du tore.

J’ajoute une petite excursion pour ceux qui ont encore du courage et de la curiosité. En effet, parler de « patron carré » et de « droites » du tore nous fait passer tout près du monde des lacets du tore : vous avez les outils pour les comprendre, et ils sont des objets massivement utilisés par les mathématiques d’aujourdhui, depuis H. Poincaré à la fin du 19ème siècle plus précisément.
Cette excursion vous permettra en outre de voir les zones colorées du tore comme trois colliers de perles, enroulés de trois manières différentes autour du tore.

Excursions gratuite et sans obligation dans le monde des lacets du tore. Cliquer pour déplier.

Les lacets d’un tore sont les courbes fermées sur elles-mêmes tracées sur le tore. Les « droites » A, B et C introduites plus haut sont trois exemples de tels lacets.

Quitte à déformer un lacet du tore, on se rend compte qu’il revient toujours à faire le tour du tore, « un certain nombre de fois dans un sens », par exemple celui du « cercle à double chevron » du tore, et « un certain nombre de fois dans l’autre » celui du « cercle à simple chevron » du tore. Numérotons-les arbitrairement « premier » et « deuxième » sens.

Voici un lacet tournant autour du tore une fois dans le premier sens et zéro fois dans le deuxième.

Voici un lacet tournant autour du tore zéro fois dans le premier sens, et une fois dans le deuxième.

Voici un lacet tournant autour du tore une fois dans chaque sens. Son image sur le tore-bouée est un peu déformée, mais on ne prête pas ici attention à ces déformation de lacets. Ces derniers glissent à volonté sur le tore comme des lassos.

Voici enfin un lacet tournant autour du tore une fois dans le premier sens et deux fois dans le deuxième.

On s’aperçoit donc que tout lacet sur le tore est codé par deux nombres : son nombre de « tours dans un sens » et son nombre de « tours dans l’autre ».

Les lacets A, B et C que j’ai utilisés sont les suivants :

  • le lacet A est celui qui fait 1 fois le tour du tore dans le premier sens et -2 fois dans le deuxième (c’est à dire deux fois, mais dans le sens rétrograde par rapport aux flèches indiquées sur le coté du carré),
  • le lacet B est celui qui fait 3 fois le tour du tore dans le premier sens et 1 fois dans le deuxième,
  • et le lacet C est celui qui fait 2 fois le tour du tore dans le premier sens et 3 fois dans le deuxième.

Si vous revenez au tore en bois ou éventuellement au carré peint, vous pouvez donc suivre les zones de couleur, comme des perles sur un collier, le long du lacet A. Les zones violette, rouge, jaune, bleue, blanche, orange et verte forment un collier s’enroulant sur le tore, une fois dans un sens et deux fois dans l’autre. Le long du lacet B, les zones violette, bleue, verte, jaune, orange, rouge et blanche forment un collier s’enroulant sur le tore, trois fois dans un sens et une fois dans l’autre. Le long du lacet C, les zones violette, jaune, blanche, verte, rouge, bleue, et orange forment un collier s’enroulant sur le tore, deux fois dans un sens et trois fois dans l’autre. On pourrait s’amuser à comprendre ces permutations des places des couleurs le long de chaque collier, mais j’ai la flemme.

Je resterai ici un peu mystérieux, en rappelant seulement que ces histoires de lacets ne sont pas une curiosité ou une anecdote, mais un outil fondamental pour comprendre les surfaces, le tore ou d’autres. Ce billet était juste l’occasion d’un aperçu à leur propos.

Un exercice montrant « pourquoi », les lacets A, B et C fonctionnent pour construire le graphe, et comment construire d’autres graphes semblables, pour les lecteurs connaissant un peu de maths de première année du supérieur.

On résume la définition de A, B et C par : $A=\left(\begin{array}{c} 1\\-2\end{array}\right)$, $B=\left(\begin{array}{c} 3\\1\end{array}\right)$ et $C=\left(\begin{array}{c} 2\\3\end{array}\right)$. Les nombres qui apparaissent, superposés, sont les nombres de tours de A, B et C dans chaque sens. On remarque alors que le déterminant de la matrice :
\[(A,B)=\left(\begin{array}{cc} 1&3\\-2&1\end{array}\right)\]
vaut sept. C’est ce qui explique que A et B se croisent sept fois. Pourquoi ? Par ailleurs, en additionnant terme à terme, on constate que $C=B-A$, c’est-à-dire que :
\[C=\left(\begin{array}{cc}{-1}&0\\0&1\end{array}\right)\cdot(A,B)=M.(A,B)\]
avec cette fois $M$ une matrice à coefficients entiers, de déterminant l’entier inversible -1. C’est ce qui explique que $C\cap A=C\cap B=A\cap B$. Pourquoi ?

Cet exercice permet de construire une infinité d’autres graphes sur le tore, à sept sommets, tous reliés, sans croisement d’arêtes. Il suffit de trouver des matrices à coefficients entiers et de déterminant 7 : elles fournissent les lacets A et B adéquats. On construit alors C de la même façon, à partir des A et B choisis.

Pour ma part, j’ai choisi A et B tels que les lacets A,B et C obtenus s’enroulent le moins de fois possible autour du tore. Cela évite d’obtenir une carte illisible, avec des hexagones très fins et très enroulés.

Remerciements. Je remercie J. Germoni, S. Cantat et X. Caruso pour leur relecture attentive et leurs suggestions nombreuses et utiles.

Article édité par Serge Cantat

Notes

[1Plus exactement, j’ai conçu et peint l’anneau. Mais je l’ai fait tailler, en bois d’aulne et sur mesure, par un tourneur sur bois, métier que j’ai découvert à cette occasion.

[2Il est frappant que ces théorèmes des 7, 8, 9 couleurs, etc, sur des surfaces apparemment compliquées, ont été prouvés en 1968, donc bien avant le théorème des quatre couleurs pour le plan. Ce devait être plus facile ; j’ignore pourquoi.

[3Si cette excursion dans le monde des Pac planètes, les tores, vous plaît, je vous conseille la lecture de ce travail
de lycéens de Talence dans le cadre de l’association Maths en jeans. Il a été encadré par mon collègue Pierre Mounoud et fait toucher des maths profondes et tout à fait contemporaines, sous une formulation simple.

Partager cet article

Pour citer cet article :

Charles Boubel — «Devinette multicolore» — Images des Mathématiques, CNRS, 2010

Commentaire sur l'article

  • Théorèmes des n couleurs

    le 10 février 2010 à 10:28, par Benoît Kloeckner

    Il est effectivement vrai que le théorème des quatre couleurs dans le plan est beaucoup plus difficile que, par exemple, le théorème des 7 couleurs dans le tore. En fait la méthode utilisée pour le tore et les surfaces « de genre supérieur » [1] ne donne qu’un théorème des 6 couleurs appliquée au plan. Il n’est pas extrêmement difficile d’améliorer ce résultat en un théorème des cinq couleurs (voir par exemple le livre « raisonnements divins » de Aigner et Ziegler), mais le passage aux quatres couleurs, lui, n’a été obtenu qu’à l’aide d’ordinateurs.

    [1En gros, utiliser la caractéristique d’Euler et un peu de dénombrement pour prouver que le graphe à colorier possède au moins un sommet ayant peu de voisins, ce qui permet la construction d’un coloriage de façon récursive.

    Répondre à ce message

Laisser un commentaire

Forum sur abonnement

Pour participer à ce forum, vous devez vous enregistrer au préalable. Merci d’indiquer ci-dessous l’identifiant personnel qui vous a été fourni. Si vous n’êtes pas enregistré, vous devez vous inscrire.

Connexionmot de t pr  carte. ?ollez >

lass="inield
dulaires nombreuse

s nombreuse dité pons nots imageits images

Si vaiv>

  • lass

    Si vaiv>

  • lass

    Si vaiv>

  • lass
  • "block-comment" il alt ent" irandom
    <

    Si vaiv>

    <

    Si vaiv> an.php?p+Fginez-ou-fpliqs-s.fre http://-et-n conservlac-29-30-9-et-16-10+ge Can

    "block-comm3>
    laticon-rss">
    "block-comm;: ume
    "block-commda 23dts, sins&0:287
    "block-commes 2-"jFginez7;aufpliqs,iques : http://ifacn conservlace(29-30/9 dans6/10)
    vaiv> v> an.php?p+Siersffi-e. Sur le-et- "block-comm3>
    laticon-rss">
    "block-comm;: ume
    "block-commda 23dts, sins&0:287
    ssi> "block-commes 2-"jSiersffi,e. Sur lesure,i>
    vaiv> v> an.php?p+M.fre http://- uxjtoure//-du-ré&iommee-16-17-9+ge Can
    "block-comm3>
    laticon-rss">
    "block-comm;: ume
    "block-commda 15dts, sins&0:287
    ssi> "block-commes 2-"jques, CNRS, 20Il x jtourre commeré&iommee (16-17/9)
    vaiv> v> an.php?p+Stephaee-Mstruqulomme-au-Chautge’-France+ge Can
    "block-comm3>
    laticon-rss">
    "block-comm;: ume
    "block-commda 11dts, sins&0:287
    ssi> "block-commes 2-"jS. Sphaee Mstruqtsommet boCierre hrefFrance
    vaiv> v> an.php?p+La-fit’-la- somm’i-c quati-c ur oux+ge Can
    "block-comm3>
    laticon-rss">
    "block-comm;: ume
    "block-commda 8dts, sins&0:287
    ssi> "block-commes 2-"jL9ème srougequci at des quati c ur oux>

    Cet

    vaiv> v> an.php?p+O.

    -e vorvlac-e ther'>-e vorvlac-et is-14-9+ge Can
    "block-comm3>
    laticon-rss">
    "block-comm;: ume
    "block-commda 8dts, sins&0:287
    ssi> "block-commes 2-"jO.

    e vorvlac – e ther'>, e vorvlacr ailleu(et is, 14/9)
    vaiv> v> li> bnt" il alt ent" i zones

    Cr&eacut2>Szones IDM

    Cr&eacu"credits"> bnt" inewsne, b

    Laisse3>Cr&eacu"credits"> 3>
    laticon-rss"><Re
    conslaire vous er_newsne, b meiséi clst
    labetal r="newsne, b _ebjec">Newsne, b IDM labet
    lnput typemmeext" vame="newsne, b _ebjec"">1 buttir
    cons
    v
    forum"> ent" i i>
  • lass ilto:?subject=D#EMAIL_WEBMASTERink-contact" title="Envoyer ceCi> laticon-contact">
  • i> v i> v i> v i> v

    i> v --n
    bnt" in{ar ent" inavns le m

    Cr&eacu
    lass h3utilt nd> <

    lass lass&eacu ilto:?su-La-&ibet -dqs-s.fre httierss- s="li>Te bet
  • lass lass&eacu ilto:?suage=identifian clasa Aclasa
  • lass lass&eacu ilto:?su-Defi/-du-Ccinsdà 1-s.fre http:/- s="li>Dts imagefis profondes
  • lass lass&eacu ilto:?su-L -dqbuqudu-18- s="li>Dts imageba: lass lass&eacu ilto:?su-Revue’-p;: lass lass
    ques, CNRS, 2010lèc17;as
  • lass lass&eac
  • lass lass&eacu ilto:?su-Eni iarref’-l-s hai- s="li>Eyanta manièrehappant deoli
  • lass lass&eac
  • lass lass&eacu ilto:?su-M.fre http://-en addit-46- s="li>ques, CNRS, 20 en addit
  • lass lass&eac
  • lass lass&eacu ilto:?su-L-IHP-s.isi>LhappantIHPpae à cag;un e siersfflier. lass lass&eac
  • lass lass&eacu ilto:?su-Te meréas-IHP- s="li>Te meréas IHP
  • lass lass&eac
  • lass lass&eacu ilto:?su-Mout ’-la-e. Sur le- s="li>qac planougee. Sur le
  • lass lass&eac
  • lass lass&eacu ilto:?su-dité po-s.fre http://-ge CanÉembllanougee. Sur le
  • lass lass&eac
  • lass lass&eacu ilto:?su-Oivemudu-m qu-ge CanOivemdes lass lass&eac
  • lass lass&eacu ilto:?su-Caf -dqs-s.fru-ge CanCafoute ofondes
  • lass lass&eac
  • lass lass&eacu ilto:?su-L sjce ques, CNRS, 20 anouge les toreTud et
  • lass lass&eac
  • lass lass&eacu ilto:?su-L -iedcast-Henri-à la fa- s="li>Lo iedcast Henri à la fin
  • lass lass&eac
  • lass lass&eacu ilto:?su-aths+--dqs-s.fru-2004-ge Can Mathéprofondes 2004
  • lass lass&eac
  • lass lass&eacu ilto:?su-aths+--dqs-s.fru-2006-ge Can Mathéprofondes 2006 lass lass&eac
  • lass lass&eacu ilto:?su-Courà 1-dqs-onnaissa-ge CanCourà 1s.

    nnaissa lass lass&eac
  • lass lass
  • lass lass&eacu ilto:?suFt pour coer'>-du-sitn s="li>Ft pour coer'>ieur.itn
  • lass lass&eacu ilto:?suage=identifian clasa Nota actualitts image
  • lass lass&eacu ilto:?suShaut-Pelte widts-sitns-amisge CanPelte widts
  • lass lass&eacu ilto:?subject=D/i>@h.cnrs.fr%2FDevinetanCon
  • lass lass
    pri
    /i>Laisser"head"> /ilin{ar

    Cr&eacunav rol/divavns le m

    Cr&eac&eacu
    lass ilto:?suMces ds-ongal//ge Candits imag : lass ilto:?suShaut-Pelte widts-sitns-amisge CanShaut webp>
    lass ilto:?subject=D/i>@h.cnrs.fr%2FDevinetanmenu con
  • lass
    ilil alt
    rel= > typemmeext/:;"> >
  • typemmeext/:;"> > typemmeext/:;"> > typemmeext/:;"> >
    var _paq = _paq || [];
    _paq.push(['trackPcnrView']);
    _paq.push(['e wbleLinkTracking']);
  • _paq.push(['setTrackerUrl', '/piwik/piwikiden']);
    _paq.push(['setShauId', 1]); (fu pour () { var d=center'>, =d.createE ces h(' '), s=d.getE ces hsByTagName(' ')[0];
    g.typem'eext/:;"> '; g.defer=true; g.async=true; g.if/ch/piwik/piwikijs';
    s.compntNode.insertBefore(g,s);
    })();
    h2 >