Haken Wolfgang

En 1976, à l’Université de l’Illinois, Wolfgang Haken et Kenneth Appel s’attaquent au coloriage des cartes planes finies formées de régions connexes. Leur résultat garantit que quatre couleurs au plus suffisent pour éviter que deux régions partageant une frontière commune de longueur non nulle portent la même couleur.

La nouveauté historique tient aussi à la preuve : un programme informatique y vérifie un très grand nombre de cas. Haken ne se résume pourtant pas à ce théorème. Ses travaux concernent également les variétés tridimensionnelles, les surfaces normales et la topologie algorithmique.

Wolfgang Haken, né à Berlin en 1928, est un mathématicien américain spécialisé en topologie. Il est principalement associé à la démonstration du théorème des quatre couleurs, obtenue en 1976 avec Kenneth Appel à l’Université de l’Illinois. Ce théorème porte sur toute carte plane finie formée de régions connexes : il existe un coloriage utilisant au plus quatre couleurs dans lequel deux régions distinctes partageant une frontière commune de longueur non nulle reçoivent toujours des couleurs différentes.

Cette démonstration occupe une place particulière dans l’histoire des mathématiques, car un programme informatique intervient de façon essentielle pour vérifier un nombre considérable de cas. L’ordinateur n’est donc pas un simple outil de dessin ou d’illustration : il participe à la vérification nécessaire à la preuve.

Les autres contributions citées de Haken appartiennent à la topologie. Les variétés de Haken forment une classe de variétés tridimensionnelles dotées de propriétés structurales particulières. Son nom est aussi attaché à la finitude de Kneser-Haken. Ses recherches ont enfin compté pour la topologie algorithmique et la théorie des surfaces normales.

Considérons une carte simplifiée de quatre régions, nommées A, B, C et D. Chaque région est adjacente aux trois autres. Pour suivre uniquement les voisinages, on représente chaque région par un sommet et chaque adjacence par un segment.

1. Les données sont quatre sommets et six adjacences : A–B, A–C, A–D, B–C, B–D et C–D.

2. Attribuons le rouge à A. Puisque B touche A, B reçoit le jaune.

3. La région C touche A et B : elle doit prendre une troisième couleur, ici le blanc. La région D touche A, B et C : elle prend une quatrième couleur, ici le noir.

4. Le contrôle consiste à parcourir les six segments : leurs deux extrémités ont toujours des couleurs différentes. Cet exemple exige quatre couleurs, tandis que le théorème affirme que quatre suffisent pour toute carte plane, même beaucoup plus complexe.

Pour lire une carte coloriée, on commence par relever les frontières communes entre régions. Le bon contrôle porte sur les régions adjacentes, et non sur la fréquence globale de chaque couleur.

Pour étudier le problème mathématiquement, on peut remplacer les régions par des sommets et leurs adjacences par des segments. Cette représentation met directement en évidence les couples qui doivent recevoir des couleurs différentes.

Pour situer Haken dans l’histoire des mathématiques, il faut retenir deux fils distincts : la preuve informatique du théorème des quatre couleurs et ses recherches topologiques sur les variétés tridimensionnelles et les surfaces normales.

Le théorème et sa démonstration. Le théorème énonce que quatre couleurs au plus suffisent pour toute carte plane. La démonstration de Haken et Appel est le raisonnement de 1976 qui établit cet énoncé en faisant intervenir un programme informatique.

Le théorème des quatre couleurs et les variétés de Haken. Le premier concerne le coloriage des cartes planes. Les secondes sont des variétés tridimensionnelles étudiées en topologie. Le nom de Haken relie ces sujets, mais ils ne désignent pas le même objet mathématique.

« Au plus quatre » ne signifie pas « exactement quatre ». Certaines cartes se colorient avec deux ou trois couleurs. Quatre est une garantie générale ; l’exemple de quatre régions toutes adjacentes montre un cas où quatre couleurs sont effectivement nécessaires.

Une couleur différente n’est exigée que pour deux régions adjacentes. Deux régions sans frontière commune peuvent recevoir la même couleur. Il faut donc examiner les voisinages avant de multiplier inutilement les couleurs.

Le recours à l’ordinateur ne remplace pas l’énoncé. Le programme intervient dans la vérification d’un très grand nombre de cas de la démonstration de 1976. Le résultat obtenu reste une affirmation portant sur toute carte plane finie dans le cadre standard du théorème.

Théorème des quatre couleurs — Approfondir l’énoncé mathématique auquel le nom de Wolfgang Haken reste principalement associé.

Colorier les pavés du plan — Prolonger la réflexion sur les contraintes de coloriage dans une autre organisation du plan.

Les travaux topologiques de Haken ouvrent aussi vers l’étude des variétés tridimensionnelles, des surfaces normales et des méthodes algorithmiques en topologie.