Graphes
Cours de recherche (30h de cours, travail
sur des articles scientifiques)
Cours : Eric Thierry (Eric.Thierry)
Présentation générale
Il s'agit d'un cours avancé de théorie des graphes. Il est
accessible à tout étudiant ayant des connaissances de bases
sur les graphes et en algorithmique. Pour se faire une idée,
une bonne recommandation est la lecture des chapitres sur
les graphes du livre “Introduction à l'algorithmique” de
Cormen, Leiserson et Rivest. Les notions qui y sont introduites
feront juste l'objet de rappels très courts.
Le but du cours est de présenter plusieurs problématiques de
théorie des graphes représentatives des questions et des outils
qui ont fait l'objet de recherches récentes (étude de classes
particulières de graphes, théorème des 4 couleurs, théorème des
graphes parfaits, théorème des mineurs ...). On s'intéressera
aux aspects mathématiques et algorithmiques qui leur sont associées.
Thèmes abordés (indicatif)
- Rappels (courts) sur les définitions, théorèmes et algorithmes
de base.
- Les graphes orientés : quelques problématiques et théorèmes
spécifiques.
- Etude de classes particulières de graphes (graphes planaires,
graphes parfaits ...).
- Outils de décomposition des graphes et applications (décomposition
modulaire, largeur arborescente ...).
Bibliographie
-
Introduction to Graph Theory, D. West.
Prentice Hall, 2nd ed., 2000.
Excellent livre de base.
- Digraphs: Theory, Algorithms and Applications, J. Bang-Jensen et G. Gutin.
Springer-Verlag, 2000. Certains chapîtres sur : http://www.cs.rhul.ac.uk/books/dbook/
Excellent livre sur les graphes orientés (digraphs).
- Introduction to Algorithms, T. Cormen, C. Leiserson, R. Rivest et C. Stein.
Mcgraw-Hill (ou Dunod pour la traduction française), 2001.
Plusieurs chapîtres sur l'algorithmique des graphes.
- The Design and Analysis of Computer Algorithms.
A. Aho, J. Hopcroft et J. Ullman. Addison Wesley, 1974.
Plusieurs chapîtres sur l'algorithmique des graphes.
- Modern Graph Theory, B. Bollobas. Springer-Verlag, 1998.
Plus pointu que le West sur certains chapîtres (graphes extrémaux, graphes aléatoires ...)
- Graph Theory, R. Diestel. Springer-Verlag, 2nd ed., 2000.
Téléchargeable : http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/
Plus pointu que le West sur certains chapîtres (graphes extrémaux, théorie des mineurs ...)
- Algorithmic Graph Theory and Perfect Graphs, M. Golumbic.
Academic Press, 1980.
Bon livre sur des classes particulières de graphes (dont les graphes parfaits).
- Graph Classes: A Survey, A. Brandstadt, Van Bang Le, J. Spinrad.
Siam Monographs on Discrete Mathematics and Applications, 1999.
Synthèse des résultats connus sur les principales classes de graphes (sans les preuves).
- Network Flows: Theory, Algorithms, and Applications.
R. Ahuja, T. Magnanti, J. Orlin. Prentice Hall, 1993.
Un catalogue d'applications des algorithmes de flots (mais des problèmes dans les preuves).
- Proofs from the Book, M. Aigner, G. M. Ziegler.
Springer-Verlag (traduction française : Raisonnements Divins), 2003.
Plusieurs jolis résultats et preuves sur les graphes.
- Four Colours Suffice, R. Wilson. Penguin, 2003.
L'histoire du théorème des 4 couleurs.