Logo ČVUT
Loading...
CZECH TECHNICAL UNIVERSITY IN PRAGUE
STUDY PLANS
2011/2012

Introduction to Graph Theory B

Login to KOS for course enrollment Display time-table
Code Completion Credits Range Language
01ZTGB Z,ZK 4 2+2 Czech
Lecturer:
Petr Ambrož (gar.)
Tutor:
Petr Ambrož (gar.), František Jahoda
Supervisor:
Department of Mathematics
Synopsis:

The course provides an explanation of modern graph theory, applications and algorithms are discussed.

Requirements:
Syllabus of lectures:

1) Basic notion of graph theory

2) Connectivity

3) Bipartite graphs

4) Forests and trees

5) Spanning tree, minimal spanning tree

6) Euler cycles and Hamilton circles

7) Maximal and perfect matching

8) Edge colouring

9) Flows in networks

10) Vertex colouring

11) Planar graphs

Syllabus of tutorials:

1) Depth-first and breadth-first search

2) Shortest path in a graph (Dijkstra, A*, Floyd-Warhsall)

3) Minimal spannig thee (Kruskal algoritm)

4) Maximal flow in a network (Ford-Fulkerson)

5) Maximál matching (Edmonds algoritm)

6) Planarity algorithm

Study Objective:

Knowledge:

Notions of graph theory, their basic properties and mutual relations. Graph algorithms.

Abilities:

Application of the theory in modelling and solving of particular questions and tasks, including computer implementation.

Study materials:

References:

[1] J.A. Bondy, U.S.R. Murty. Graph theory.

Graduate Texts in Mathematics 244. Springer, New York, (2008).

Recommended references:

[2] J. Matoušek and J. Nešetřil. Kapitoly z diskrétní matematiky. MatfyzPress,

1996.

[3] Ján Plesník. Grafové algoritmy.

Veda, Bratislava, (1983).

Teaching tools:

Computer lab (Windows/Unix) with Python and C++.

Note:
Time-table for winter semester 2011/2012:
Time-table is not available yet
Time-table for summer semester 2011/2012:
Time-table is not available yet
The course is a part of the following study plans:
Generated on 2012-7-9
For updated information see http://bilakniha.cvut.cz/en/predmet24524605.html