Universitatea Babeş-Bolyai Cluj-Napoca
Facultatea de Matematică şi Informatică
Ciclul de studii: Licenţă
Domeniul: Informatică
Programul de studii: Informatică - linia de studiu maghiară, Miercurea Ciuc
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. Főállásban az  Egyetem  oktatói
Név	Tudományos	Oktatói	Tanszék	Tevékenység	
	fokozat	státus		E	Sz	L	
EGRI Edith	Dr. 	adj.	Informatikai rendszerek	*	*	*	

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öző területeken fellépő problémák gráfok segítségével való modellezésének elsajátítása 
- A gráfelméletben fellépő 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ítőfá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, Műszaki 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 

Példatárak:
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 modellezhető feladatok, alapfogalmak: irányított és irányítatlan gráf, egyszerű 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üggő gráf, erősen összefüggő gráf (összefüggő komponensek algoritmusa), útmátrix, centrum, sugár, átmérő.
2.	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ítőfák. Kruskal algoritmusa minimális feszítőfa 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égű 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ékű maximális párosítás.
13. Szélsőé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
előadás, gyakorlat, feladatmegoldás, beszélgetés	

VIII. Értékelés
•	év közben
–	félévi zárthelyi dolgozat írása
–	labor feladatok időbeni 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égső jegy: az év közben szerzett jegy, illetve a félév végén kapott jegy egyenlő arányban számít bele

IX. Kiegészíto könyvészet
11. www.cs.ubbcluj.ro/~kasa/graf.html (graf.pdf)
12. http://www.ms.sapientia.ro/www/hu/oktatasi-anyagok/grafalgoritmusok-katai-zoltan (grafalgoritmusok_jegyzet.pdf)	

	Dékán,						Tanszékvezető,

	Dátum,	Előadás felelőse,
        	2010.10.22.	Dr. EGRI Edith adjunktus