Kombinatorika és gráfelmélet 2

A tantárgy angol neve: Combinatorics and Graph Theory 2

Adatlap utolsó módosítása: 2023. május 30.

Budapesti Műszaki és Gazdaságtudományi Egyetem
Villamosmérnöki és Informatikai Kar

TTK

Matematika BSc

Elméleti specializácó 
Tantárgykód Szemeszter Követelmények Kredit Tantárgyfélév
VISZA026   2/2/0/v 4 5
3. A tantárgyfelelős személy és tanszék Dr. Fleiner Tamás,
4. A tantárgy előadója

Dr. Fleiner Tamás, egyetemi docens

Dr. Tóth Géza, egyetemi docens

5. A tantárgy az alábbi témakörök ismeretére épít Alapvető gráfelméleti fogalmak és algoritmusok.
6. Előtanulmányi rend
Ajánlott:

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 

8. A tantárgy részletes tematikája

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.

9. A tantárgy oktatásának módja (előadás, gyakorlat, laboratórium) Heti 2 óra előadás és heti 2 óra gyakorlat.
10. Követelmények

2 db zárthelyi. Aláírás feltétele: mindkettő legyen legalább elégséges.

Vizsgaidőszakban szóbeli vizsga. Érdemjegy súlyozása: zh 40%, házi feladat 10%, szóbeli vizsga 50%.

11. Pótlási lehetőségek TVSZ szerint (Egy zárthelyi pótolható)
12. Konzultációs lehetőségek Igény szerint.
13. Jegyzet, tankönyv, felhasználható irodalom

Katona Gyula Y., Recski András, Szabó Csaba: A számítástudomány elemei, Typotex, Budapest, 2002

Friedl Katalin, Recski András, Simonyi Gábor: Gráfelmélet példatár, Typotex, Budapest, 2006.

Fleiner Tamás: A számítástudomány alapjai,  http://www.cs.bme.hu/~fleiner/jegyzet/NESZ.pdf

14. A tantárgy elvégzéséhez átlagosan szükséges tanulmányi munka
Kontakt óra56
Félévközi készülés órákra14
Felkészülés zárthelyire 8
Házi feladat elkészítése 14
Kijelölt írásos tananyag elsajátítása 
Vizsgafelkészülés 28
Összesen 120
15. A tantárgy tematikáját kidolgozta

Dr. Fleiner Tamás, egyetemi docens

Dr. Tóth Géza, egyetemi docens