---

Module Graphes et Structures, HMIN223

M1 Informatique, M1 Math/Info

Annee 2018/2019

---

    Infos pratiques:

• Attention, la page migre vers le moodle du cours...
• Contenu: Théorie et algorithmique des graphes, exemples d'applications.
• Horaires: Cours, td le lundi matin de 8h00 à 13h00. Début des cours le lundi 21 janvier. Pas cours le 4 Février...
• Volume: 11 Cours et 22 TD.
• Responsable S. Bessy

    Plan du cours:

• Chap. 1: Généralités, rappels.
• Chap. 2: Couplage.
• Chap. 3: Flots.
• Chap. 4: Connectivité.
• Chap. 5: Coloration: sommets, arêtes.
• Chap. 6: Deux classes de graphes: graphes planaires et graphes chordaux.
• Chap. 7: Applications.

    Planning:

Planning du semestre

    Notes de cours:

Notes de Cours

    Fiches de TD:

Fiche 1       Fiche 2       Fiche 3       Fiche 4

    Contrôle de connaisances:

• Contrôle continu: pour 30% de la note finale (avec règle du max). Contrôle sur table + devoirs à rendre + ...
• Contrôle terminal: pour 70% de la note finale (avec règle du max).

    Bibliographie et pré-requis:

Le cours s'appuyera principalement sur les ouvrages [2] et [3].

• [1] Introduction à l'algorithmique (2ème édition). T. Cormen, C. Leiserson, R. Rivest, C. Stein. Dunod éditeur.
• [2] Graph Theory. J.A. Bondy, U.S.R. Murty. Springer.
  Version française, traduit et mis à disposition par F. Havet.
• [3] Graph Theory (3rd edition). R. Diestel. Springer.
  édition électronique, accessible librement.
• [4] Proof from the book (4th edition). M. Aigner, G. Ziegler, K. Hofmann. Springer.
• [5] Algorithm Design. J. Kleinberg, E. Tardos. Pearson International Edition.

• Prérequis :
  - Généralités sur les graphes (on trouvera des infos dans chap. 1 et 2 de [2] ou chap. 1 de [3]).
  - Connexité, arbres (voir chap. 3 et 4 de [2] ou chap. 1 de [3]).
  - Parcours (voir chap. 6 de [2] ou chap. 23 de [1]).
  - Calculs de distance (voir chap. 6 de [2] ou chap. 25 et 26 de [1]).
  - Complexité d'algorithmes et Np complétude (voir chap. 8 de [2] ou chap. 33 de [1]).