Graphes et algorithmes, 4e éd. (collection EDF R&D)

Minoux Michel, Gondran Michel

Description

Les modèles et les algorithmes de graphes se sont imposés aujourd'hui dans de nombreuses disciplines, aussi bien dans les sciences de base (physique, chimie, biologie, sciences humaines, informatique théorique et algorithmique) que dans les sciences de l'ingénieur (automatique, optimisation de systèmes, économie et recherche opérationnelle, analyse de données, ingénierie des grands réseaux de communication de type internet, etc). Cette nouvelle édition est la seule à offrir un panorama aussi complet de ces outils et de leurs plus récents développements.
Graphes et algorithmes rend compte de la puissance de modélisation procurée par les graphes, et de la disponibilité d'une vaste panoplie d'algorithmes opérationnels. Cette nouvelle édition développe les nombreux résultats, souvent fins, conduisant à la réduction de la complexité des algorithmes (flots, chemins, arbres, etc.) , les nouvelles familles d'algorithmes approchés (ou métaheuristiques) en particulier ceux inspirés de la biologie (algorithmes génétiques, ou ceux imitant le comportement des colonies de fourmis) , les algorithmes fondés sur des processus aléatoires (algorithmes itératifs aléatoires ou algorithmes gloutons aléatoires).
Proposant au lecteur environ 230 exercices et plus de 100 problèmes concrets modélisés, cette nouvelle édition s'est enrichie aussi d'une présentation plus aérée et de nombreuses références bibliographiques.
Graphes et algorithmes s'adresse à un large éventail de chercheurs et ingénieurs des laboratoires et bureaux d'études, et de futurs ingénieurs et étudiants en licence et master.
1. Généralités sur les graphes. Définitions et concepts de base. Matrices associées à un graphe. Connexité. Cycles et cocycles - Nombre cyclomatique. Quelques graphes particuliers. Les hypergraphes. Graphes aléatoires et connexité. 2. Le problème du plus court chemin. Définitions et exemples. Les algorithmes. Le problème central de l'ordonnancement. 3. Algèbres de chemins et dioïdes. L'algèbre du plus court chemin. Définitions et propriétés. Quelques exemples. Algorithmes généraux. Algèbres de chemins dans un graphe sans circuit. Un dioïde particulier. Les dioïdes à gauche et à droite. Généralisation des algèbres de chemins. Théorie des dioïdes et applications. 4. Arbres et arborescences. Arbres - Définitions et propriétés. Le problème de l'arbre de poids minimum. Arborescences. 5. Flots et réseaux de transport. Définitions et propriétés. Le problème du flot maximum dans un réseau de transport. Le problème du flot compatible - Théorème de compatibilité. Flots et connexité. Flots à coût minimum. 6. Flots avec multiplicateurs - Multiflots. Flots avec multiplicateurs. Problèmes de multiflots. 7. Couplages et b-couplages. Le problème du couplage maximum. Algorithme de recherche d'un couplage maximum. Couplage de poids maximum. Un algorithme pour le problème du couplage de poids maximum. b-Couplages - b-Couplages maximum et b-couplage de poids maximum. 8. Parcours eulériens et hamiltoniens. Cycles et chaînes eulériens. Le problème du Postier chinois (non orienté). Circuits et cycles hamiltoniens. 9. Matroïdes. Définitions et résultats fondamentaux. Dualité. Le problème du sous-ensemble indépendant de poids maximum : l'algorithme glouton. Intersection de matroïdes. Matroïdes avec conditions de parité et généralisations. Polymatroïdes. 10. Les problèmes difficiles de la classe NP. Réductions et relations d'équivalence entre problèmes. Partition et recouvrement d'un hypergraphe. Le problème du couplage d'un hypergraphe. Coloration d'un graphe et d'un hypergraphe. Le problème du sac à dos multidimensionnel. Les problèmes de coûts fixes et les fonctions d'ensemble. Les problèmes d'ordonnancement. Quelques autres problèmes concrets. Problèmes NP-complets et réductions entre problèmes. 11. Les algorithmes d'énumération par séparation, évaluation et propagation de contraintes. Un exemple d'exploration par séparation, évaluation et propagation. Les procédures d'exploration par séparation et évaluation. Deux exemples d'applications. Évaluation par défaut et pénalités. ALICE. 12. Algorithmes approchés et métaheuristiques. Les algorithmes itératifs de voisinage. Les algorithmes gloutons. Les métaheuristiques inspirés de la biologie. Régularisation des coûts. Optimalité des algorithmes approchés. Annexe 1. Programmation linéaire. Annexe 2. Programmation linéaire en nombres entiers. Annexe 3. Relaxation lagrangienne et résolution du problème dual. Annexe 4. Programmation dynamique. Annexe 5. Les problèmes de ratio minimum. Index. (Exercices et références bibliogra­phiques en fin de chaque chapitre).

