Graphes et hypergraphes

Cover......Page 1
Series......Page 3
Title......Page 7
Copyright page......Page 8
Dedication......Page 9
Avant-Propos......Page 11
Table des matières......Page 15
PREMIÈRE PARTIE. LES GRAPHES......Page 19
1. Le concept de graphe......Page 21
2. Glossaire de base pour la théorie des graphes......Page 23
3. Liste des symboles......Page 27
1. Cycles et cocycles......Page 29
2. Cycles dans un graphe planaire......Page 34
1. Arbres et coarbres......Page 40
2. Graphes fortement connexes et graphes sans circuits......Page 43
3. Arborescences......Page 48
4. Graphes injectifs, fonctionnels, semi-fonctionnels......Page 51
5. Dénombrements d'arbres......Page 57
1. Le problème du chemin entre deux points......Page 69
2. Le problème du plus court chemin......Page 74
3. Centres et rayon d'un graphe quasi fortement connexe......Page 76
4. Diamètre d'un graphe fortement connexe......Page 80
5. Dénombrements de chemins......Page 87
1. Le problème du flot maximum......Page 90
2. Le problème du flot compatible......Page 100
3. Flots et tensions : étude algébrique......Page 103
4. Le problème de la tension maximum......Page 108
1. Existence d'un $p$-graphe avec des demi-degrés donnés......Page 115
2. Existence d'un $p$-graphe sans boucles avec des demi-degrés donnés......Page 122
3. Existence d'un graphe simple avec des degrés donnés......Page 128
1. Le problème du couplage maximum......Page 135
2. Le problème du recouvrement minimum......Page 142
3. Couplages dans un graphe biparti......Page 143
4. Une extension du théorème de Koenig......Page 153
1. Le problème du c-couplage maximum......Page 163
2. Transferts......Page 166
3. Évaluation de la cardinalité maximum......Page 168
1. Graphes $h$-connexes......Page 176
2. Points d'articulation et blocs......Page 186
3. Graphes $k$-arête-connexes......Page 191
1. Chemins et circuits hamiltoniens......Page 197
2. Chemins hamiltoniens dans un graphe complet......Page 203
3. Théorèmes d'existence pour un circuit hamiltonien......Page 206
4. Théorèmes d'existence pour un cycle hamiltonien......Page 215
5. Graphes Hamilton-connectés......Page 226
6. Cycles hamiltoniens dans un graphe planaire (résultats)!......Page 231
1. Cycles eulériens dans un multigraphe......Page 236
2. Recouvrement des arêtes par des chaînes disjointes......Page 240
3. Dénombrement des circuits eulériens......Page 246
1. Coloration des arêtes......Page 254
2. Théorèmes généraux......Page 260
3. Coloration des arêtes d'un graphe planaire régulier......Page 273
1. Caractérisations d'un ensemble stable maximum......Page 278
2. Théorème de Turàn et variations......Page 284
3. Graphes $\alpha$-critiques......Page 292
4. Sommets et arêtes critiques......Page 303
5. Nombre de stabilité et recouvrement des sommets par des chemins......Page 304
1. Nombre d'absorption......Page 309
2. Noyaux......Page 313
3. Fonctions de Grundy......Page 318
4. Applications aux jeux du type Nim......Page 325
1. Coloration des sommets......Page 332
2. Graphes $\gamma$-critiques......Page 345
3. Construction de Hajôs......Page 355
4. Dénombrement des colorations : polynômes chromatiques......Page 358
5. Colorations de graphes planaires (résultats)......Page 360
1. Graphes $\alpha$-parfaits et $\gamma$-parfaits......Page 365
2. Graphes de comparabilité......Page 368
3. Graphes triangulés......Page 372
4. Graphes $i$-triangulés......Page 374
5. Graphes représentatifs d'une famille d'intervalles......Page 376
6. Nombres fondamentaux d'un produit ou d'une somme cartésienne de graphes simples......Page 381
DEUXIÈME PARTIE. LES HYPERGRAPHES......Page 389
1. Le concept d'hypergraphe......Page 391
2. Cycles d'un hypergraphe......Page 393
3. Hypergraphes associés aux familles de cliques d'un graphe......Page 398
4. Graphe représentatif des arêtes d'un hypergraphe......Page 401
1. Couplages et c-couplages dans un hypergraphe......Page 414
2. Nombre de transversalité......Page 419
1. Nombre de stabilité et nombre chromatique d'un hypergraphe......Page 428
2. Cliques d'un hypergraphe......Page 432
3. Application aux bonnes colorations des arêtes d'un graphe......Page 437
4. Application aux différentes généralisations du nombre chromatique d'un graphe......Page 440
1. Nombre de stabilité fort et nombre chromatique fort d'un hypergraphe......Page 446
2. Hypergraphes équilibrés......Page 448
3. Hypergraphes unimodulaires......Page 455
4. Application aux fonctions stochastiques......Page 464
1. Matroïde sur un ensemble......Page 471
2. Théorème de Rado et variations......Page 476
3. Image d'un matroïde......Page 481
4. Le problème de la base de poids minimum et de l'arbre de longueur minimum......Page 488
Bibliographie......Page 493
Liste des termes utilisés, lexique français-anglais-allemand......Page 513
Fig. 19.4......Page 521