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

-

Livres
335 pages
Lire un extrait
Obtenez un accès à la bibliothèque pour le consulter en ligne
En savoir plus

Description

Théorie des graphes et applications est un ouvrage, à la fois pédagogique et complet, qui présente une é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 le problème de l'emploi du temps avec les colorations, l'affectation optimale avec les couplages et le "voyageur de commerce" avec les cycles hamiltoniens.
Dans cette nouvelle édition de Théorie des graphes et applications, le thème des chemins optimaux - aux nombreuses applications - est enrichi de nouveaux algorithmes présentés de façon originale. Chaque chapitre est accompagné d'exercices de niveaux différents.
Des problèmes généraux sont proposés en fin d'ouvrage. Les algorithmes randomisés de graphes y sont aussi traités. Deux annexes aident le lecteur, en particulier pour une introduction au délicat sujet de la complexité algorithmique.
Introduction. Chapitre 1. Généralités. Chapitre 2. Arbres. Chapitre 3. Colorations. Chapitre 4. Graphes orientés. Chapitre 5. Recherche arborescente. Chapitre 6. Chemins optimaux. Chapitre 7. Parcours en largeur lexicographique. Chapitre 8. Couplages. Chapitre 9. Flots. Chapitre 10. Tournées eulériennes. Chapitre 11. Tournées hamiltonniennes. Chapitre 12. Représentations planes. Chapitre 13. Problèmes commentés. Appendice. Algorithmes randomisés de graphes. Annexe A. Expression des algorithmes. Annexe B. Bases de la théorie de la complexité. Bibliographie. Index.

Sujets

Informations

Publié par
Date de parution 21 avril 2011
Nombre de visites sur la page 147
EAN13 9782746241732
Langue Français

Informations légales : prix de location à la page 0,063 €. Cette information est donnée uniquement à titre indicatif conformément à la législation en vigueur.

