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.
A fenti forma a Neptun sajátja, ezen technikai okokból nem változtattunk.
A kötelező előtanulmányi rend az adott szak honlapján és képzési programjában található.
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.
Two lectures and two tutorials each week.
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.
According to the general rules: one midterm can be repeated.
R. Diestel: Graph Theory (online available)
J.A. Bondy & U.S.R. Murty: Graph Theory with Applications