De l'Halloween et de mathématiques

L’Halloween approche à grands pas et cette année, encore, en plus de déguster des friandises, nous verrons sortir les sorcières, les squelettes, sans oublier les araignées. Ces dernières pourront alors plus librement tisser leurs toiles dans nos villes. Ces toiles peuvent rappeler des objets mathématiques appelés : graphe. Ceux-ci sont intéressants, car on peut trouver beaucoup de théorèmes très simples à comprendre les concernant.

Les graphes sont simplement des ensembles de points, appelés sommets, reliés ensemble par des lignes, appelées arêtes. La position des points est sans importance : ce qui importe, c’est comment les points sont reliés entre eux. Certains graphes, comme ceux représentant une toile d’araignée, ont une certaine particularité de pouvoir être dessinés sans qu’aucune arête ne se croise, de tels graphes sont dits planaires. 

Un premier problème lié aux graphes est l’énigme des trois maisons. L’énigme s’énonce comme suit : nous avons trois maisons (hantées) qui doivent être alimentées en eau, en électricité et en gaz par des canalisations allant à trois sources distinctes. S’il est impossible, pour des raisons de sécurité, de croiser les canalisations, est-il possible d’alimenter les trois maisons? Cette situation peut être représentée par un graphe avec comme sommets les trois maisons et les trois sources, et comme arêtes, trois triplets partant de chaque maison et allant à chaque source. La question est de savoir si ce graphe est planaire. Vous pouvez essayer aussi longtemps que vous voulez, il est impossible d’alimenter les trois maisons sans croisement. Il est possible de démontrer ceci avec des propriétés assez complexes des graphes planaires.

Un autre problème lié aux graphes planaires est le théorème des quatre couleurs. L’énoncé est très simple et rappelle certains types de dessins que les enfants font. Ce théorème nous dit qu’il est toujours possible de colorier une carte, ou un coloriage, avec seulement quatre couleurs de telle façon que deux régions qui se touchent sur une frontière (pas seulement sur un coin) ont deux couleurs distinctes. Une autre façon de voir le théorème est qu’étant donné un graphe planaire, il est possible d’attribuer une couleur à chaque sommet de sorte que deux sommets reliés par une arête sont de couleurs distinctes.

Ce théorème, qui peut sembler contre-intuitif, est, malgré son aspect enfantin, vraiment très difficile à démontrer. Ce théorème est resté une conjecture pendant longtemps avant de pouvoir être démontré en 1976 par Kenneth Appel et Wolfgang Haken. Il fut le premier théorème majeur à être démontré sur un ordinateur. Ils ont réussi à réduire le problème à plus d’un millier de cas à être traité informatiquement. Pour que ce théorème soit valide, il faut par contre que les régions soient connexes, c’est-à-dire en un morceau. Un exemple de région non connexe sur la Terre est l’Alaska, qui fait partie des États-Unis, mais qui est totalement isolé des autres états. On pourrait aussi donner en exemple le Groenland (Danemark) ou encore la Tasmanie (Australie).