Course detail

Theory of Graphs

FAST-HA53Acad. year: 2015/2016

Various types of graphs and their applications. Basic structures defined for graphs used for their classification. Tractable and intractable combinatorial problems as modelled by graphs. Essential algorithms used to solve graph problems. Theory of NP-completeness.

Language of instruction

Czech

Number of ECTS credits

2

Mode of study

Not applicable.

Guarantor

RNDr. Karel Mikulášek, Ph.D.

Department

Institute of Mathematics and Descriptive Geometry (MAT)

Learning outcomes of the course unit

Students will be acquainted with the basics of the theory of simple graphs, directed graphs, and multigraphs. They will get an understanding of the relationship between the planarity and colourability of a graph. They will be able to apply the basic methods to solving tractable combinatorial problems on graphs as well as the travelling salesman problem as a representative of intractable NP complete problems.

Prerequisites

Basics of combinatorics as taught at secondary schools. Symbol processing.

Co-requisites

Not applicable.

Planned learning activities and teaching methods

Not applicable.

Assesment methods and criteria linked to learning outcomes

Not applicable.

Course curriculum

Not applicable.

Work placements

Not applicable.

Aims

After the course, students should be acquainted with the basics of the theory of graphs. They should also be able to apply the knowledge acquired when dealing with problems they may come across as engineers or businessmen.

Specification of controlled education, way of implementation and compensation for absences

Extent and forms are specified by guarantor’s regulation updated for every academic year.

Recommended optional programme components

Not applicable.

Prerequisites and corequisites

Not applicable.

Basic literature

Nešetřil, J.: Teorie grafů. SNTL, 1978.
Gross, Y; Yellen, J: Graph Theory. CRC Press, 1999.

Recommended reading

Not applicable.

Classification of course in study plans

  • Programme N-P-C-GK Master's

    branch G , 1. year of study, summer semester, elective

Type of course unit

 

Exercise

26 hours, compulsory

Teacher / Lecturer

RNDr. Karel Mikulášek, Ph.D.