Informations

• Publié par: Tec & Doc - Editions Lavoisier
• Date de parution: 27 avril 2009
• Nombre de lectures: 300
• EAN13: 9782743018658
• Licence : Tous droits réservés
• Langue: Français
• Poids de l'ouvrage: 10 Mo

Extrait

9:HSMHOD=UVUXZZ:

Collection EDF R&D

Graphes et algorithmes e 4 édition

Michel฀Gondran฀•฀Michel฀Minoux

Graphes et algorithmes

e 4 édition revue et augmentée

Graphes et algorithmes

e 4 édition revue et augmentée

Michel Gondran Docteur d’État en Mathématiques appliquées Président de l’Académie européenne interdisciplinaire des Sciences (AEIS)

Michel Minoux Professeur à l’université Pierre et Marie Curie (Paris VI)

11, rue Lavoisier 75008 Paris

Chez le même éditeur

Programmation mathématique, théorie et algorithmes e M. Minoux, 2 édition, 2008

Mathématiques appliquées à l’agroalimentaire A.-C. Roudot, 2007

Les mathématiques dans le monde scientifique contemporain collection « Rapport sur la science et la technologie », n° 20 Académie des sciences, 2005

Éléments finis pour l’ingénieur : grands principes et petites méthodes collection « EDF R&D » P. Thomas, 2006

Études causales par graphes cartésiens P. Vergez, 2004

Méthode des éléments finis pour les sciences de l’ingénieur J. Chaskalovic, 2004

Techniques mathématiques pour l’industrie alimentaire collection « Sciences et techniques agroalimentaires » J.-J. Daudin, C. Duby, coord., 2002

Graphes, dioïdes et semi-anneaux M. Gondran, M. Minoux, 2002

Cas d’analyse conjointe J.-C. Liquet, 2001

Statistique pour l’environnement J. Bernier, E. Parent, J.-J. Boreux, 2000

DAN GER LE PHOTOCOPILLAGE

TUE LE LIVRE

© LAVOISIER, 2009 ISSN : 1773-5300 e ISBN : 978-2-7430-1035-5 (4 édition, 2009) e ISSN : 0399-4198 / ISBN : 978-2-2120-1571-3 (3 édition, 1995) e ISSN : 0399-4198 (2 édition, 1985) re ISSN : 0399-4198 (1 édition, 1979)

Toute reproduction ou représentation intégrale ou partielle, par quelque procédé que ce soit, des pages publiées dans le présent ouvrage, faite sans l’autorisation de l’éditeur ou du Centre français d’exploitation du droit de copie (20, rue des Grands-Augustins - 75006 Paris), est illicite et constitue une contrefaçon. Seules sont autorisées, d’une part, les reproductions strictement réservées à l’usage privé du copiste et non destinées à une utilisation collective, et, d’autre part, les analyses et courtes citations justifiées par le caractère scientifique ou d’information de l’œuvre er dans laquelle elles sont incorporées (Loi du 1 juillet 1992 - art. L 122-4 et L 122-5 et Code pénal art. 425).

À Catherine

©฀Lavoisier฀–฀La฀photocopie฀non฀autorisée฀est฀un฀délit

À Claudine

Les auteurs

Michel Gondran diplômé de l’École polytechnique docteur d’État en Mathématiques appliquées lauréat de l’Académie des sciences et de l’Académie des inscriptions et belles- lettres président de l’Académie européenne interdisciplinaire des sciences co-auteur deGraphes, dioïdes et semi-anneaux(Lavoisier, Paris, 2001 ; Springer, New York, 2008)

Michel Minoux diplômé de l’École polytechnique professeur à l’Université Pierre et Marie Curie (Paris VI) conseiller scientifique auprès de la DGA/MRIS auteur deProgrammation mathématique : théorie et algorithmes(Dunod, Paris, 1983 ; Lavoisier, Paris 2008 ; Wiley, New York, 1986 ; Nauka, Moscou, 1990) co-auteur deGraphes, dioïdes et semi-anneaux(Lavoisier, Paris, 2001 ; Springer, New York, 2008)

©฀Lavoisier฀–฀La฀photocopie฀non฀autorisée฀est฀un฀délit