Théorie des graphes
Objectives
To discover basic concepts and methods of graph theory from a family of practical problems. At the end of the lecture, the student must discover ten important problems and appropriate algorithms.
Description
· Basic objects
· Shortest path: Moore-Dijkstra and Ford algorithms.
· Scheduling: PER analysis
· Hamiltonian paths: Demoucron and Kaufman methods - Malgrange
· Eulerian paths
· Maximum flows: Ford-Fulkerson algorithm
· Optimal assignments: Hungarian method
· Properties relating to cycles, trees , Spanning trees with optimal weight: Kruskal's algorithm
· Graph coloring, planar graphs: Euler's formula.
Bibliography
Graphs and hypergraphs - Author: Claude Berge - Publisher: Dunod, 1975
Graphs and Algorithms - Author: Michel Gondran and Michel Minoux - Editor: Eyrolles, 1980
Session 1 ou session unique - Contrôle des connaissances
Modalité | Nature | Coefficient | Remarques |
---|---|---|---|
CT (contrôle terminal) | Oral/Ecrit | 100% | Examen Théorie des Graphes |
Session 2 - Contrôle des connaissances
Modalité | Nature | Coefficient | Remarques |
---|---|---|---|
CT (contrôle terminal) | Oral/Ecrit | 100% | Examen Théorie des Graphes |