1 Introduction et notions fondamentales ........................ 1
1.1 Quelques problèmes ...................................... 2
1.2 Nombres et ensembles .................................... 8
1.3 Récurrence mathématique et autres types de
démonstration .......................................... 18
1.4 Fonctions .............................................. 28
1.5 Relations .............................................. 35
1.6 Relations d'équivalence ................................ 40
1.7 Ensembles ordonnés ..................................... 44
2 Dénombrement combinatoire ................................... 52
2.1 Fonctions et sous-ensembles ............................ 52
2.2 Permutations et factorielles ........................... 58
2.3 Coefficients binomiaux ................................. 61
2.4 Estimations: une introduction .......................... 72
2.5 Estimations: la fonction factorielle ................... 80
2.6 Estimations: les coefficients binomiaux ................ 88
2.7 Le principe d'inclusion-exclusion ...................... 94
2.8 La responsable du vestiaire ........................... 100
3 Graphes: une introduction .................................. 106
3.1 Notion de graphe; isomorphisme ........................ 106
3.2 Sous-graphes, composantes et matrice d'adjacence ...... 115
3.3 Score d'un graphe ..................................... 123
3.4 Graphes eulériens ..................................... 129
3.5 Un algorithme qui permet de trouver un cycle
eulérien .............................................. 135
3.6 Graphes eulériens orientés ............................ 139
3.7 2-connexité ........................................... 144
4 Les arbres ................................................. 151
4.1 Définition et caractérisations des arbres ............. 151
4.2 Isomorphismes d'arbres ................................ 159
4.3 Arbres couvrants d'un graphe .......................... 165
4.4 Problème de l'arbre couvrant de poids minimal ......... 171
4.5 Algorithmes de Jarník et de Boruvka ................... 178
5 Dessiner des graphes dans le plan .......................... 183
5.1 Dessiner dans le plan et sur d'autres surfaces ........ 183
5.2 Cycles dans les graphes planaires ..................... 191
5.3 La formule d'Euler .................................... 198
5.4 Coloriages de cartes: le probleme des quatre
couleurs .............................................. 209
6 Double décompte ............................................ 221
6.1 Arguments de parité ................................... 221
6.2 Théorème de Sperner concernant les families
indépendantes ......................................... 231
6.3 Un résult at en théorie extrémale des graphes ......... 239
7 Le nombre d'arbres couvrants ............................... 244
7.1 Le résultat ........................................... 244
7.2 Une preuve via le score ............................... 246
7.3 Une preuve avec des vertébrés ......................... 248
7.4 Une preuve qui utilise le code de Prüfer .............. 250
7.5 Ce qui est peut-être la preuve la plus simple ......... 254
7.6 Une preuve qui utilise les déterminants ............... 257
8 Plans projectifs finis ..................................... 266
8.1 Définitions et propriétées fondamentales .............. 266
8.2 Existence de plans projectifs finis ................... 277
8.3 Carrés latins orthogonaux ............................. 282
8.4 Applications combinatoires ............................ 286
9 Probabilité et preuves probabilistes ....................... 290
9.1 Preuves par le dénombrement ........................... 290
9.2 Espaces probabilisés finis ............................ 298
9.3 Variables aléatoires et espérance ..................... 309
9.4 Quelques applications ................................. 315
10 Fonctions gènèratrices ..................................... 326
10.1 Applications combinatoires des polynômes .............. 326
10.2 Intervention des séries entières ...................... 330
10.3 Nombres de Fibonacci et nombre d'or ................... 342
10.4 Arbres binaires ....................................... 350
10.5 Sur le lancement de dés ............................... 355
10.6 Marche aléatoire ...................................... 356
10.7 Partitions d'entiers .................................. 360
11 Applications de l'algèbre linéaire ......................... 368
11.1 Blocs ................................................. 368
11.2 Inégalité de Fisher ................................... 374
11.3 Recouvrement par des graphes bipartis complets ........ 378
11.4 Espace cyclique d'un graphe ........................... 381
11.5 Circulations et coupures: retour sur l'espace
cyclique .............................................. 385
11.6 Vérification probabiliste ............................. 390
Annexe: Prérequis d'algèbre ................................... 401
Bibliographie ................................................. 411
Indications pour certains exercices ........................... 417
Index ......................................................... 441
|
