Théorie
des graphes - Cours de Recherche
Master
d'Informatique Fondamentale - ENS Lyon
Présentation
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èmes et algorithmes de décomposition,
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.
Evaluation
Après les premières séances de cours, une liste de
sujets de synthèse sera proposée. Votre contribution
consistera à rédiger un court mémoire sur l'un de
ces sujets, puis à le présenter à l'oral.
D'autre part, un examen aura lieu la dernière semaine. Il
portera sur l'ensemble du cours et pourra aussi faire intervenir des
notions présentées pendant les différents
exposés. La répartition de la note finale du cours sera
grosso modo 2/3 sujet de synthèse + 1/3 examen.
Sujets de
synthèse
Vous devez chacun choisir un sujet différent dans la liste
proposée (ICI
!), ainsi qu'une date pour l'exposer (environ 20 min
+ questions), et écrire un court mémoire sur ce sujet.
Vous devez également relire le mémoire de deux autres
étudiants et écrire une petite fiche de lecture. Une fois votre
choix fait, inscrivez-vous sur le planning 2008/2009
pour fixer le sujet, la date et les sujets dont vous souhaitez
être relecteurs !
Les sujets de synthèse proposés peuvent faire appel
à différents documents (articles, livres, exercices)
ainsi que vos propres preuves ou algos ! Vous avez une certaine
liberté pour aborder chaque sujet du moment que vous
répondez à la question centrale. Des pistes sont
proposées, vous n'êtes pas obligés de les suivre
toutes. La liste des documents suggérés n'est bien
sûr pas exhaustive. Le mémoire doit faire entre environ 10
et 15 pages (figures non comprises). Une exigence est qu'il doit
présenter au moins un
théorème avec sa preuve et/ou un algorithme avec son
analyse.
N'hésitez surtout pas à me contacter si vous avez des
questions sur le contenu d'un sujet ou sur les documents qui vous sont
nécessaires. En particulier, si vous n'arrivez pas à
récupérer des articles ou si des livres ne sont plus
disponibles à la bibliothèque, dites-le moi.
Le cours précédent celui de l'exposé
(généralement la semaine précédente),
l'étudiant donne trois exemplaires de son rapport : à moi
et aux deux relecteurs. Chaque relecteur fait une fiche critique de
relecture (1 ou 2 pages maxi) et me la donne avant l'exposé. Si
cela vous intéresse, jetez un coup d'oeil au guide du relecteur par Ian Parberry
(un peu surdimensionné par rapport à notre exercice) : A Guide for New Referees.
Les relecteurs posent également des questions à celui qui
expose. L'exposé dure environ 20mn et est suivi d'une
séance de questions (environ 10mn). Ne dépassez en aucun cas 30mn tout
compris, répétez avant pour connaître la
durée de votre exposé
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 ...)
- Graph Theory, A. Bondy, U. Murty.
Graduate Texts in Mathematics 244, Springer, 2008 (2nd ed.).
Généraliste avec des bonnes fiches sur les raisonnements typiques.
- Algorithmic Graph Theory and Perfect
Graphs, M. Golumbic.
Academic Press, 1980 (1st ed.). Annals of Discrete Mathematics, 2004 (2nd ed.).
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.
- Poly de
Vincent Bouchitté. Cours de L3 (quelques erreurs et
typos). ICI
Me contacter
THIERRY Eric, bureau A4 à l'IXXI (Institut des Systèmes
Complexes, comment
venir ?)
Email: eric.thierry@ens-lyon.fr