Graphes

Objectifs

L'étudiant doit maîtriser les concepts et les principaux résultats de la théorie des graphes et être capable de les appliquer à des situations et problèmes de la vie courante. Il est capable de programmer et de tester des algorithmes classiques de la théorie des graphes, tels que les circuits d'Euler, le plus court chemin de Diskjstra, le coloriage de Welsh-Powell, etc.

Description

Chapitre 1 : Définitions et concepts de base

Chapitre 2 : Connexité dans les graphes

Chapitre 3 : Graphes eulériens, graphes hamiltoniens

Chapitre 4 : Parcours de graphe

Chapitre 5 : Planarité et coloration de graphes

Chaque chapitre sera étudié en groupe de TD où seront alternés le cours et les exercices.

Les 5 TP seront principalement consacrés au projet.

Bibliographie

Gondran, Michel, and Michel Minoux. Graphs and algorithms. Wiley, 1984

Alain Bretto, Alain Faisant, François Hennecart. Eléments de théorie des graphes. Lavoisier Hermes 2018 2e édition revue et augmentée.

Pré-requis nécessaires

Programmation en OCaml

Session 1 ou session unique - Contrôle des connaissances

Session 2 - Contrôle des connaissances