Discrete Mathematics

Lecturer:

Tutor:

Supervisor:

Synopsis:

The subject of discrete mathematics is demonstrated on the elements of graph theory. The definitions, theorems, proofs, data structures and algorithms and their time complexity are included.

Requirements:

Basic knowledges from linear algebra.

Syllabus of lectures:

1.Subject of discrete mathematics.

2.Graph theory, undirected graph.

3.Basic graph types, isomorphism of graphs.

4.Paths, circles and cliques in graph.

5.Graph characteristics, vertex characteristics.

6.Connected graphs, vertex distance, metric space of vertices.

7.Matrix representation of undirected graph, Wilshaw and Floyd algorithm.

8.Euler and Hamiltonian graphs.

9.Planar graphs, chromatic number.

10.Tree, root tree, tree algorithms.

11.Heuristic and greedy algorithms.

12.Minimum spanning tree, Kruskal or Prim algorithm.

13.Optimum paths in graph.

Syllabus of tutorials:

1.Subject of discrete mathematics.

2.Graph theory, undirected graph.

3.Basic graph types, isomorphism of graphs.

4.Paths, circles and cliques in graph.

5.Graph characteristics, vertex characteristics.

6.Connected graphs, vertex distance, metric space of vertices.

7.Matrix representation of undirected graph, Wilshaw and Floyd algorithm.

8.Euler and Hamiltonian graphs.

9.Planar graphs, chromatic number.

10.Tree, root tree, tree algorithms.

11.Heuristic and greedy algorithms.

12.Minimum spanning tree, Kruskal or Prim algorithm.

13.Optimum paths in graph.

14.Traveling salesman problem.

Study Objective:

Knowledge:

Elements of graph theory, fields of application of graph theory, graph algorithms.

Abilities:

Solving of versatile spectrum of problems from graph theory

Study materials:

Compulsory literature:

[1] J. Matoušek, J. Nešetřil: Kapitoly z diskrétní matematiky, Karolinum, Praha, 2000.

[2] J. Nešetřil: Teorie grafů, SNTL, Praha, 1979.

Recommended literature:

[3] R. Diestel: Graph Theory, Springer Verlag, Berlin, 1996.

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: