Théorie des graphes - Cours de recherche 2010/2011
Master d'Informatique Fondamentale - ENS Lyon

Cours : Eric Thierry + participation de Christophe Crespelle

Présentation

Cours avancé de théorie des graphes, accessible à tout étudiant ayant des connnaissances de bases sur les graphes et en algorithmique. Pour se faire une idée, un bonne recommandation est la lecture des chapitres sur les graphes du livre Introduction à l'algorithmique de Cormen, Leiserson, Rivest, Stein. 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 sujet, 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. Le calcul 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 DES SUJETS, ainsi qu'une date pour l'exposer (environ 15 min exposé + 5 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, envoyez-moi un email pour fixer le sujet et la date. Envoyez-moi aussi ensuite 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 15mn et est suivi d'une séance de questions (environ 5mn). Ne dépassez en aucun cas 20mn tout compris, répétez avant pour connaître la durée de votre exposé

Planning indicatif 2010

Le cours a lieu le mercredi de 8h à 10h en salle A1 (4ème étage, ENS Sciences).

Planning des exposés

Bibliographie

• Introduction to graph theory. D. West. Prentice Hall, 2000.
  Excellent livre de base.
• Digraphs: Theory, Algorithms and Applications. J. Bang-Jensen et G. Gutin. Springer-Verlag, 2000.
  Excellent livre de base sur les graphes orientés. Livre en 1ère édition téléchargeable ici.
• Introduction to Algorithms. T. Cormen, C. Leiserson, R. Rivest et C. Stein. Mcgraw-Hill (ou Dunod pour la traduction française), 2001.
  Une bible de l'algorithmique, avec plusieurs chapitres sur l'algorithmique de graphes.
• Algorithm Design. J. Kleinberg, E. Tardos. Addison Wesley, 2005.
  Un autre excellent livre généraliste en algorithmique, avec des chapitres sur les graphes.
• The Design and Analysis of Computer Algorithms. A. Aho, J. Hopcroft et J. Ullman. Addison Wesley, 1974.
  Plusieurs chapitres sur l'algorithmique de graphes, avec des algorithmes non traités ailleurs.
• Combinatorial Optimization. C. Papadimitriou, K. Steiglitz. Dover, 1998.
  Une référence en optimisation combinatoire, avec une bonne introduction à la programmation linéaire.
• Modern Graph Theory. B. Bollobas. Springer-Verlag, 1998.
  Plus pointu que le West sur certains chapitres (graphes extrémaux, graphes aléatoires ...).
• Graph Theory, R. Diestel. Springer-Verlag, 2nd ed., 2000.
  Plus pointu que le West sur certains chapitres (graphes extrémaux, graphes infinis, théorie des mineurs ...). Livre téléchargeable ici.
• 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.
  Une synthèse de 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 (des erreurs dans certaines 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.
  Attention, il reste quelques erreurs et typos. Téléchargeable ici
• CATBox - An Interactive Course in Combinatorial Optimization. W. Hochstattler, A. Schliep.
  Un bon outil d'animation d'algorithmes de graphes. Téléchargeable ici