Algorithmique des graphes

Les graphes sont un objet mathématique qui dispose de très nombreuses applications dans presque tous les domaines. Dans ce cours, nous présentons les concepts généraux (graphe orienté, graphe non-orient, graphe valué, degré, chemin, cycle, fermeture, connexité, isomorphisme, clique, stable, coloration…), quelques classes de graphe spécifique (planaire, biparti, complet) et des algorithmes pour trois problèmes classiques d’optimisation (plus court chemin, arbre couvrant minimum et flot-maximum).