Théorème des 4 couleurs & Représentations par segments.

Un map monde en 4 couleurs.

Le Théorème des 4 couleurs affirme que toute carte peut être coloriée avec 4 couleurs, de façon à ce que des régions voisines aient des couleurs différentes. Il a fallu plus d'un siècle pour montrer ce résultat et les seuls preuves connues font appel à un programme de vérification. Dis autrement, aucun être humain n'a vérifié 'à la main' chaque étape de ces preuves.

Le but de ce stage est de trouver un contrexemple à la Conjecture de West (renforçant à la fois le Théorème des 4 couleurs et la Conjecture de Scheinerman). Cette conjecture dit que tout graphe planaire admet une représentation dans laquelle chaque sommet est représenté par un segment et où deux segments s'intersectent si et seulement si les sommets correspondants sont voisins. Il faut de plus que les segments soient de pente $0, \pi/4,\pi/2$ ou $3\pi/4$, et que les segments parallèles ne s'intersectent pas.

Un graphe planaire,

et sa représentation.

Le stage consistera à tester la conjecture sur de petits graphes planaires générés via plantri en programmant les 2 fonctions suivantes :

Une fonction qui étant donné un graphe planaire $G$, énumère toutes les assignations de pentes possibles (ceci est équivalent à énumérer les 4-colorations de $G$).

Une fonction qui étant donné un graphe planaire $G$ où chaque sommet s'est vu attribuer une pente, vérifie si il existe un système de segments respectant ces préconisations. Ceci consistera à traduire ce problème en un simple programme linéaire (notion introduite en HLIN 606).

Suivant l'avancée des travaux les stagiaires implémenteront des optimisations améliorant le temps d’exécution de ces tests.