Graphs and Algorithms
A tantárgyleírás hatályossága
| Subject name (Hungarian, English) |
Gráfok és algoritmusok
Graphs and Algorithms
|
||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Subject code | BMEVISZA028 | ||||||||||||
| Subject type | — | ||||||||||||
| Training Level | — | ||||||||||||
| Course types and hours (weekly/semester) |
|
||||||||||||
| Assessment type | vizsga | ||||||||||||
| Credits | 4 | ||||||||||||
| 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
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).
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
Workload to complete the subject
No workload breakdown provided.
Validity of subject requirements
Curriculum placement
No curriculum placements recorded for this subject version.