A tantárgyleírás hatályossága
Hatályosság kezdete:
2026. March 21.
Hatályosság vége:
—
| Subject name (Hungarian, English) |
Gráfelmélet
Graph Theory
|
||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Subject code | BMEVISZA086 | ||||||||||||
| 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 | www.cs.bme.hu/.... | ||||||||||||
| 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
Programme
- Introduction
Why are they interesting and what are we interested in about them
Trees and their main properties
Coding and counting trees on n labelled vertices
2. The Königsberg bridges problem and Euler tours
Euler tours in directed graphs
The existence of deBruijn sequences
Hamiltonian cycles
The different nature of Hamiltonian cycles and Euler tours
Necessary conditions for Hamiltonicity
Sufficient conditions for Hamiltonicity due to Dirac,
- Matchings and their relevance
Kőnig's min-max theorem
Perfect matchings in general graphs, Tutte's criterion
Stable matchings and their use
The existence of stable matchings in bipartite graphs
- Network flows
The Ford-Fulkerson min-max result and its relation to Kőnig's one
Menger's min-max results
The relevance of min-max formulae in general
- Planarity,
Minors and Wagner's criterion
The equivalence of forbidding the Kuratowski graphs as minors and as topological
subgraphs
- Coloring graphs as a model for scheduling
Bounding the chromatic number from below, Mycielski's construction
Coloring edges
Line graphs and the analogs of the previous bounds
Improving the greedy algorithm, Vizing's upper bound
- Coloring planar graphs, 4-color theorem and 5-color theorem,
theorem
Perfect graphs, perfectness of bipartite graphs, their line graphs and the complements
of these
Odd holes, odd antiholes and their relevance
Relation of complementation and perfectness in general
8. List coloring
Relation of the list coloring number to the chromatic number, list coloring conjecture
Galvin's theorem and its relation to stable matchings
List coloring planar graphs
Thomassen's inductive argument
Voigt's construction for the sharpness of Thomassen's result
- Extremal graph theory
The Erdős-Stone theorem and the Erdős-Simonovits limit result
The Kővari-T.Sós-Turán upper bound for the analogous bipartite problem
- Ramsey theory
Examples of Ramsey-type results outside graph theory
Ramsey numbers, upper and lower bounds
- Hypergraphs as generalizations of graphs and as set systems
Sperner systems and their maximum possible size
LYM inequality
Intersecting set systems, Erdős-Ko-Rado theorem
- Kneser's conjecture as a problem on hypergraphs
Kneser graphs and fractional colorings
The objective of the first part of this course is to introduce the students with some of the most important notions of graph theory and develop their skill to solve basic exercises. It is also an objective of the course that on the way they become able to identify graph theory problems in a natural way even if those appear in a different setting.
The objective of the second part is to deepen the students' knowledge of graph theory by showing interrelations of some of the seemingly loosely related concepts and further develop their problem solving skills. Although there is no formal prerequisite for this course, some basic mathematical maturity is expected.
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
Lectures and recitations
Tanulástámogató anyagok
Online források
Reinhard Diestel: Graph Theory, 3rd Edition, Springer-Verlag, Heidelberg, 2005; or ; ; Béla Bollobás: Modern Graph Theory, Springer-Verlag, Heidelberg, Corr. 2nd printing 2002. ; Additional useful reading: Martin Aigner, Günter Ziegler:Proofs from the Book, Springer-Verlag, Heidelberg, 1998.
Recommended preliminary knowledge for completing the subject
Knowledge type competencies
(azon előzetes ismeretek összessége, amelyek megléte nem kötelező, de a tantárgy eredményes teljesítését nagyban elősegíti)
nincs
Skill type competencies
(azon előzetes képességek és készségek összessége, amelyek megléte nem kötelező, de a tantárgy eredményes teljesítését nagyban elősegíti)
nincs
Recommended (non-compulsory) preliminary competencies
(azon ajánlott (nem kötelező) előzetesen megszerzendő kompetenciák összessége, amelyek jelentősen hozzájárulnak a tantárgy eredményes teljesítéséhez)
nincs
General rules
Requirements:
The grade given will be based on four homework assignments consisting of five problems each, and on the final exam. The solutions should be handed in by the due date that will be on the 4th, 6th, 9th and 11th weeks, respectively. The assignments will be handed out at least a week before the due date. (Please note that no late homework will be accepted.) The assignments weigh 15% each while the final exam weighs 40% in calculating the final score.
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
Requirements valid from:
—
Requirements valid until:
—
Curriculum placement
No curriculum placements recorded for this subject version.