Département de mathématiques de l'Université de La Rochelle

 

THEORIE DES GRAPHES - Découvrir le site

 

L'objectif de cette formation de théorie des graphes est double : d'une part, apporter aux enseignants de lycée une familiarité avec un domaine qu'ils n'ont probablement jamais rencontré au cours de leurs études, d'autres part de proposer quelques exemples d'activités utilisables dans les classes. Les concepts présentés ont fait l'objet d'un enseignement optionnel de première année de deug.

La suite de cette page contient une description des divers chapitres de cette formation, ainsi que des liens permettant d'accéder à ces chapitres.

Les deux premiers chapitres du site concernent les questions liés aux parcours sur un graphe. Les graphes eulériens sont ceux pour lesquels existe un chemin parcourant toutes les arêtes une fois et une seule sans "lever le crayon". Les graphes hamiltoniens sont ceux pour lesquels existe un chemin passant par tous les sommets, là encore sans lever le crayon. Malgré l'apparente similitude des concepts, la connaissance que nous avons de chaque type de graphe est très différente : alors qu'il est possible de caractériser complètement et simplement la première catégorie, on ne dispose pour le seconde que de résultats très partiels.

Parmi les graphes qu'on utilise beaucoup dans les applications, et notamment en informatique, figurent les arbres. Ce sont les graphes pour lesquels il existe un unique chemin d'un sommet à un autre. Nous donnons ici quelques propriétés et caractérisations de ces graphes, et prouvons un théorème d'énumération appelé théorème de Cayley.

Les deux derniers chapitres portent sur la question des graphes planaires. Le contenu du chapitre 4, traité in extenso, justifierait un cours entier à lui seul. Il s'agit de comprendre les méthodes employées par les mathématiciens pour démontrer le théorème des quatre couleurs, résultat selon lequel il est possible de colorier toute carte de géographie imaginable avec seulement quatre couleurs, de sorte que deux régions partageant une frontière non réduite à un point ne soient jamais de la même couleur. Un fait intéressant concernant ce théorème est qu'il s'agit d'un des rares résultats de la recherche récente (la première démonstration date du début des années 1970, elle a été depuis simplifiée plusieurs fois et présente aujourd'hui un caractère "humain" qu'elle n'avait pas initialement car elle nécessitait alors de considérables calculs informatiques) dont non seulement l'énoncé mais également les grandes étapes de la preuve sont accessibles à des personnes qui ne sont pas des chercheurs professionnels. Après ce grand théorème, nous examinons au chapitre 5 quelques propriétés générales des graphes planaires, c'est-à-dire dessinables sur un plan sans que deux arêtes ne se coupent (à part éventuellement en une extrémité commune), et énonçons en particulier le théorème de Kuratowski, selon lequel il n'existe "essentiellement" que deux graphes planaires dont sont dérivés tous les autres.