# Ope. Res. : Graph theory

Contenus

## Graph theory course

This course presents some graph theory algorithms like spanning trees, shortest path problems and flow problems. 🔗 project 1 🔗 project 2 🔗 SYLLABUS MARKS http://graphonline.ru/en/ Session / Timeline Tutorial / Oral exam Idea / Concept Video none none 🔗 Decision making / motivation 1 🔗 Tutorial 1 Complexity → 🔗 Big oh notation 🔗 → 🔗 Termination and correctness 🔗 2 🔗 Tutorial 2 Graph theory's basics → 🔗 A / directed graph → Degree → Path / cycle → Complete graph 🔗 → Subgraph → 🔗 Tree 3 🔗 Tutorial 3 → 🔗 Eulerian circuit 🔗 → Hamiltonian circuit 🔗 → 🔗 Graph coloring 🔗 4 🔗 Tutorial 4 Spanning tree → 🔗 Kruskal's algorithm 🔗 → Prim's algorithm 🔗 End of project 1 how to solve: 🔗 5 & 6 🔗 Tutorial 5 Shortest path problem → 🔗 Linear program 🔗 → Dynamic program 🔗 → 🔗 Dijkstra's algorithm 🔗 → 🔗 DAG algorithm 🔗 → 🔗 Bellman-Ford's algorithm 🔗 → 🔗 Floyd-Warshall's algorithm 🔗 how to solve: 🔗 7 & 8 🔗 Tutorial 6 Flow problem → 🔗 Max flow problem 🔗 → Flows and cut ˄ → Augmenting path ˄ → Min cut problem ˄ → 🔗 Ford-Fulkerson's algorithm 🔗 how to solve: 🔗 9 & 10 🔗 Tutorial 7 Transportation problem → 🔗 Definition and special cases 🔗 → Initial solution 🔗 → 🔗 Stepping stone algorithm → Degeneracy End of project 2 how to solve: 🔗 REFERENCES Introduction to Algorithms: Cormen, T and Leiserson, C The Algorithm Design Manual: Steven S. Skiena Electric Power System Applications of Optimization, Second Edition: James A. Momoh FR FR EN ES