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 óra 56 Félévközi készülés órákra 56 Felkészülés zárthelyire 20 Házi feladat elkészítése Kijelölt írásos tananyag elsajátítása Vizsgafelkészülés 48 Összesen 180
15. Syllabus prepared by Tamás Fleiner and Géza Tóth