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 and 14) Further topics: flows in networks, cuts. Maximal flow and minimal cut Theorem. Graph models.
Discussions:
1) Graphs, simple graphs. Degree of a vertex.
2) Paths and cycles. Important graph classes.
3) Trees, bridges and cuts.
4) Graph isomorphisms.
5) Graph connectivity, blocks and articulations.
6) Matching and covers in general and bipartite graphs. Perfect matchings.
7) Edge colorings. Chromatic index.
8) Vertex colorings, Chromatic number.
9) Planar graphs. Euler's formula for general planar graphs.
10) Non-planar graphs, measures of non-planarity.
11) Eulerian and Hamiltonian graphs.
12) Oriented graphs. Oriented paths and cycles.
13 and 14) Further topics; graph models and their limits.
During the semester each student prepares one or two projects. Topic of each project is chosen among topics presented in the lecture. Assignments are available on the instructor webpage or in the university electronic information system, for example:
1) planar graphs and their applications
2) graph colorings and their applications
For a pass it is necessary to have at least one project graded for at least 10 points.
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 and 14) Further topics: flows in networks, cuts. Maximal flow and minimal cut Theorem. Graph models.
Discussions:
1) Graphs, simple graphs. Degree of a vertex.
2) Paths and cycles. Important graph classes.
3) Trees, bridges and cuts.
4) Graph isomorphisms.
5) Graph connectivity, blocks and articulations.
6) Matching and covers in general and bipartite graphs. Perfect matchings.
7) Edge colorings. Chromatic index.
8) Vertex colorings, Chromatic number.
9) Planar graphs. Euler's formula for general planar graphs.
10) Non-planar graphs, measures of non-planarity.
11) Eulerian and Hamiltonian graphs.
12) Oriented graphs. Oriented paths and cycles.
13 and 14) Further topics; graph models and their limits.
During the semester each student prepares one or two projects. Topic of each project is chosen among topics presented in the lecture. Assignments are available on the instructor webpage or in the university electronic information system, for example:
1) planar graphs and their applications
2) graph colorings and their applications
For a pass it is necessary to have at least one project graded for at least 10 points.