Les graphes et leurs applications

Couverture......Page 1
Page de titre......Page 2
Table des matières......Page 6
1.1 Championnat entre plusieurs équipes......Page 8
1.2 Graphes vides et graphes complets......Page 10
1.3 Graphes isomorphes......Page 12
1.4 Graphes planaires......Page 16
1.5 Problèmes planaires......Page 18
1.6 Nombre d'arêtes d'un graphe......Page 22
2.1 Les composantes......Page 26
2.2 Le problème des ponts de Königsberg......Page 28
2.3 Graphes eulériens......Page 30
2.4 Suivez les flèches !......Page 33
2.5 Cycles hamiltoniens......Page 35
2.6 Problèmes amusants et graphes......Page 37
3.1 Arbres et forêts......Page 41
3.2 Cycles et arbres......Page 43
3.3 Le problème du réseau......Page 45
3.4 Les rues et les places......Page 48
4.1 Affectation du personnel......Page 52
4.2 Autres formulations......Page 55
4.3 Tournois en plusieurs tours......Page 58
5.1 Retour sur les championnats entre plusieurs équipes......Page 63
5.2 Les problèmes de trafic à sens unique......Page 65
5.3 Demi-degrés d'un sommet......Page 70
5.4 Graphes généalogiques......Page 73
6.1 Casse-têtes et graphes orientés......Page 80
6.2 La théorie des jeux......Page 83
6.3 Le paradoxe du journaliste......Page 89
7.1 Relations et graphes......Page 94
7.2 Relations particulières......Page 97
7.3 Relations d'équivalence......Page 100
7.4 Relations d'ordre......Page 105
8.1 Conditions d'existence des graphes planaires......Page 109
8.2 La formule d'Euler......Page 113
8.3 Relations dans les graphes. Dual d'un graphe......Page 116
8.4 Les solides de Platon......Page 118
8.5 Les mosaïques......Page 122
9.1 Le problème des quatre couleurs......Page 126
9.2 Le théorème des cinq couleurs......Page 130
SOLUTIONS......Page 135
BIBLIOGRAPHIE......Page 146
LEXIQUE......Page 148