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

335

pages

Français

Ebooks

2011

Écrit par
Fournier Jean-Claude

Publié par
Hermès - Editions Lavoisier

Lire un extrait

Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus

Découvre YouScribe en t'inscrivant gratuitement

Je m'inscris

Découvre YouScribe en t'inscrivant gratuitement

Je m'inscris

335

pages

Français

Ebook

2011

Lire un extrait

Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus

Publié par

Hermès - Editions Lavoisier

Date de parution

21 avril 2011

Nombre de lectures

285

EAN13

9782746241732

Langue

Français

Poids de l'ouvrage

2 Mo

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.

Voir

Publié par

Hermès - Editions Lavoisier

Date de parution

21 avril 2011

Nombre de lectures

285

EAN13

9782746241732

Langue

Français

Poids de l'ouvrage

2 Mo

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é signiﬁ-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 eﬃcace de reconnaissance de certaines classes de graphes. Un appendice,Algorithmes randomisés de graphes, est donné en ﬁn d’ou-vrage. Ces algorithmes ont beaucoup été développés ces dernières années. Ils représententunetouteautrefa¸cond’envisageruntraitementalgorithmique, quipermetderésoudredefac¸onéléganteeteﬃcacebeaucoupdeproblèmes, dont certains connus pour être algorithmiquement diﬃciles. Deux exemples représentatifs de problèmes de graphes sont ainsi traités. Enﬁn, 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

Chapitre 1. Généralités 15 1.1. Origine de la notion de graphe . . . . . . . . . . . . . . . . . . 15 1.2. Déﬁnition 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éﬁnitions 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

Théorie des graphes et applications

Chapitre 4. Graphes orientés 4.1. Déﬁnitions 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’aﬀectation . . . . . . . . . . . . . . . . . . . . . 188 8.4. Problème de l’aﬀectation 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 ﬂot maximum . . . . . . . . . . . . . . . . . . . 211

Voir