470-4302/02 – Graph Theory (TG)
| Gurantor department | Department of Applied Mathematics | Credits | 6 |
| Subject guarantor | doc. Mgr. Petr Kovář, Ph.D. | Subject version guarantor | doc. Mgr. Petr Kovář, Ph.D. |
| Study level | undergraduate or graduate | Requirement | Optional |
| Year | | Semester | summer |
| | Study language | English |
| Year of introduction | 2015/2016 | Year of cancellation | |
| Intended for the faculties | FEI | Intended for study types | Follow-up Master |
Subject aims expressed by acquired skills and competences
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.
Teaching methods
Lectures
Individual consultations
Tutorials
Project work
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.
Compulsory literature:
J. Matoušek, J. Nešetřil, Chapters in Discrete Mathematics, Karolinum Praha (2000).
Recommended literature:
D. B. West, Introduction to graph theory - 2nd ed., Prentice-Hall, Upper Saddle River NJ, (2001).
Way of continuous check of knowledge in the course of semester
During the semester each student prepares one or two projects.
Topic of each project is chosen among topics presented in the lecture.
The sumbission date and all assignments are available on the instructor webpage or in the university electronic information system.
(Each student has to register for a topic.)
For a pass it is necessary to have at least one project graded for at least 10 points.
E-learning
Other requirements
There are no other requirements.
Prerequisities
Subject has no prerequisities.
Co-requisities
Subject has no co-requisities.
Subject syllabus:
Lectures:
1) Graphs, simple graphs. Incidence matrix and adjacency matrix. Subgraphs. Degree of a vertex.
2) Paths and cycles.
3) Trees, bridges and cuts.
4) Graph isomorphisms.
5) Connectivity and blocks. Cut sets.
6) Matching and covers in general and bipartite graphs. Perfect matchings.
7) Edge colorings. Chromatic index, Vizing's Theorem.
8) Vertex colorings, Chromatic number, Brook's Theorem.
9) Planar graphs. Dual graphs, Euler's formula for connected planar graphs, Kuratowski's Theorem. Four Color Theorem.
10) Non-planar graph, measures of non-planarity.
11) Eulerian and Hamiltonian graphs.
12) Oriented graphs. Oriented paths and cycles.
13) Tournaments, graph models.
14) Further topics: flows in networks, cuts.
Conditions for subject completion
Occurrence in study plans
Occurrence in special blocks