Éléments de théorie des graphes

Auteur(s) :

Bretto, Alain (1958-....) Découvrir l'auteur

Résumé

Après une introduction au langage de base, les auteurs présentent les différents types de graphes, puis les relations entre les graphes et les structures de données algorithmiques, la connexité et les flots, la notion de planarité. Ce sont ensuite les aspects algébriques élémentaires de la théorie des graphes qui sont étudiés, les colorations et couplages, la théorie spectrale. ©Electre 2018

Autre(s) auteur(s)
- Faisant, Alain
- Hennecart, François (1966-....)
Éditeur(s)
- Lavoisier Hermès
- Impr. CPI Firmin-Didot
Date
- DL 2018
Notes
- Index
Langues
- Français
Description matérielle
- 1 vol. (XIX-542 p.) : ill. ; 24 cm
Collections
- Collection IRIS (Paris. 2000)
Sujet(s)
- Théorie des graphes
ISBN
- 978-2-7462-4850-2
Indice
- 511.5 Théorie des graphes
Quatrième de couverture
- Cet ouvrage est une introduction à la théorie des graphes. La plupart des notions élémentaires et classiques y sont introduites selon une approche originale, précise et rigoureuse. Ainsi les résultats énoncés font l'objet, dans leur quasi-totalité, de démonstrations détaillées.
  L'aspect topologique et l'aspect algébrique, derniers avatars de cette théorie, ont été développés de manière approfondie. La variété des thèmes abordés a pour objectif de conduire le lecteur à appréhender les graphes dans leur plus grande diversité afin d'en percevoir la puissance en tant qu'outil mathématique. L'accent a également été mis sur l'algorithmique des graphes, qui se prêtent particulièrement bien aux structures de données et à la programmation.
  Cette deuxième édition propose une présentation plus complète des graphes planaires et de la théorie spectrale. On y trouve aussi un nouveau chapitre sur les graphes aléatoires et quelques éléments d'analyse sur graphes.
  Ce livre peut être d'usage courant pour les étudiants en informatique et en mathématiques du niveau licence mais il s'adresse également aux étudiants de master ainsi qu'aux élèves ingénieurs. Il pourra aussi être utile à des étudiants doctorants et à des chercheurs confirmés voulant en savoir plus sur ce domaine.
