2. Diplômes
3. Diplôme ingénieur ISIMA (statut apprenti)
4. 1ère année
5. Semestre 6
6. Tronc commun
7. UE-Maths-Appli---S6
8. Théorie des graphes

Théorie des graphes

Objectifs

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

Plan du cours

1. Introduction, vocabulaire, notions de bases sur les graphes orientés et non orientés, représentation d’un graphe en machine.
2. Théorème de caractérisation des arbres et des éléments de preuve.
3. DFS : parcours en profondeur et applications et quelques unes de ses applications (dont le tri topologique d’un graphe sans circuit).
4. BFS : parcours en profondeur et les distances dans les graphes non pondérés.
5. Calculs de distances dans les graphes pondérés : Dijkstra, Bellman-Ford ; méthodes et limites (cas des poids négatifs). 
6. Algorithmes gloutons (Prim, Kruskal) pour le problème de l’arbre de point minimum (éléments de preuves de correction).
7. 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.
8. Chemins Eulériens, graphes planaires, chemins/cycles Hamiltoniens. Présentation informelle de la NP-complétude et de ses conséquences pratiques.
9. Introductions aux flots maximaux

Description des TP

A remplir

Connaissances requises

Aucune. 

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).