Graphs and Optimization This module introduces fundamental concepts in graph theory, shortest path problems, and linear programming, providing both theoretical foundations and practical algorithms.
Chapter 1: Graph Theory Covers the basics of graphs, including terminology, degrees, subgraphs, cycles, and circuits. Different graph representations are studied, along with the graph coloring problem.
Chapter 2: Shortest Path Focuses on valued graphs and shortest path problems. Key algorithms include Dijkstra’s and Floyd’s for shortest paths, as well as Kruskal’s and Prim’s algorithms for constructing minimum spanning trees.
Chapter 3: Linear Programming Introduces optimization through linear programming. Topics include problem formulation, geometric interpretation, the simplex method, and duality, with applications to real-world optimization problems.
- Enseignant: Khalil Zahmoul