Graphs and Algorithms
A tantárgy neve magyarul / Name of the subject in Hungarian: Gráfok és algoritmusok
Last updated: 2018. július 8.
Mathematics BSc
Theorethics and Applied Specialization
This lecture intends to introduce areas that are closely connected to graph theory but usually do not fit into an introductory course. The algorithmic approach plays an important role in the solution of the studied problems.
Algorithmic proofs: greedy techniques, improving pahts, local improvements and elementary constructions
Stable matchings, the Gale-Shapley algorithm, lattice property of stable matchings. Applications: linking property of paths, Galvin's theorem, Alon-Tarsi theorem on the choosability of planar bipartite graphs, the Sands-Sauer-Woodrow theorem, kernels in acyclic digraphs.
Stable matchings on nonbipartite graphs: Irving's algorithm. Stable half-matchings and Scarf's lemma
Finding minimum cuts in graphs, the Nagamochi-Ibaraki algorithm (maxback order), simplicial graphs, simplicial vertices, list-colouring of simplicial graphs, Karger's algorithm
Representation of laminar families and of minimum cuts: the Gomory-Hu (cut equivalent) tree and the cactus-representation.
Tutte theorem, Tutte-Berge formula, Edmonds-Gallai structure theorem, factor critical graphs.
Lovász' theorem on splitting off, construction of 2k-edge-connected graphs, Nash-Williams'orientation theorem.
Circulations and flows. Hoffmann's theorem, algorithm for minimum-cost circulation.
Applications of the integrality lemma (edge-coloring of bipartite graphs, rounding property of flows and Baranyai's theorem).
In the semester: two midterm. The condition for the audit is that both midterms are succesful.
In the exam season: oral exam for those that have a valid audit. The final grade is based 40% on the midterms and 60% on the oral exam.
R. Diestel: Graph Theory
András Frank: Connections in Combinatorial Optimization