Budapest University of Technology and Economics, Faculty of Electrical Engineering and Informatics

    címtáras azonosítással

    vissza a tantárgylistához   nyomtatható verzió    

    Graphs and Algorithms

    A tantárgy neve magyarul / Name of the subject in Hungarian: Gráfok és algoritmusok

    Last updated: 2018. július 8.

    Budapest University of Technology and Economics
    Faculty of Electrical Engineering and Informatics

    Mathematics BSc

    Theorethics and Applied Specialization 

    Course ID Semester Assessment Credit Tantárgyfélév
    VISZA028   2/2/0/v 4 6
    3. Course coordinator and department Dr. Fleiner Tamás, Számítástudományi és Információelméleti Tanszék
    4. Instructors Tamás Fleiner
    5. Required knowledge Basic graph theoretical notions and algorithm.
    6. Pre-requisites
    Combinatorics and Graph Theory 1.        BMEVISZA025
    7. Objectives, learning outcomes and obtained knowledge

    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.

    8. Synopsis

    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).

    9. Method of instruction Two lectures and two  tutorials each week.
    10. Assessment

    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.

    11. Recaps According to the general rules: one midterm can be repeated.
    12. Consultations Before the oral exams.
    13. References, textbooks and resources

    R. Diestel: Graph Theory

    András Frank: Connections in Combinatorial Optimization

    14. Required learning hours and assignment
    Kontakt óra56
    Félévközi készülés órákra28
    Felkészülés zárthelyire8
    Házi feladat elkészítése 
    Kijelölt írásos tananyag elsajátítása 
    15. Syllabus prepared by Tamás Fleiner