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

    Belépés
    címtáras azonosítással

    vissza a tantárgylistához   nyomtatható verzió    

    Combinatorics and Graph Theory 1

    A tantárgy neve magyarul / Name of the subject in Hungarian: Kombinatorika és gráfelmélet 1

    Last updated: 2016. május 6.

    Budapest University of Technology and Economics
    Faculty of Electrical Engineering and Informatics
    Mathematics BSc
    Course ID Semester Assessment Credit Tantárgyfélév
    VISZA025   2/2/0/v 6 2
    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 and Géza Tóth
    6. Pre-requisites
    Kötelező:
    NEM ( TárgyEredmény( "BMEVISZAA01" , "jegy" , _ ) >= 2
    VAGY
    TárgyEredmény("BMEVISZAA01", "FELVETEL", AktualisFelev()) > 0
    VAGY
    TárgyEredmény( "BMEVISZAA02" , "jegy" , _ ) >= 2
    VAGY
    TárgyEredmény("BMEVISZAA02", "FELVETEL", AktualisFelev()) > 0 )

    A fenti forma a Neptun sajátja, ezen technikai okokból nem változtattunk.

    A kötelező előtanulmányi rendek grafikus formában itt láthatók.

    8. Synopsis

    Enumerative combinatorics (permutations and combinations, binomial theorem, theorems on the binomial coefficients). Significant methods for enumeration, pigeonhole principle and the sieve.

    Basic Graph Theoretical notions (vertex, edge, degree, isomorphism, path, cycle, connectivity). Trees, Cayley's formula, Prüfer-sequences. Kruskal's greedy algorithm. Characterization of bipartite graphs. Matchings, theorems of Kőnig, Hall and Frobenius, Tutte theorem, Gallai's theorems. Network flows, the Ford-Fulkerson algorithm, Edmonds-Karp algorithm.  

    Menger's theorems, higher vertex and edge connectivity of graphs, Dirac's theorem.

     Euler's result on Eulerian tours and trails.

    Hamiltonian cycles and paths, necessary condition for the existence. Sufficient conditions (theorems of Dirac, Ore, Pósa and Chvátal).

     Planarity, relation to embeddability on the sphere and the torus, stereographic projection, Euler polyhedron theorem, Kuratowski's theorem, Fáry theorem.

     BFS and DFS, algorithms for shortest paths (Dijkstra, Ford, Floyd), PERT.

    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, 10% on the homework assignments and 50% on the oral exam.

    11. Recaps

    According to the general rules: one midterm can be repeated.

    12. Consultations According to demand
    13. References, textbooks and resources

    R. Diestel: Graph Theory (online available)

    J.A. Bondy & U.S.R. Murty: Graph Theory with Applications

     

    14. Required learning hours and assignment
    Kontakt óra56
    Félévközi készülés órákra56
    Felkészülés zárthelyire20
    Házi feladat elkészítése 
    Kijelölt írásos tananyag elsajátítása 
    Vizsgafelkészülés48
    Összesen180
    15. Syllabus prepared by Tamás Fleiner and Géza Tóth