Kombinatorika és gráfelmélet 1

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

Adatlap utolsó módosítása: 2015. november 9.

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

TTK

Matematika BSc szak
Tantárgykód Szemeszter Követelmények Kredit Tantárgyfélév
VISZA025   2/2/0/v 6 2
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

6. Előtanulmányi rend
Kötelező:
NEM ( TárgyEredmény( "BMEVISZAA01" , "jegy" , _ ) >= 2
VAGY
TárgyEredmény("BMEVISZAA01", "FELVETEL", AktualisFelev()) > 0
VAGY
TárgyEredmény( "BMEVISZAA02" , "jegy" , _ ) >= 2
VAGY
TárgyEredmény("BMEVISZAA02", "FELVETEL", AktualisFelev()) > 0 )

A fenti forma a Neptun sajátja, ezen technikai okokból nem változtattunk.

A kötelező előtanulmányi rend az adott szak honlapján és képzési programjában található.

Ajánlott:
Villamosmérnöki és mérnökinformatikus szakos hallgatók nem vehetik fel.
8. A tantárgy részletes tematikája

Leszámlálások (permutációk, variációk, kombinációk, binomiális tétel, binomiális együtthatókra vonatkozó tételek). Nevezetes leszámlálási módszerek, skatulya-elv, szita-módszer.

Gráfelméleti alapfogalmak (pont, él, fokszám, izomorfia, út, kör, összefüggőség). Fák, Cayley-tétel, Prüfer-kód. Mohó algoritmus, Kruskal-tétel. Páros gráfok, jellemzésük. Párosítások, Kőnig-Hall-Frobenius-tétel, Tutte-tétel, Gallai tételei, Kőnig tételei. Hálózati folyamok, Ford-Fulkerson-tételek, Edmonds-Karp-tétel.

Menger tételei, gráfok magasabb pont- és él-összefüggőségi számai, Dirac-tétel.

Euler-bejárások, Euler-tétele.

Hamilton-körök és utak, létezésük szükséges feltétele. Elégséges feltételek (Dirac, Ore, Pósa és Chvatal tételei).

Síkbarajzolhatóság, viszonya a gömb és a tórusz felszínére való rajzolhatósághoz, sztereografikus projekció, Euler-formula. Kuratowski-tétel, Fáry-Wagner-tétel.

Szélességi és mélységi keresés, legrövidebb utak megkeresése (Dijkstra, Ford, Floyd algoritmusok), PERT-módszer.

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

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

Vizsgaidőszakban: szóbeli vizsga az aláírással rendelkezőknek. Érdemjegy súlyozása: ZH 40%, házi feladat 10%, szóbeli 50%.

11. Pótlási lehetőségek TVSZ szerint (Egy sikertelen 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ákra56
Felkészülés zárthelyire20
Házi feladat elkészítése 
Kijelölt írásos tananyag elsajátítása 
Vizsgafelkészülés48
Összesen180
15. A tantárgy tematikáját kidolgozta

Dr. Fleiner Tamás, egyetemi docens

Dr. Tóth Géza, egyetemi docens