El' ements de Th' eorie des Graphes

INSTITUT NATIONAL POLYTECHNIQUE DE LORRAINE
Ecole Nationale Superieure d’Electricite et de Mecanique
Elements de Theorie des Graphes
Didier Maquin
Version provisoire du 3 mai 2003Table des matieres
Avant propos 4
1 Un bref historique de la theorie des graphes 4
2 Introduction 6
2.1 Qu’est-ce qu’un graphe? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.2 Graphes et applications multivoques . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.3 Principales de nitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
3 Modes de representation d’un graphe 9
3.1 Listes de succession . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
3.2 Matrice d’adjacence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
3.3 d’incidence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
4 Etude de la connexite 11
4.1 Cha^ nes et cycles, elementaires et simples . . . . . . . . . . . . . . . . . . . . . . 11
4.2 Chemins et circuits, elementaires et . . . . . . . . . . . . . . . . . . . . . 12
4.3 Graphes et sous-graphes connexes . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
4.4 et fortement connexes . . . . . . . . . . . . . . . . . . . . . 13
4.5 Cycles et nombre cyclomatique . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
5 Parcours euleriens et hamiltoniens 15
5.1 Cha^ nes et cycles euleriens . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
5.2 Cha^ ...