Contents

Toggle## 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 |