Component
École Nationale Supérieure d'Électrotechnique d'Électronique d'Informatique d'Hydraulique et des Télécommunications
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.