Subject » BMEVISZM022
Combinatorics and Graph Theory 2M
Kombinatorika és gráfelmélet 2M
A tantárgyleírás hatályossága
Hatályosság kezdete:
2026. March 21.
Hatályosság vége:
—
| Subject name (Hungarian, English) |
Kombinatorika és gráfelmélet 2M
Combinatorics and Graph Theory 2M
|
||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Subject code | BMEVISZM022 | ||||||||||||
| Subject type | — | ||||||||||||
| Training Level | — | ||||||||||||
| Course types and hours (weekly/semester) |
|
||||||||||||
| Assessment type | vizsga | ||||||||||||
| Credits | 5 | ||||||||||||
| 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 | https://www.renyi.hu/~geza/kombi2/ | ||||||||||||
| 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
Geometriai és absztrakt dualitás, gyenge izomorfia (2-izomorfia), Whitney tételei.
Pont- és élszínezési alapfogalmak, Mycielsky-konstrukció, Brooks-tétel.
Ötszíntétel.
Vizing-tétel, élszínezés kapcsolata teljes párosításokkal, Petersen-tétel.
Listaszínezés, Galvin-tétel.
Perfekt gráfok, intervallumgráfok, Perfekt gráf tétel.
Ramsey-tétel, Erdős-Szekeres-tétel, Erdős-féle alsó becslés, valószínűségszámítási módszer.
Turán-tétel, Erdős-Stone-tétel, Erdős-Simonovits-tétel.
Hipergráfok, Erdős-Ko-Rado-tétel, Sperner-tétel, LYM-egyenlőtlenség.
De Bruijn-Erdős-tétel, véges síkok, konstrukciójuk véges testből, differencia-halmazokból.
Generátorfüggvények, Fibonacci-számok, Catalan-számok.
Részben rendezett halmazok, Dilworth-tétel.
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
Heti 2 óra előadás és heti 2 óra gyakorlat.
Tanulástámogató anyagok
Not provided.
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)
Alapvető gráfelméleti fogalmak és algoritmusok.
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)
Alapvető gráfelméleti fogalmak és algoritmusok.
General rules
Követelmények:
2 db zárthelyi. Aláírás feltétele: mindkettő legyen legalább elégséges.
hetente 2db 10 pontos beadandó házi feladat, a teljesítés feltétele 40 pont megszerzése
Vizsgaidőszakban szóbeli vizsga. Érdemjegy súlyozása: zh 40%, házi feladat 10%, szóbeli vizsga 50%.
Pótlási lehetőségek:
Egy zárthelyi pótolható, házi feladat nem pótolható
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
IMSc program:
Dr. Fleiner Tamás, egyetemi docens
Dr. Tóth Géza, egyetemi docens
Recommended courses
Kombinatorika és Gráfelmélet 1. BMEVISZA025 vagy
A számítástudomány alapjai BMEVISZAA05 vagy
Bevezetés a számításelméletbe 2. BMEVISZAA04
Kizárás:
BMEVISZA026 Kombinatorika és Gráfelmélet 2.
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.