-
Diplômes
-
Licence informatique
-
Licence 3
-
Semestre 5
-
TC
-
Theorie-des-graphes
-
Algorithmes d'optimisation sur les graphes
Algorithmes d'optimisation sur les graphes
Objectifs
L'objectif de cette partie est de se familiariser avec
les problèmes d'optmisisation et leurs résolutions par
des algorithmes polynomiaux.
Plan du cours
- Plus courts chemin à source unique
- Définitions et propriétés
- Algorithme de Dijkstra
- Algorithme de Bellman
- Arbres couvrants de poids minimum
- Méta algorithme de Tarjan (Règles rouges et bleues)
- Algorithmique de Kruskal
- Algorithme de Prim
- Flots maximum dans les réseaux
- Notion de chemin améliorant
- Condition nécéssaire et suffisante
- Algorithme Ford-Fulkerson
- Algorithme Edmonds-Karp
- Coloration dans les graphes
- Définition et bones inférieures et supérieures
- Heuristique Gloutonne
- Théorème de Brooks
- Coloration d'arêtes
- Vizing pour les graphes bipartis
Description des TP
A remplir
Connaissances requises
A remplir
RSE (Responsabilité Sociale et Environnementale)
Bibliographie
A remplir