Combinatorics and Graph Theory 1
A tantárgyleírás hatályossága
| Subject name (Hungarian, English) |
Kombinatorika és gráfelmélet 1
Combinatorics and Graph Theory 1
|
||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Subject code | BMEVISZA025 | ||||||||||||
| Subject type | — | ||||||||||||
| Training Level | — | ||||||||||||
| Course types and hours (weekly/semester) |
|
||||||||||||
| Assessment type | vizsga | ||||||||||||
| Credits | 6 | ||||||||||||
| Subject coordinator |
Fleiner Tamás
position: egyetemi tanár
contact:
fleiner.tamas@vik.bme.hu
|
||||||||||||
| Responsible department |
Számítástudományi és Információelméleti Tanszék
|
||||||||||||
| Faculty | Villamosmérnöki és Informatikai Kar | ||||||||||||
| Subject website | — | ||||||||||||
| Primary curriculum type | — | ||||||||||||
| Direct prerequisites – Strong prerequisite | none | ||||||||||||
| Direct prerequisites – Weak prerequisite | none | ||||||||||||
| Direct prerequisites – Parallel prerequisite | none | ||||||||||||
| Direct prerequisites – Milestone prerequisite | none | ||||||||||||
| Direct prerequisites – Exclusion | none |
Objectives
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.
No objectives provided.
Learning outcomes
Ez a tantárgy a KKK rendeletben meghatározott, következő kompetenciák fejlesztését szolgálja:
Knowledge
No learning outcomes recorded.
Skills
No learning outcomes recorded.
Attitudes
No learning outcomes recorded.
Autonomy and responsibility
No learning outcomes recorded.
Oktatási módszertan
Tanulástámogató anyagok
Online források
Recommended preliminary knowledge for completing the subject
General rules
Assessment methods
In-term assessments
No detailed assessments provided.
Weight of in-term assessments
No weights provided.
Exam-period assessments
No detailed assessments provided.
Weight of exam elements
No weights provided.
Grade calculation
No grade thresholds provided.
Attendance requirements
No attendance requirements provided.
Rules for retake and resubmission
Not provided.
Short description
Not provided.
Detailed description
Not provided.
Recommended courses
Not provided.
Workload to complete the subject
No workload breakdown provided.
Validity of subject requirements
Curriculum placement
No curriculum placements recorded for this subject version.