• Brno University of Technology - Centre of Sports Activities
  • Research centres

  • Pravděpodobně máte vypnutý JavaScript. Některé funkce portálu nebudou funkční.

Course detail

Graphs and Algorithms

Course unit code: FSI-SGA-A
Academic year: 2016/2017
Type of course unit: compulsory
Level of course unit: Master's (2nd cycle)
Year of study: 1
Semester: winter
Number of ECTS credits:
Learning outcomes of the course unit:
The students will be made familiar with the basics of the theory of graphs and graph algorithms.
This will provide them with tools for using graphs to model various practical problems, which may then be solved by using the graph algorithms.
Mode of delivery:
90 % face-to-face, 10 % distance learning
Prerequisites:
Students are expected to have secondary school knowledge of set theory and combinatorics.
Co-requisites:
Not applicable.
Recommended optional programme components:
Not applicable.
Course contents (annotation):
The course will provide students with basic concepts of the theory of graphs and with some algorithms based on that theory. After the basic definitions, the classic problems will be discussed including the Euler path and Hamilton cycle of a graph, vertex colouring, planar graphs etc. The next concept to be investigated will be trees and tree-based algorithms. Attention will also be paid to the problem of finding the shortest path in a graph. Students will also learn about bipartite graphs and matching problems. Oriented graphs will be introduced to build networks and flows in them and deal with algorithms used to find a critical path. The course will be oriented towards applications of graphs that can be found in many areas of practical life. Emphasis will be placed on applications in computer science, optimization and theory of control and in operation research.
Recommended or required reading:
Biggs, N.L.: Discrete Mathematics, Oxford Science Publications 1999
Plesník, J.: Grafové algoritmy, Veda, Bratislava 1983
Wallis, W.D.: A Beginner's Guide to Graph Theory, Birkhäuser Boston 2000
Willson, J.R., Watkins, J.J.: Graphs: An Introductory Approach, Wiley 1990
Balakrishnan, V.K.: Introductory Discrete Mathematics, Dover Publications, Inc., New York 1996
Piff, M.: Discrete Mathematics, An Introduction for Software Engineers, Cambridge University Press 1991
Plesník, J.: Grafové algoritmy, Veda, Bratislava 1983
Willson, J.R., Watkins, J.J.: Graphs: An Introductory Approach, Wiley 1990
Planned learning activities and teaching methods:
The course is taught through lectures explaining the basic principles and theory of the discipline. Exercises are focused on practical topics presented in lectures.
Assesment methods and criteria linked to learning outcomes:
The course unit credit is awarded on condition of having attended the seminars actively and passed a written test. The exam has a written and an oral part. The written part tests student's ability to deal with various problems using the knowledge and skills acquired in the course. In the oral part, the student has ro prove that he or she has mastered the related theory.
Language of instruction:
English
Work placements:
Not applicable.
Course curriculum:
Not applicable.
Aims:
The course aims to acquaint the students with the theory of graphs and graph-based algorithms, which are commonly used to solve problems in engineering and other areas.
Specification of controlled education, way of implementation and compensation for absences:
Since the attendance at seminars is required, it will be checked systematically by the teacher supervising the seminar. If a student misses a seminar, an excused absence can be cpmpensated for via make-up topics of exercises.

Type of course unit:

Lecture: 26 hours, optionally
Teacher / Lecturer: RNDr. Karel Mikulášek, Ph.D.
Syllabus: 1. Basic concepts
2. Paths and cycles
3. Colouring of vertices
4. Trees
5. Sorting algorithms
6. Spanning trees
7. The shortest path problem
8. Bipartite graphs
9.Colouring of edges
10.Matching
11.Directed graphs
12.The critical path problem
13.Flows in networks
seminars: 13 hours, compulsory
Teacher / Lecturer: RNDr. Karel Mikulášek, Ph.D.
Syllabus: Seminars will closely follow the lectures.

The study programmes with the given course