Lecture: During the "exam period" oral exams will be announced to test the students' knowledge. Additionally, bonus points can be earned during the semester.
Practice: There will be 2 midterms, on 17th October and 5th December. In the first week of the exam period, one of the midterms can be rewritten on request by the student.
Additionally, bonus points can be earned during the semester.
Grades:
0% – 50%: fail (1)
51% – 62%: pass (2)
63% – 75%: satisfactory (3)
76% – 87%: good (4)
88% – 100%: excellent (5)
1. Degree sequences. Graph theory basics (graph, simple graph, vertex, edge, degree, neighborhood, subgraphs).
Realizable degree sequences, Havel—Hakimi-theorem (and algorithm).
2. Counting trees. Connectivity, trees. Prüfer codes and Cayley's theorem.
3. Network flows. Networks, feasible flows, flow value, cuts. Maximum flow - minimum cut theorem. Ford—Fulkerson-algorithm.
An application: Project selection. k-edge-connectivity and k-connectivity. Menger's theorems.
4. Matchings. Matchings, and the parameter ν(G). Matchings in bipartite graphs: Kőnig blocking set, marriage theorem, and the Hungarian method.
Matchings in general graphs: Tutte blocking set, Tutte's theorem, and Edmond's blossom algorithm.
5. Vertex coloring. Proper (vertex) coloring, chromatic number. Upper bound for χ(G) in terms of maximum degree, greedy coloring algorithm. Brooks' theorem. Planar graphs and the four color theorem.
6. Edge coloring. Proper edge coloring, edge chromatic number. Vizing's and Shannon's theorems. Edge chromatic number of complete graphs. Edge chromatic number of bipartite graphs.
7. Some graph algorithms. Breadth-first and depth-first tree transversals. Dijkstra's algorithm for finding shortest path in edge-weighted graphs.
8. Eulerian trails and applications. Eulerian trails and circuits. Euler's theorem. Chinese postman problem.
9. Hamiltonian path, Hamiltonian cycle and applications. Hamiltonian path and cycle. Dirac's theorem. A condition that implies that a graph
does not contain Hamiltonian path/cycle (after leaving k vertices...). Traveling salesman problem, and a 2-approximation algorithm.
The proofs are needed in the same detail (no proof / partial proof / sketch of the proof / full proof etc.) as it was presented in the lecture.
Tree: #1, #2, #3.
Spanning tree: #1, #2.
Components: #1 (a graph with 4 components),
#2 (a graph with 3 components),
#3 (a graph with 3 components).
Matchings: #1 (non-perfect), #2 (perfect),
#3 (matching in a bipartite graph), #4 (matching in a bipartite graph that covers A),
#5 (perfect matching in a bipartite graph).
Kőnig blocking set: #1, #2.
Proper (vertex) coloring: #1, #2, #3.
Four color map problem / Four color theorem #1, #2.
Edge coloring: #1, #2.
Tree traversals: breadth-first search, depth-first search.
Eulerian trails: #1 (Eulerian circuit),
#2 (Eulerian circuit),
#3 (open Eulerian trail),
#4 (open Eulerian trail).
Hamiltonian path: #1, #2.
Hamiltonian cycle: #1, #2, #3.
These pictures were mostly collected from the web (see the URLs for the source).
Douglas B. West: Introduction to Graph Theory (Prentice Hall)
Reinhard Diestel: Graph Theory (Springer-Verlag, free online version)
Benny Sudakov: Graph Theory (electronic lecture notes)
| ⇦ | Main page |
