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

Jean-Claude Fournier

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

• Informatique
• Algèbre
• Arithmétique
• Mathématiques

Informations

• Publié par: Hermès - Editions Lavoisier
• Date de parution: 21 avril 2011
• Nombre de lectures: 278
• EAN13: 9782746241732
• Langue: Français
• Poids de l'ouvrage: 2 Mo

Extrait

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èmes e 2 édition, revue et augmentée Jean-Claude Fournier

Collection dirigée par Jean-Charles Pomerol

Extrait de la collection

B ANATRE Michelet al.–Informatique diffuse, 2007.

B ARTHELEMY Pierre, R OLLAND Robert et V ERON Pascal –Cryptographie, 2005.

C AFERRA Ricardo –Logique pour l’informatique et pour l’intelligence artificielle, 2010

C ARDON Alain –La complexité organisée : systèmes adaptatifs, 2004.

C HRISMENT Claudeet al.–Bases de données relationnelles, 2008.

C HRISMENT Claudeet al. – Bases de données orientées-objet, 2011

G UILLOT Philippe –Courbes elliptiques : une présentation élémentaire pour la cryptographie, 2010.

H OMES Bernard –Les tests logiciels, 2011

P ARIS Stéphane –Le multimédia et la compression, 2009.

P ARIS Stéphane –Le multimédia,2009.

P IERSON Jacky –La biométrie, 2007.

P OLI Alain et G UILLOT Philippe –Algèbre et protection de l’information, 2005.

P OLI Alain et G UILLOT Philippe –Algèbre, confidentialité et intégrité en multimédia, 2009.

V ARRETTE Sébastien et B ERNARD Nicolas –Programmation avancée en C avec exercices corrigés, 2006.

V ERDRET Philippe –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¸cond’envisageruntraitementalgorithmique, quipermetderésoudredefac¸onéléganteetefficacebeaucoupdeproblè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