Universitatea Babeş-Bolyai Cluj-Napoca
Facultatea de Matematică şi Informatică
Ciclul de studii: Licenţă
Domeniul: Informatică
Programul de studii: Informatică - linia de studiu maghiară
Limba de predare: Maghiară

SYLLABUS

I. Általános adatok
Kód	Tantárgy neve	
MIG0001	Gráfalgoritmusok	

Félév	Órák: C+S+L+P	Kategória	Típus	
5	2+1+1+0	szaktárgy	kötelezö	

II. Foállásban az  Egyetem  oktatói
Név	Tudományos	Oktatói	Tanszék	Tevékenység	
	fokozat	státus		E	Sz	L	
KÁSA Zoltán	Dr. 	Prof.	Magyar Matematika és Informatika	*			

Társult oktatók
Név	Tudományos	Intézmény	Állás	Tevékenység 	
	fokozat		típusa	E	Sz	L	

III. A tantárgy célkitűzései
- Gráfelméleti alapokkal való megismerkedés
- A különbözo területeken fellépo problémák gráfok segítségével való modellezésének elsajátítása 
- A gráfelméletben fellépo egyes algoritmusok ismertetése és azok programozása	

IV. A tantárgy tartalma
1. Alapfogalmak
2. Gráfok bejárása
3. Utak a gráfban. Legrövidebb utak algoritmusai: Moore-Dijkstra, Bellman-Kalaba, Ford, Floyd-Warshall. Kritikus út. Euler- és Hamilton-gráfok.
4. Fák és ligetek, feszítofák. Kruskal és Prim algoritmusa
5. Síkba rajzolható gráfok
6. Folyamfeladatok, Ford-Fulkerson algoritmus, minimális 
7. Páros gráfok
8. Extrémgráfok (Ramsey és Turán tétele)
9. Gráfok színezése	

V. Könyvészet
1. BERGE C., Graphes et hypergraphes, Dunod, Paris 1970.
2. B. ANDRÁSFAI: Introductory graph theory, Akadémiai Kiadó - North Holland, 1987.
3. BERGE C., Teoria grafurilor si aplicatiile ei, Ed. Tehnica, 1972 
4. T. TOADERE: Grafe. Teorie, algoritmi si aplicatii , Ed. Albastra, Cluj-N., 2002 
5. KÁSA ZOLTÁN: Combinatiroca cu aplicatii, Presa Universitara Clujeana, 2003.
6. ANDRÁSFAI BÉLA: Gráfelmélet, Polygon Kiadó, Szeged, 199
7. CORMEN, LEISERSON, RIVEST: Introducere in algoritmi, Editura Computer Libris Agora,    2000. - in maghiara: Algoritmusok, Mtszaki Könyvkiadó, Budapest, I. kiadás 1997, II. kiadás 1999, III. kiadás 2000. 
8. ANDRÁSFAI BÉLA: Gráfok. Mátrixok és folyamok, Akadémiai Kiadó, Budapest, 1983. 
9. ANDRÁSFAI BÉLA: Ismerkedés a gráfelmélettel, Tankönyvkiadó, Budapest, 1971. 
10. ROSU A.: Teoria grafelor, algoritmi, aplicatii. Ed. Milit.1974 

Culegeri de probleme:
1. KÁSA Z., TARTIA C., TAMBULEA L.: Culegere de probleme de teoria grafelor, Lito. Univ.   Cluj-Napoca 1979. 
2. CATARANCIUC S., IACOB M.E., TOADERE T., Probleme de teoria grafelor, Lito. Univ.   Cluj-Napoca, 1994. 
3. TOMESCU I., Probleme de combinatorica si teoria grafurilor. Ed. Did. si Pedag. Bucuresti 1981.
4. L. LOVÁSZ : Combinatorial problems and exercises, Akadémiai Kiadó, Budapest, 1980.
5. Lovász László: Kombinatorikai problémák és feladatok, Typotex Kiadó, Budapest, 1999.	

VI. Az oktatói tevékenység heti tematikája
1. Gráfokkal modellezheto feladatok, alapfogalmak: irányított és irányítatlan gráf, egyszeru gráf, részgráf, séta, vonal, út, kör, lánc, Euler kör, Hamilton kör, gráfok ábrázolása (grafikusan, mátrixokkal, listával), összefüggo gráf, erosen összefüggo gráf (összefüggo komponensek algoritmusa), útmátrix, centrum, sugár, átméro.
Gráfok mélységi és szélességi bejárásainak algoritmusai
3. Legrövidebb utak nem súlyozott gráfokban (Moore algoritmusa). Legrövidebb utak súlyozott gráfokban: egy csúcsból minden csúcsba (Dijkstra, ill. Ford algoritmusa).
4. Legrövidebb utak súlyozott gráfokban: minden csúcsból egy csúcsba (Bellman-Kalaba), minden csúcsból minden csúcsba (Floyd-Warshall) Az algoritmusok bonyolultsága.
5. A kritikus út módszere
6. Euler- és Hamilton gráfok (Fleury algoritmusa, Hamilton út és kör keresése)
7. Fák és ligetek. Gyökeres fák, bináris fák, gazdaságos feszítofák. Kruskal algoritmusa minimális feszítofa meghatározására. Prim algoritmus
8. Prüfer-kód. Huffman algoritmusa.
9. Síkba rajzolható gráfok. Kuratowski tétele. Duális gráfok. Keresztezési szám.
10. Folyamfeladatok: a hálózati folyam és a vele kapcsolatos fogalmak ismertetése. Ford-Fulkerson algoritmus és elemzése.
11. Általánosított folyam. Minimális költségu maximális folyam. Busacker-Saaty tétele.
12. Páros gráfok, optimális hatásfokú foglalkoztatás. Módszerek maximális párosítás keresésére páros gráfokban: alternatív utak módszere, folyam segítsége, független 1-esek módszere. Minmális értéku maximális párosítás.
13. Szélsoérték feladatok - extrémgráfok. Bennfoglalás és kizárás elve. Zarankiewicz, Ramsey és Turán tétele.
14. Gráfok színezése, függetlencsúcs-halmazok, kromatikus polinom. 	

VII. Alkalmazott didaktikai módszerek

VIII. Értékelés
év közben
félévi zárthelyi dolgozat írása
labor feladatok idobeni leadása, szemináriumi tevékenység értékelése (óránként)
félév végén: írásbeli és gyakorlati vizsga
Végso jegy: az év közben szerzett jegy, illetve a félév végén kapott jegy egyenlo arányban számít bele	

IX. Kiegészíto könyvészet

	Dékán,						Tanszékvezető,

	Dátum,						Előadás felelőse,
	2011. szept. 30. 					Prof. Dr.  KÁSA Zoltán