Terms for 2017
September, 5
Admission Interviews
September, 7
Open Day
September, 12
Admission Interviews
September, 14
Open Day
Full list of terms
Graph Algorithms
This course follows freely topics from subjects Essentials of Algorithm Design and Optimalization and Mathematical Methods 2. It is however not completely dependent and most of the parts are started from the very begining. The main topic is Graph Theory with emphasis to represents graphs in computer memory and performing basic algorithms with these. Examples of these algorithms are graph search (depth first and breath first) as well as shortest path algorithm and searching for a spanning tree. The task of the subject is to provide necessary knowledge for implementing these algorithms using language Ruby and show several features that can be used in practical algorithms.
What are you going to learn
-
Graphs – graph definition and its basic properties, representation of graphs in computer memory.
-
Trees – definition of tree and its basic properties, isomorfism of trees.
-
Graph search - search through a graph, depth first search and breath first search, search for a shortest path (Dijsktra algorithm).
-
Minimal spanning tree - Kruskal algorithm, Jarník algorithm and Borůvka algorithm.
-
Graph coloring - introducing graph coloring problem, inexact algorithms for graph coloring: naive, Welsh-Powell, DSATUR and RLF.
-
Oriented graphs - basic definition and its properties, topological sort.
How the course is organized
Full time study
The course consists of 6 lectures and 6 workshops, each lasting 1,5 hours.
Part time study
The course is taught only in full time study form for part time students.
Recommended literature
-
DIESTEL, R.: Graph Theory, 4th edition, Springer, 2012.
-
BOLLOBÁS, B.: Modern Graph Theory, Corrected Edition, Springer, 2013.