Signaler un problème
Théorie des graphes et applications
A Hugo, Eliott, Mathieu, Elise, Aurélie, Antonin, Ethan, Ermine et suivants…
© LAVOISIER, 2006, 2011 LAVOISIER 11, rue Lavoisier 75008 Paris www.hermes-science.com www.lavoisier.fr ISBN 978-2-7462-3215-0 ISSN 1242-7691 Le Code de la propriété intellectuelle n'autorisant, aux termes de l'article L. 122-5, d'une part, que les "copies ou reproductions strictement réservées à l'usage privé du copiste et non destinées à une utilisation collective" et, d'autre part, que les analyses et les courtes citations dans un but d'exemple et d'illustration, "toute représentation ou reproduction intégrale, ou partielle, faite sans le consentement de l'auteur ou de ses ayants droit ou ayants cause, est illicite" (article L. 122-4). Cette représentation ou reproduction, par quelque procédé que ce soit, constituerait donc une contrefaçon sanctionnée par les articles L. 335-2 et suivants du Code de la propriété intellectuelle. Tous les noms de sociétés ou de produits cités dans cet ouvrage sont utilisés à des fins d’identification et sont des marques de leurs détenteurs respectifs. Printed and bound in England by Antony Rowe Ltd, Chippenham, April 2011.
Théorie des graphes et applications avec exercices et problèmese 2 édition, revue et augmentée Jean-Claude Fournier
Collection dirigée par Jean-Charles Pomerol
Extrait de la collection
BANATREMichelet al.Informatique diffuse, 2007.
BARTHELEMYPierre, ROLLANDRobert et VERONPascal –Cryptographie, 2005.
CAFERRARicardo –Logique pour l’informatique et pour l’intelligence artificielle, 2010
CARDONAlain –La complexité organisée : systèmes adaptatifs, 2004.
CHRISMENTClaudeet al.Bases de données relationnelles, 2008.
CHRISMENTClaudeet al.Bases de données orientées-objet, 2011
GUILLOTPhilippe –Courbes elliptiques : une présentation élémentaire pour la cryptographie, 2010.
HOMESBernard –Les tests logiciels, 2011
PARISStéphane –Le multimédia et la compression, 2009.
PARISStéphane –Le multimédia,2009.
PIERSONJacky –La biométrie, 2007.
POLIAlain et GUILLOTPhilippe –Algèbre et protection de l’information, 2005.
POLIAlain et GUILLOTPhilippe –Algèbre, confidentialité et intégrité en multimédia, 2009.
VARRETTESébastien et BERNARDNicolas –Programmation avancée en C avec exercices corrigés, 2006.
VERDRETPhilippe –De Perl à Java : programmation des expressions régulières, 2004.
Avant-propos à la deuxième édition
Cette deuxième édition est expurgée de quelques erreurs et incorrections malheureusement encore présentes dans la première édition. Mais surtout, elle est enrichie de plusieurs parties nouvelles, sur des sujets qui se sont révélés utiles dans un ouvrage de base sur la théorie des graphes et ses applications. C’est d’abord le chapitre 6,Chemins optimaux, qui a été complété signifi-cativement avec une série d’algorithmes qui résolvent le problème général de la recherche de plus courts chemins dans les graphes valués. Ces algorithmes sont classiques aussi, mais beaucoup plus sophistiqués que les très classiques algorithmes de Dijkstra et de Floyd. Nous introduisons à cette occasion une expression algorithmique originale qui permet une présentation plus simple et conceptuellement plus claire de ces algorithmes. Un chapitre entièrement nouveau a été ajouté : le chapitre 7,Parcours en largeur lexicographique. Il s’agit d’un algorithme devenu très classique aujourd’hui, et qui est un outil efficace de reconnaissance de certaines classes de graphes. Un appendice,Algorithmes randomisés de graphes, est donné en fin d’ou-vrage. Ces algorithmes ont beaucoup été développés ces dernières années. Ils représententunetouteautrefa¸condenvisageruntraitementalgorithmique, quipermetderésoudredefac¸onéléganteetecacebeaucoupdeproblèmes, dont certains connus pour être algorithmiquement difficiles. Deux exemples représentatifs de problèmes de graphes sont ainsi traités. Enfin, pour faciliter l’accès aux notions décrites dans cet ouvrage, l’index a été largement développé. En particulier, à la rubriqueAlgorithmesont référencés les algorithmes étudiés, et à la rubriqueProblème, les problèmes traités. Nous remercions Guillaume Fournier pour sa participation à la mise au point de ces nouvelles parties.
Jean-Claude Fournier
Introduction
Table
des
matières
11
Chapitre 1. Généralités 15 1.1. Origine de la notion de graphe . . . . . . . . . . . . . . . . . . 15 1.2. Définition des graphes . . . . . . . . . . . . . . . . . . . . . . 19 1.3. Sous-graphes . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 1.4. Châınes et cycles . . . . . . . . . . . . . . . . . . . . . . . . . 26 1.5. Degrés . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 1.6. Connexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 1.7. Graphes bipartis . . . . . . . . . . . . . . . . . . . . . . . . . 32 1.8. Aspects algorithmiques . . . . . . . . . . . . . . . . . . . . . . 34 1.9. Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
Chapitre 2. Arbres 41 2.1. Définitions et propriétés . . . . . . . . . . . . . . . . . . . . . 41 2.2. Arbres couvrants . . . . . . . . . . . . . . . . . . . . . . . . . 46 2.3. Problème de l’arbre couvrant minimum . . . . . . . . . . . . . 51 2.4. Connectivité . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 2.5. Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
Chapitre 3. Colorations 69 3.1. Problèmes de colorations . . . . . . . . . . . . . . . . . . . . . 69 3.2. Colorations d’arêtes . . . . . . . . . . . . . . . . . . . . . . . . 69 3.3. Aspects algorithmiques . . . . . . . . . . . . . . . . . . . . . . 71 3.4. Le problème de l’emploi du temps . . . . . . . . . . . . . . . . 73 3.5. Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
8
Théorie des graphes et applications
Chapitre 4. Graphes orientés 4.1. Définitions et généralités . . . . . . . . . . . . . . . . . . . . . 4.2. Graphes orientés sans circuits . . . . . . . . . . . . . . . . . . 4.3. Arborescences . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.4. Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
83 83 90 94 97
Chapitre 5. Recherche arborescente 99 5.1. Parcours d’une arborescence . . . . . . . . . . . . . . . . . . . 99 5.2. Optimisation d’une suite de décisions . . . . . . . . . . . . . . 105 5.3. Parcours d’un graphe orienté . . . . . . . . . . . . . . . . . . . 111 5.4. Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
Chapitre 6. Chemins optimaux 123 6.1. Problèmes de distances et de plus courts chemins . . . . . . . 123 6.2. Graphes non valués, parcours en largeur . . . . . . . . . . . . 125 6.3. Cas des graphes sans circuits . . . . . . . . . . . . . . . . . . . 130 6.4. Application à l’ordonnancement . . . . . . . . . . . . . . . . . 132 6.5. Cas des longueurs positives . . . . . . . . . . . . . . . . . . . . 139 6.6. Cas général . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146 6.7. Algorithme de Floyd . . . . . . . . . . . . . . . . . . . . . . . 160 6.8. Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161
Chapitre 7. Parcours en largeur lexicographique 167 7.1. Retour sur le parcours en largeur . . . . . . . . . . . . . . . . 167 7.2. LexBFS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168 7.3. Application aux graphes triangulés . . . . . . . . . . . . . . . 172 7.4. Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179
Chapitre 8. Couplages 181 8.1. Couplages et châınes alternées . . . . . . . . . . . . . . . . . . 181 8.2. Couplages dans les graphes bipartis . . . . . . . . . . . . . . . 184 8.3. Problème de l’affectation . . . . . . . . . . . . . . . . . . . . . 188 8.4. Problème de l’affectation optimale . . . . . . . . . . . . . . . . 196 8.5. Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 204
Chapitre 9. Flots 207 9.1. Flots dans les réseaux de transport . . . . . . . . . . . . . . . 207 9.2. Théorème du flot maximum . . . . . . . . . . . . . . . . . . . 211