Introduction à la théorie des graphes

Le but de ce fascicule est d'initier les lycéens à la théorie des graphes. Il n'a pas pour ambition de présenter une théorie complète, mais de montrer comment les graphes peuvent être une méthode de résolution de problèmes intéressante.

Ce cours se veut accessible aux élèves de lycée, car il ne demande pratiquement pas de connaissances préalables. Il est découpé en deux parties principales : les graphes non orientés et les graphes orientés.

Comme la théorie des graphes utilise un jargon bien particulier, le début du cours comporte beaucoup de définitions. Un index et un lexique en fin de fascicule aideront l'élève à assimiler ces termes.

Les 75 exercices sont essentiellement de deux types :

• Des exercices théoriques sur les graphes, qui sont souvent des démonstrations assez simples, généralement par induction, ou par l'absurde ; il y a aussi des exercices de réflexion qui permettent de se rendre compte si on a bien compris un concept ou non.

• Des exercices pratiques où il peut être avantageux d'utiliser des graphes pour modéliser et résoudre un problème.

Graphes non orientés

• Premières définitions

• Graphe partiel et sous-graphe

• Degrés

• Chaînes et cycles

• Graphes eulériens

• Graphes hamiltoniens

• Couplages

• Graphes planaires

• Représentations non graphiques d’un graphe

• Arbres

• Arbres couvrants

• Coloration

• Graphes triangulés

Graphes orientés

• Graphes orientés

• Degré d’un sommet d’un digraphe

• Chemins et circuits

• Représentations non graphiques des digraphes

• Digraphes sans circuit

• Graphes de comparabilité

• Algorithme de Dijkstra

• Réseau PERT