|
Lecturer(s)
|
|
|
|
Course content
|
1. Basic notions of graph theory: graph, subgraph, important classes of graphs, walks, trails and paths, connectivity, degree sequences. 2. Trees: characterization of trees, spanning tree and the problem of the minimal spanning tree. 3. Eulerian and Hamiltonian graphs: Eulerian graphs and their characterization, sufficient conditions for Hamiltonian graphs. 4. Graph colorings: vertex coloring, edge coloring, generalized colorings, bounds for chromatic invariants. 5. Planar graphs: Euler's formula and its consequences, Platonic solids, characterization of planar graphs, vertex coloring of planar graphs. 6. Planar graphs: Euler's formula and its consequences, Platonic solids, characterization of planar graphs, vertex coloring of planar graphs. 7. The shortest path problem in digraphs: Dijkstra's algorithm. 8. Selected problems in graph theory: matchings in bipartite graphs, extremal combinatorics, Ramsey numbers and their estimations.
|
|
Learning activities and teaching methods
|
|
Monologic Lecture(Interpretation, Training)
|
|
Learning outcomes
|
The aim is to become familiar with basic concepts, statements and applications in graph theory.
1. Knowledge Acquisition of basic knowledge in graph theory.
|
|
Prerequisites
|
Elementary knowledge of finite sets is assumed.
|
|
Assessment methods and criteria
|
Oral exam
Credit: active demonstration of knowledge. Exam: understanding of the subject, proofs of the main statements.
|
|
Recommended literature
|
-
Demel, Jiří. (2002). Grafy a jejich aplikace. Academia.
-
Diestel, Reinhard. (2017). Graph Theory 5th ed.
-
Chartrand G., Zhang. P. (2012). A First Course in Graph Theory. Dover Publications.
-
J.A. Bondy, U.S.R. Murty. (2008). Graph Theory. Springer.
-
Jiří Matoušek, Jaroslav Nešetřil. (2000). Kapitoly z diskrétní matematiky. Praha.
|