Graphes

Après une introduction aux graphes (définitions, représentation en mémoire, parcours, chemins et arbres), le cours étudie des problèmes qui admettent une solution algorithmique efficace : arbre couvrant minimal, plus courts chemins, flot maximal et couplage maximum. L'étude de ces algorithmes fait apparaître des propriétés classiques de la théorie des graphes. Les notes s'appuient sur le polycopié de Denis Lapoire et sur les cours intégrés de Nicolas Hanusse. Un devoir maison, réalisé en groupe, simule la propagation du Covid-19 sur différentes familles de graphes.

Notes de cours

Cours8 pages

• Définitions généralesDéfinitions de base de la théorie des graphes : graphes orientés et non orientés, degrés, planarité, isomorphisme, graphe partiel, sous-graphe, union et quotient.
• Représentation des graphesReprésentation des graphes en mémoire : tableaux de listes d'adjacence et matrice d'adjacence, avantages et inconvénients.
• Algorithmes de parcoursParcours en largeur (BFS) et en profondeur (DFS) d'un graphe, détection de cycles et tri topologique.
• Chemins et arbresChemins, concaténation, distance, cycles, graphes acycliques, arborescences et arbres, avec un lexique des familles de graphes usuelles.
• Arbre couvrant minimalProblème de l'arbre couvrant minimal : coupures, algorithme générique, algorithmes de Kruskal et de Prim.
• Plus court cheminPlus courts chemins dans un graphe orienté pondéré : relâchement, algorithme de Bellman-Ford (poids négatifs, détection de cycle absorbant) et algorithme de Dijkstra.
• Flot maximalFlot maximal dans un réseau : réseau résiduel, chemins améliorants, théorème flot maximal / coupe minimale, algorithmes de Ford-Fulkerson et d'Edmonds-Karp, théorèmes de Menger.
• CouplageProblème du couplage maximum : chemins alternés augmentants, théorème de Berge, arbres alternés et contraction des orbites (fleurs).

Travaux dirigés7 pages

• TD 1 : notions généralesLemme des poignées de main, degrés, graphe de Petersen, dénombrement de graphes et test d'isomorphisme.
• TD 2 : implémentation de graphesImplémentation des primitives usuelles d'un graphe (adjacence, degré, liste des voisins) par matrice d'adjacence et par listes d'adjacence.
• TD 3 : parcours en largeur et en profondeurApplications des parcours de graphes : test de biparticité par 2-coloration et sortie d'un labyrinthe par l'algorithme de Trémaux.
• TD 4 : Union-FindStructure Union-Find pour les ensembles disjoints : version naïve, forêt avec union par rang, preuve de la borne logarithmique sur la hauteur.
• TD 5 : cycles et voyageur de commerceCycles hamiltoniens et problème du voyageur de commerce : force brute avec l'algorithme de Heap, programmation dynamique de Held-Karp, théorème de Dirac et 2-approximation par arbre couvrant minimal.
• TD 6 : flot maximalDécider si un flot est maximal et intégralité du flot maximal dans un réseau à capacités entières.
• Devoir maison : propagation du Covid-19Simulation de la propagation du Covid-19 sur des graphes circulaires, aléatoires et mixtes, stratégies de tests et de confinement, modèle SIR et recherche de chemin A*.

Ressources

Support de l'enseignant (Moodle)1 document

• Polycopié du cours

Exercices1 document

• Feuille d'exercices