Article : Coloriage - Lycée Jean Puy (Roanne) Lycée Saint Paul (Roanne)

Article
Résumé de la production
Le problème de coloriage d'une carte géographique consiste à attribuer à chaque pays d'une carte une couleur de sorte que deux pays avec une frontière commune ne soient pas attribués la même couleur. On souhaite colorier une carte donnée avec un nombre minimum de couleurs. Combien en faut-il pour colorier toutes les cartes possibles ? On appelle ce nombre le le nombre chromatique ? Cette question, difficile, est abordé, d'abord sous l'angle de la caractéstique d'Euler de la configuration des pays ; ce qui donne un invariant, très intéressant, mais qui n'apporte pas d'information directe sur le nombre chromatique même si ce dernier, tout comme la caractéristique d'Euler, ne dépend que de la forme (topologie) du support sur lequel on dessine les cartes. En donnant un exemple explicite, les élèves montrent que 4 couleurs sont nécessaires pour colorier toutes les cartes (dans le plan). Une preuve du fait que 4 couleurs suffisent existe, mais elle utilise de façon importante des calculs faits sur ordinateur. Le cas de cartes sur un tore est aussi brièvement évoqué.
Mots clés
problème des 4 couleurs
nombre chromatique
caractéristique d'Euler