Tuesday 10:00-12:00, Kerékjártó room
There will be 2 midterms, on 18th October and 6th 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. Basics
2. Connectivity
3. Realization of degree sequences. Trees.
4. Spanning trees
5. Network flows
6. Application of network flows
Sample midterm exam #1,
Sample midterm exam #2.
Components: #1 (a graph with 4 components),
#2 (a graph with 3 components),
#3 (a graph with 3 components).
Tree: #1, #2.
Spanning tree: #1, #2.
Tree traversals: breadth-first search, depth-first search.
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 set: #1, #2.
Proper (vertex) coloring: #1,
#2.
Four color map problem / Four color theorem #1, #2.
Edge coloring: #1, #2.
Eulerian tours: #1 (closed Eulerian tour),
#2 (closed Eulerian tour),
#3 (non-closed Eulerian tour).
Hamiltonian path: #1, #2.
Hamiltonian cycle: #1, #2, #3.
These pictures were mostly collected from the web (see the URLs for the source).
Béla Csaba, Péter Hajnal, Gábor V. Nagy: Graph theory for MSc students in computer science (2019) [Note, textbook]
