Théorie des graphes

Objectifs

Maitriser les notions théoriques et les algorithmiques classiques de graphes.

Savoir utiliser ces notions et méthodes pour la modélisation de situations simples.

Plan du cours

Introduction, vocabulaire, notions de bases sur les graphes orientés et non orientés, représentation d’un graphe en machine.
Théorème de caractérisation des arbres et des éléments de preuve.
DFS : parcours en profondeur et applications et quelques unes de ses applications (dont le tri topologique d’un graphe sans circuit).
BFS : parcours en profondeur et les distances dans les graphes non pondérés.
Calculs de distances dans les graphes pondérés : Dijkstra, Bellman-Ford ; méthodes et limites (cas des poids négatifs).
Algorithmes gloutons (Prim, Kruskal) pour le problème de l’arbre de point minimum (éléments de preuves de correction).
Ordonnancements d’un graphe de tâches avec contraintes de précédence : algorithmes pour déterminer les dates aux plus tôt, dates au plus tard, chemin critique.
Chemins Eulériens, graphes planaires, chemins/cycles Hamiltoniens. Présentation informelle de la NP-complétude et de ses conséquences pratiques.
Introductions aux flots maximaux :
1. réseau, capacités, flot, coupes, chaines améliorantes, algorithme de Ford et Fulkerson.
2. Présentation des résidus et algorithme d’étiquetage.
3. Résolution du problème du flot « faisable ».
4. Résolution du problème du flot canalisé.

Description des TP

A remplir

Connaissances requises

Aucune connaissances requises pour suivre cet enseignement.

RSE (Responsabilité Sociale et Environnementale)

Bibliographie

Pour la partie algorithmique : « Introduction à l’algorithmique » Cormen, Leiserson, Rivest, édition Dunod (ou toute version plus récente de cet ouvrage de référence).

Pour la partie structurelle on peut utiliser : « Graph Theory with applications » Bondy et Murty, North Holland (ou toute version plus récente de cet ouvrage).