|
Lecturer(s)
|
|
|
|
Course content
|
1. Basic notions of graph theory (graphs and subgraphs, trails, walks, paths, connectivity, special clases of graphs, vertex degree, degree sequences in graphs). 2. Trees (characterization of trees, spanning tree of a graph, problem of minimal spanning tree). 3.Vertex and edge connectivity in graphs (measures of graph connectivity, bridges, cut-vertex and 2-connected graphs, Menger's theorems). 4. Eulerian and Hamiltonian graphs (Eulerian graphs and their characterization, results related to Hamiltonian graphs). 5. Graph colorings (vertex and edge colorings of graphs, lower and upper bounds for chromatic numbers). 6. Planar graphs (Euler's formula and its consequences, Platonic solids, characterization of planar graphs, coloring of planar graphs). 7. Embeddings of graphs on two dimensional surfaces (genus of a surface, some examples of embeddings of graphs on surfaces with different genus).
|
|
Learning activities and teaching methods
|
|
Monologic Lecture(Interpretation, Training)
|
|
Learning outcomes
|
The main aim is to become familiar with basic concepts and techniques used in graph theory.
1. Knowledge Students define the basic notions of graph theory, investigate their properties and relationships between them.
|
|
Prerequisites
|
Elementary knowledge of finite sets is assumed.
|
|
Assessment methods and criteria
|
Oral exam, Written exam
The student must be able to understand the basic concepts and be able to solve practical tasks.
|
|
Recommended literature
|
-
A.Bodny,R.M.Murty. (2008). Graph Theory. Springer London.
-
Chajda I. (2000). Vybrané kapitoly z algebry. PřF UP Olomouc.
-
J. Matoušek, J. Nešetřil. (2002). Kapitoly z diskrétní matematiky. Karolinum.
-
J.Demel. (2002). Grafy a jejich apliakce. Academia.
-
Korte B., Vygen J. (2018). Combinatorial Optimization (Theory and Algorithms). Springer.
-
R. Disestel. (2017). Graph Theory. Springer-Verlag Berlin Heidelberg.
|