Kombinatorika és gráfelmélet 2M

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

Adatlap utolsó módosítása: 2020. december 15.

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

TTK

Matematika MSc

Diszkrét Matematika blokk
Tantárgykód Szemeszter Követelmények Kredit Tantárgyfélév
VISZM022   2/2/0/v 5  
3. A tantárgyfelelős személy és tanszék Dr. Fleiner Tamás,
A tantárgy tanszéki weboldala https://www.renyi.hu/~geza/kombi2/
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

Kizárás:
BMEVISZA026 Kombinatorika és Gráfelmélet 2.

7. A tantárgy célkitűzése

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.
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%.

11. Pótlási lehetőségek Egy zárthelyi pótolható, házi feladat nem 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ákra18
Felkészülés zárthelyire8
Házi feladat elkészítése40
Kijelölt írásos tananyag elsajátítása
Vizsgafelkészülés28
Összesen150
IMSc tematika és módszer

Dr. Fleiner Tamás, egyetemi docens

Dr. Tóth Géza, egyetemi docens