Course Unit Code | 470-4302/01 |
---|
Number of ECTS Credits Allocated | 6 ECTS credits |
---|
Type of Course Unit * | Choice-compulsory type B |
---|
Level of Course Unit * | Second Cycle |
---|
Year of Study * | |
---|
Semester when the Course Unit is delivered | Summer Semester |
---|
Mode of Delivery | Face-to-face |
---|
Language of Instruction | Czech |
---|
Prerequisites and Co-Requisites | Course succeeds to compulsory courses of previous semester |
---|
Name of Lecturer(s) | Personal ID | Name |
---|
| KOV16 | doc. Mgr. Petr Kovář, Ph.D. |
Summary |
---|
The course covers both basic and advanced topics of Graph Theory, often overlapping with other branches of mathematics (algebra, combinatorics).
A mandatory part of the course is one or sometimes two projects focused on real life problems that are solved using methods of graph theory.
|
Learning Outcomes of the Course Unit |
---|
Each student is supposed to
- analyze real life problems
- express them as a graph theory problem
- solve the problem using graph theory methods
- give an interpretation of the theoretical results in the terms of the original problems
At the same time he should decide what are the limits of an ideal theoretical solution in contrast to the real situation.
|
Course Contents |
---|
Lectures and discussions
- Graphs, simple graphs. Incidence matrix and adjacency matrix. Subgraphs. Degree of a vertex.
- Paths and cycles.
- Trees, bridges and cuts.
- Graph isomorphisms.
- Connectivity and blocks. Cut sets.
- Matching and covers in general and bipartite graphs. Perfect matchings.
- Edge colorings. Chromatic index, Vizing's Theorem.
- Vertex colorings, Chromatic number, Brook's Theorem.
- Planar graphs. Dual graphs, Euler's formula for connected planar graphs, Kuratowski's Theorem. Four Color Theorem.
- Non-planar graph, measures of non-planarity.
- Eulerian and Hamiltonian graphs.
- Oriented graphs. Oriented paths and cycles.
- Tournaments and graph models
|
Recommended or Required Reading |
---|
Required Reading: |
---|
J. Matoušek, J. Nešetřil, Chapters in Discrete Mathematics, Karolinum Praha (2010). |
P. Kovář: Teorie grafů, VŠB (2011)
J. Matoušek, J. Nešetřil, Kapitoly z diskrétní matematiky, Karolinum Praha (2010).
|
Recommended Reading: |
---|
D. B. West, Introduction to graph theory, Prentice-Hall, Upper Saddle River NJ, (2019), ISBN 9780131437371. |
D. B. West, Introduction to graph theory, Prentice-Hall, Upper Saddle River NJ, (2019), ISBN 9780131437371. |
Planned learning activities and teaching methods |
---|
Lectures, Individual consultations, Tutorials, Project work |
Assesment methods and criteria |
---|
Task Title | Task Type | Maximum Number of Points (Act. for Subtasks) | Minimum Number of Points for Task Passing |
---|
Exercises evaluation and Examination | Credit and Examination | 100 (100) | 51 |
Exercises evaluation | Credit | 20 (20) | 10 |
Project | Project | 20 | 10 |
Examination | Examination | 80 (80) | 41 |
Written part | Written examination | 60 | 30 |
Theoretical part | Oral examination | 20 | 5 |