# VTG Graph Theory

course | grade | year | semester | branch |

VTG | 2 | 2 | winter | Applied Computer Science and Control |

VTG | 2 | 2 | winter | Applied Computer Science and Control (P) |

VTG-A | 2 | 1 | winter | Mechanical Engineering |

VTG-A | 2 | 2 | winter | Applied Computer Science and Control |

VTG-K | 2 | 2 | winter | Applied Computer Science and Control |

VTG-K | 2 | 2 | winter | Applied Computer Science and Control (P) |

## Supervisor

prof. RNDr. Ing. Miloš Šeda, Ph.D.## Annotation

The course provides an introduction to graph theory and familiarises students with basic terms. It deals with the following topics: Graph representation. Time complexity of algorithms. Data structures (binary heap, disjoint sets, ...). Eulearian trails, Hamiltonian paths. Breadth-first searching, depth-first searching, backtracking, branch and bound method. Connectivity and reachability. Shortest path problems (Dijkstra's algorithm, Floyd-Warshall algorithm). Network graphs. Trees, spanning tree problem, Steiner tree problems. Fundamentals of computational geometry, Voronoi diagrams, Delaunay triangulation. Network flows. Graph colouring. Graph matching.