Une 1ère partie concerne les graphes valués.

Arbres couvrant de poids minimal : après l’étude de quelques règles concernant les cycles, les coupes, les arêtes de plus faible poids, ou de plus fort poids dans un cycle, sont décrits plusieurs algorithmes : Tarjan, Prim, Kursal, et Sollin (les schémas de preuve sont amenés). Nombreux exemples en TD.

Chemins de longueurs minimale : le principe d’optimalité de Bellman est décrit, permettant de présenter le principe d’élémentarité d’un chemin optimal. Trois idées permettant de scinder le chemin en sous chemins, permettent d’écrire le système d’équations auquel obéissent les longueurs optimales entre sommets. Trois algorithmes sont alors déduits de ces 3 conceptions. Nombreux exemples en TD.

Flots dans les réseaux : après avoir décrit le problème en terme de réseau, capacités, flots, et coupes, on s’intéresse à des chaînes augmentant le flot, avant de décliner le théorème du flot maximal/coupe minimale, en algorithme de Ford Fulkerson. Nombreux exemples en TD.

Une 2^ème partie, en fonction du temps, concerne les couplages et colorations de graphes.

À la fin de cette UE/EC, vous serez capable de :

• Après modélisation, de mettre en place un algorithme permettant d’obtenir un arbre couvrant de poids minimal
• Après modélisation, de mettre en place un algorithme de recherche de chemin le plus court
• Après modélisation, de mettre en place un algorithme de recherche de flot minimal.

L3 NEC : UE Théorie des graphes 1

Évaluation Continue Intégrale (ECI) 100%