Théorie des graphes et applications : avec exercices et problèmes

Auteur(s) :

Fournier, Jean-Claude (1940-....) Découvrir l'auteur

Résumé

Etude des principaux aspects de la théorie des graphes et de ses applications, en particulier celles relevant de l'optimisation combinatoire.

Contributeur(s)
- Pomerol, Jean-Charles (1943-....). Metteur en scène ou réalisateur
Éditeur(s)
- Hermès science publications
- Lavoisier
Date
- 2006
Notes
- Bibliogr. p. [284]. Index
Langues
- Français
Description matérielle
- 288 p. ; 24 x 16 cm
Collections
- Informatique
Sujet(s)
ISBN
- 2-7462-1247-1
Indice
- 511.5 Théorie des graphes
Quatrième de couverture
- Cet ouvrage, à la fois pédagogique et complet, présente l'étude des principaux aspects de la théorie des graphes et de ses applications, en particulier celles relevant de l'optimisation combinatoire.
  Il expose ainsi en détail des sujets significatifs associés, tels que, par exemple, le problème de l'emploi du temps avec les colorations, l'affectation optimale avec les couplages, le «voyageur de commerce» avec les cycles hamiltoniens, etc.
  Des exercices de tous niveaux accompagnent les chapitres, des problèmes généraux sont proposés à la fin. Deux annexes peuvent utilement aider le lecteur sur les algorithmes, en particulier pour une introduction au délicat sujet de la complexité algorithmique.
Tables des matières
- - Théorie des graphes et applications
  - avec exercices et problèmes
  - Jean-Claude Fournier
  - hermes Science publications
  - Lavoisier
  - Introduction
    9
  - Chapitre 1. Généralités 13
  - 1.1. Origine de la notion de graphe13
  - 1.2. Définition des graphes17
  - 1.3. Sous-graphes21
  - 1.4. Chaînes et cycles22
  - 1.5. Degrés27
  - 1.6. Connexité29
  - 1.7. Graphes bipartis30
  - 1.8. Aspects algorithmiques32
  - 1.9. Exercices
    36
  - Chapitre 2. Arbres 39
  - 2.1. Définitions et propriétés39
  - 2.2. Arbres couvrants44
  - 2.3. Problème de l'arbre couvrant minimum49
  - 2.4. Connectivité54
  - 2.5. Exercices
    62
  - Chapitre 3. Colorations 67
  - 3.1. Problèmes de colorations67
  - 3.2. Colorations d'arêtes67
  - 3.3. Aspects algorithmiques69
  - 3.4. Le problème de l'emploi du temps71
  - 3.5. Exercices
    78
  - Chapitre 4. Graphes orientés 81
  - 4.1. Définitions et généralités81
  - 4.2. Graphes orientés sans circuits89
  - 4.3. Arborescences91
  - 4.4. Exercices
    95
  - Chapitre 5. Recherche arborescente 97
  - 5.1. Parcours d'une arborescence97
  - 5.2. Optimisation d'une suite de décisions103
  - 5.3. Parcours d'un graphe orienté109
  - 5.4. Exercices
    118
  - Chapitre 6. Chemins optimaux 121
  - 6.1. Problèmes de distances et de plus courts chemins121
  - 6.2. Graphes non valués, parcours en largeur123
  - 6.3. Cas des graphes sans circuits128
  - 6.4. Application à l'ordonnancement130
  - 6.5. Cas des longueurs positives136
  - 6.6. Autres cas144
  - 6.7. Exercices
    146
  - Chapitre 7. Couplages 151
  - 7.1. Couplages et chaînes alternées151
  - 7.2. Couplages dans les graphes bipartis154
  - 7.3. Problème de l'affectation158
  - 7.4. Problème de l'affectation optimale164
  - 7.5. Exercices
    174
  - Chapitre 8. Flots 177
  - 8.1. Flots dans les réseaux de transport177
  - 8.2. Théorème du flot maximum181
  - 8.3. Algorithme du flot maximum185
  - 8.4. Flots avec stocks et demandes193
  - 8.5. Revisites de théorèmes196
  - 8.6. Exercices
    200
  - Chapitre 9. Tournées eulériennes 201
  - 9.1. Chaînes et cycles eulériens201
  - 9.2. Algorithmes205
  - 9.3. Problème du postier chinois210
  - 9.4. Exercices
    217
  - Chapitre 10. Tournées hamiltonniennes 219
  - 10.1. Cycles hamiltoniens219
  - 10.2. Le problème du voyageur de commerce222
  - 10.3. Approximation d'un problème difficile225
  - 10.4. Approximation du PVC géographique227
  - 10.5. Exercices
    239
  - Chapitre 11. Représentations planes 241
  - 11.1. Graphes planaires241
  - 11.2. Autres représentations des graphes247
  - 11.3. Exercices
    249
  - Chapitre 12. Problèmes commentés 251
  - 12.1. Problème 1: une démonstration de k-connexité251
  - 12.2. Problème 2: une application à la compilation253
  - 12.3. Problème 3: noyaux dans un graphe255
  - 12.4. Problème 4: couplage dans un graphe biparti régulier258
  - 12.5. Problème 5: théorème de Birkhoff-Von Neumann259
  - 12.6. Problème 6: couplages et pavages261
  - 12.7. Problème 7: exploitation d'une mine à ciel ouvert
    263
  - Annexe 1. Expression des algorithmes
    267
  - Annexe 2. Bases de la théorie de la complexité
    273
  - Bibliographie
    285
  - Index 287
Origine de la notice:
- Electre