Contents
ToggleGraph 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 |