EN
Home / Fields of study / Courses / Graph Algorithms

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

  1. Graphs – graph definition and its basic properties, representation of graphs in computer memory.
  2. Trees – definition of tree and its basic properties, isomorfism of trees.
  3. Graph search - search through a graph, depth first search and breath first search, search for a shortest path (Dijsktra algorithm).
  4. Minimal spanning tree - Kruskal algorithm, Jarník algorithm and Borůvka algorithm.
  5. Graph coloring - introducing graph coloring problem, inexact algorithms for graph coloring: naive, Welsh-Powell, DSATUR and RLF.
  6. 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.