Ope. Res. : Graph theory

Contents

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