Tables des matières
- - Éléments de théorie des graphes
  - Alain Bretto
  - Alain Faisant
  - François Hennecart
  - Lavoisier
  - Préface de la deuxième éditionv
  - À propos des auteursvii
  - Avant-propos à la première éditionix
  - 1 Concepts fondamentaux 1
  - 1.1 Graphes non orientés1
  - 1.1.1 Degré6
  - 1.1.2 Chaîne et cycle7
  - 1.1.3 Sous-graphes9
  - 1.2 Décomposition connexe13
  - 1.3 Graphes orientés14
  - 1.4 Graphes simples17
  - 1.5 Opérations sur les graphes20
  - 1.6 Représentations des graphes20
  - 1.7 Algorithmes et théorie de la complexité22
  - 1.7.1 Complexité en temps d'un algorithme23
  - 1.7.2 Classes de complexité28
  - 1.8 Définition d'un graphe à partir de la fonction d'incidence29
  - 1.9 Isomorphismes de graphes. Groupes d'automorphismes30
  - 1.10 Compléments : quelques structures de base34
  - 2 Quelques graphes remarquables 37
  - 2.1 Graphes bipartis37
  - 2.2 Arbres et arborescences42
  - 2.2.1 Arbres42
  - 2.2.2 Arborescences47
  - 2.3 Digraphes sans circuit50
  - 2.4 Graphes eulériens et graphes hamiltoniens53
  - 2.4.1 Graphes eulériens53
  - 2.4.2 Graphes hamiltoniens57
  - 3 (Di)graphes et structures de données 67
  - 3.1 Procédures récursives68
  - 3.1.1 Complexité d'un algorithme récursif70
  - 3.2 Arbres et arborescences : le retour73
  - 3.2.1 Représentation d'une arborescence sous forme fils-frère75
  - 3.2.2 Arborescences binaires80
  - 3.2.3 Arborescences binaires de recherche82
  - 3.2.4 Arborescences de priorité, les tas90
  - 3.2.5 Arborescences AVL94
  - 3.2.6 Propriétés des arborescences binaires100
  - 3.3 Complexité en temps des algorithmes sur les arborescences binaires102
  - 3.4 Graphes : le retour104
  - 3.4.1 Représentation par matrice d'adjacence104
  - 3.4.2 Représentation par tableau des listes de successeurs104
  - 3.4.3 Remarques sur la complexité de ces représentations105
  - 3.4.4 Parcours d'un (di)graphe105
  - 3.5 Compléments110
  - 3.5.1 Types de données simples110
  - 3.5.2 Fonctions112
  - 3.5.3 Passage des paramètres dans une fonction113
  - 3.5.4 Structures linéaires114
  - 4 Connexité et flots dans les réseaux 121
  - 4.1 Sommet-connexité et arête-connexité121
  - 4.2 Graphes 2-sommet-connexes125
  - 4.3 Graphes 2-arête-connexes133
  - 4.4 Flots dans un réseau134
  - 4.4.1 Définitions135
  - 4.4.2 Le théorème de Ford et Fulkerson139
  - 4.5 Applications des flots dans un réseau146
  - 4.6 Compléments : lois de Kirchhoff151
  - 5 Graphes planaires 155
  - 5.1 Dessins155
  - 5.2 Graphes planaires158
  - 5.2.1 Rappels de topologie de (...)ⁿ158
  - 5.2.2 Lignes polygonales158
  - 5.2.3 Graphes plongés170
  - 5.2.4 Faces171
  - 5.2.5 La formule d'Euler174
  - 5.2.6 Graphes planaires et blocs179
  - 5.2.7 Graphes planaires 2-connexes181
  - 5.3 Graphes planaires maximaux et polyèdres181
  - 5.3.1 Graphes planaires maximaux181
  - 5.3.2 Polyèdres184
  - 5.4 Comparaison des plongements186
  - 5.5 Le théorème de Kuratowski et le théorème de Wagner190
  - 5.6 Graphe dual199
  - 5.7 Croisements, épaisseur et genre d'un graphe203
  - 5.7.1 Croisements et épaisseur203
  - 5.7.2 Genre d'un graphe205
  - 5.8 Compléments de topologie et géométrie du plan211
  - 5.8.1 Éléments de topologie211
  - 5.8.2 Preuve du théorème de Jordan polygonal215
  - 6 Graphes et algèbre linéaire 223
  - 6.1 Matrices et graphes223
  - 6.1.1 Le cas orienté229
  - 6.1.2 Le cas non orienté230
  - 6.2 Espaces vectoriels et graphes232
  - 6.2.1 Cas des graphes orientés232
  - 6.2.2 Cas des groupes non orientés236
  - 6.3 Circulation238
  - 6.4 Graphes planaires242
  - 6.5 Compléments d'algèbre linéaire245
  - 6.5.1 Espaces vectoriels245
  - 6.5.2 Matrices248
  - 6.5.3 Produits scalaires251
  - 6.5.4 L'espace hermitien (...)ⁿ252
  - 7 Coloration 257
  - 7.1 Coloration des sommets258
  - 7.1.1 Propriétés générales258
  - 7.1.2 Le théorème de Brooks263
  - 7.1.3 Le théorème de Zykov266
  - 7.1.4 Graphes critiques267
  - 7.1.5 Graphes constructibles269
  - 7.1.6 Graphes planaires et cartes271
  - 7.2 Coloration des arêtes276
  - 7.3 Morphismes de graphes283
  - 7.3.1 Quotients de graphe285
  - 7.3.2 Morphismes et quotients de graphes simples286
  - 7.3.3 Morphismes et coloration287
  - 7.4 Graphes parfaits289
  - 7.5 Coloration par listes292
  - 7.6 Polynôme chromatique295
  - 8 Couplage et factorisation 299
  - 8.1 Définitions et premières propriétés299
  - 8.2 Couplages dans les graphes bipartis305
  - 8.2.1 Le théorème de Hall305
  - 8.2.2 Réseau associé à un graphe biparti308
  - 8.2.3 Remarques d'ordre algorithmique309
  - 8.3 Couplages dans les graphes quelconques309
  - 8.4 Factorisation317
  - 8.5 Quelques applications des couplages319
  - 8.6 Généralisation de la notion de facteur327
  - 9 Graphes et théorie des groupes 331
  - 9.1 Groupes de permutations331
  - 9.2 Groupes d'automorphismes d'un graphe et de son graphe des arêtes333
  - 9.2.1 Automorphismes, automorphismes d'arêtes333
  - 9.2.2 Étude de Ker (...)337
  - 9.2.3 Étude de Im (...)337
  - 9.3 Graphe de Cayley colorié340
  - 9.4 Le problème de König343
  - 9.5 Action de groupe348
  - 9.6 Graphes transitifs352
  - 10 Théorie spectrale et applications 355
  - 10.1 Spectre d'un graphe355
  - 10.1.1 Polynôme caractéristique355
  - 10.1.2 Entrelacement des valeurs propres357
  - 10.1.3 Spectres des graphes bipartis362
  - 10.1.4 Propriétés combinatoires du polynôme caractéristique365
  - 10.1.5 Spectre, diamètre et coloration368
  - 10.2 Laplacien d'un graphe371
  - 10.3 Spectre de graphes réguliers379
  - 10.3.1 Trou spectral379
  - 10.3.2 Graphes expanseurs382
  - 10.4 Graphes de Ramanujan385
  - 10.4.1 Un exemple : le graphe de Petersen385
  - 10.4.2 Majoration du diamètre388
  - 10.4.3 Minorations de (...)389
  - 10.5 Graphes de Cayley non orientés395
  - 10.5.1 Graphes circulants395
  - 10.5.2 Actions de groupes sur les graphes de Cayley398
  - 10.5.3 Le cas du graphe de Petersen399
  - 10.5.4 Cycles hamiltoniens dans les graphes de Cayley401
  - 11 Graphes aléatoires 405
  - 11.1 Modèles de graphes aléatoires406
  - 11.2 Propriétés statistiques des graphes411
  - 11.3 Propriétés satisfaites asymptotiquement par presque tous les graphes413
  - 11.4 Propriétés structurelles principales des graphes aléatoires415
  - 11.5 Transition de phase421
  - 11.5.1 Valeurs critiques du paramètre de Bernoulli421
  - 11.5.2 Quelques exemples de fonctions seuil425
  - 11.6 Résumé des étapes de l'évolution de (...)(n; p)426
  - 11.7 Quelques remarques428
  - 11.8 Quelques rappels de probabilité430
  - 11.8.1 Espaces probabilisés et mesures de probabilité430
  - 11.8.2 Indépendance et probabilités conditionnelles432
  - 11.8.3 Variables aléatoires finies433
  - 11.8.4 Quelques exemples de lois de probabilités434
  - 11.8.5 Inégalités classiques435
  - 11.8.6 Propriétés asymptotiques438
  - 12 Graphes pondérés et applications 443
  - 12.1 Graphes pondérés443
  - 12.2 Le laplacien en physique444
  - 12.3 De la physique aux graphes : laplacien harmonique445
  - 12.3.1 Dérivée seconde discrète445
  - 12.3.2 Laplacien d'un graphe pondéré446
  - 12.3.3 Gradient d'une fonction et formules de GREEN448
  - 12.3.4 Laplacien orienté450
  - 12.4 Problème de Dirichlet450
  - 12.5 Marches aléatoires dans les graphes453
  - 12.5.1 Chaînes de Markov453
  - 12.5.2 Stationnarité et réversibilité458
  - 12.5.3 Classes de communication460
  - 12.5.4 Classification des états460
  - 12.5.5 Périodicité465
  - 12.5.6 Mémento des propriétés fondamentales467
  - 12.5.7 Exemples de chaînes de Markov471
  - 12.5.8 Le modèle d'Ising en dimension 2474
  - 12.6 Réseaux électriques478
  - 12.6.1 Définitions478
  - 12.6.2 Réseaux électriques et marches aléatoires480
  - 12.6.3 Principe de Thomson et loi de Rayleigh481
  - 12.6.4 Promenade aléatoire dans (...)485
  - 12.7 Inégalité de Cheeger488
  - 13 Autres perspectives 495
  - 13.1 Polynômes de Tutte495
  - 13.1.1 Propriétés de base497
  - 13.1.2 Polynôme de Tutte et polynôme chromatique504
  - 13.1.3 Polynôme de Tutte et arbres de recouvrement505
  - 13.1.4 Polynôme de Tutte et planarité506
  - 13.1.5 Autres applications507
  - 13.2 Théorie de Ramsey508
  - 13.3 Matroïdes515
  - 13.4 Hypergraphes520
  - Bibliographie525
  - Index527
  - Symboles utilisés537
Origine de la notice:
- FR-751131015 ;
- Electre