Nous attaquons des problèmes de théorie des graphes et combinatoire grâce à la puissance de calcul des ordinateurs couplée à des algorithmes astucieux.
Le théorème des 4 couleurs dit qu’avec 4 couleurs on peut colorier toute carte où les pays sont connexes tel que deux pays voisins aient différentes couleurs. C’est le premier résultat prouvé en utilisant l'ordinateur, en 1989. Nous expliquons la preuve et recréons un programme qui permet de l’établir, et peut être utilisé pour attaquer d’autres problèmes. Nous donnons une piste pour automatiser plus cette méthode.
La domination dans une grille consiste à mettre des pierres sur certaines cases tel que chaque case sans pierre a une voisine qui en contient une. Ce problème a été résolu en 2011 en utilisant l’ordinateur pour prouver une formule donnant le nombre minimum de pierres selon la taille de la grille. Nous adaptons cette méthode pour deux variantes de la domination et résolvons partiellement deux autres variantes.
Le problème de dénombrement associé demande combien il y a d’ensembles dominant une grille donnée. Nous étudions ce problème pour la domination et trois variantes. Nous prouvons l'existence de taux de croissance asymptotiques pour ces 4 problèmes, et encadrons ces taux.
Un polyomino est un ensemble de carrés connexe, comme les pièces de Tetris. En existe-t-il un d'ordre impair ? Il s'agit de trouver un polyomino qui pave un rectangle avec un nombre impair de copies, mais n’en pave pas de plus petit. Nous n'avons pas résolu ce problème de 1989, mais avons créé un programme qui énumère les polyominos et cherche leur ordre. Nous classifions, selon leur ordre, les polyominos de taille au plus 18.
Gratuit
Disciplines