Graphes et hypergraphes

Page de titre......Page 1
Avant-propos......Page 5
Table dess matières......Page 9
PREMIÈRE PARTIE. LES GRAPHES......Page 13
1. Le concept de graphe......Page 15
2. Glossaire de base pour la théorie des graphes......Page 17
3. Liste des symboles......Page 21
1. Cycles et cocycles......Page 23
2. Cycles dans un graphe planaire......Page 28
1. Arbres et coarbres......Page 34
2. Graphes fortement connexes et graphes sans circuits......Page 37
3. Arborescences......Page 42
4. Graphes injectifs, fonctionnels, semi-fonctionnels......Page 45
5. Dénombrements d'arbres......Page 51
1. Le problème du chemin entre deux points......Page 63
2. Le problème du plus court chemin......Page 68
3. Centres et rayon d'un graphe quasi fortement connexe......Page 70
4. Diamètre d'un graphe fortement connexe......Page 74
5. Dénombrements de chemins......Page 81
1. Le problème du flot maximum......Page 84
2. Le problème du flot compatible......Page 94
3. Flots et tensions : étude algébrique......Page 97
4. Le problème de la tension maximum......Page 102
1. Existence d'un p-graphe avec des demi-degrés donnés......Page 109
2. Existence d'un p-graphe sans boucles avec des demi-degrés donnés......Page 116
3. Existence d'un graphe simple avec des degrés donnés......Page 122
1. Le problème du couplage maximum......Page 129
2. Le problème du recouvrement minimum......Page 136
3. Couplages dans un graphe biparti......Page 137
4. Une extension du théorème de Konig......Page 147
1. Le problème du c-couplage maximum......Page 157
2. Transferts......Page 160
3. Évaluation de la cardinalité maximum......Page 162
1. Graphes h-connexes......Page 170
2. Points d'articulation et blocs......Page 180
3. Graphes k-arête-connexes......Page 185
1. Chemins et circuits hamiltoniens......Page 191
2. Chemins hamiltoniens dans un graphe complet......Page 197
3. Théorèmes d'existence pour un circuit hamiltonien......Page 200
4. Théorèmes d'existence pour un cycle hamiltonien......Page 209
5. Graphes Hamilton-connectés......Page 220
6. Cycles hamiltoniens dans un graphe planaire (résultats)......Page 225
1. Cycles eulériens dans un multigraphe......Page 230
2. Recouvrement des arêtes par des chaînes disjointes......Page 234
3. Dénombrement des circuits eulériens......Page 240
1. Coloration des arêtes......Page 248
2. Théorèmes généraux......Page 254
3. Coloration des arêtes d'un graphe planaire régulier......Page 267
1. Caractérisations d'un ensemble stable maximum......Page 272
2. Théorème de Turan et variations......Page 278
3. Graphes ex-critiques......Page 286
4. Sommets et arêtes critiques......Page 297
5. Nombre de stabilité et recouvrement des sommets par des chemins......Page 298
1. Nombre d'absorption......Page 303
2. Noyaux......Page 307
3. Fonctions de Grundy......Page 312
4. Applications aux jeux du type Nim......Page 319
1. Coloration des sommets......Page 326
2. Graphes y-critiques......Page 339
3. Construction de Hajos......Page 349
4. Dénombrement des colorations : polynômes chromatiques......Page 352
5. Colorations de graphes planaires (résultats)......Page 354
1. Graphes (x-parfaits et y-parfaits......Page 359
2. Graphes de comparabilité......Page 362
3. Graphes triangulés......Page 366
4. Graphes i-triangulés......Page 368
5. Graphes représentatifs d'une famille d'intervalles......Page 370
6. Nombres fondamentaux d'un produit ou d'une somme cartésienne de graphes simples......Page 375
DEUXIÈME PARTIE. LES HYPERGRAPHES......Page 383
1. Le concept d'hypergraphe......Page 385
2. Cycles d'un hypergraphe......Page 387
3. Hypergraphes associés aux familles de cliques d'un graphe......Page 392
4. Graphe représentatif des arêtes d'un hypergraphe......Page 395
1. Couplages et c-couplages dans un hypergraphe......Page 408
2. Nombre de transversalité......Page 413
1. Nombre de stabilité et nombre chromatique d'un hypergraphe......Page 422
2. Cliques d'un hypergraphe......Page 426
3. Application aux bonnes colorations des arêtes d'un graphe......Page 431
4. Application aux différentes généralisations du nombre chromatique d'un graphe......Page 434
1. Nombre de stabilité fort et nombre chromatique fort d'un hypergraphe......Page 440
2. Hypergraphes équilibrés......Page 442
3. Hypergraphes unimodulaires......Page 449
4. Application aux fonctions stochastiques......Page 458
1. Matroïde sur un ensemble......Page 465
2. Théorème de Rado et variations......Page 470
3. Image d'un matroïde......Page 475
4. Le problème de la base de poids minimum et de l'arbre de longueur minimum......Page 482
Bibliographie......Page 487
Liste des termes utilisés, lexique français-anglais-allemand......Page 507