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	Algoritmica grafelor – Gráfalgoritmusok	

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

II. Főállású oktatók
Név	Tudományos	Oktatói	Tanszék	Tevékenység	
	fokozat	státus		E	Sz	L	
KÁSA Zoltán	Dr.	Prof.	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
A tantárgy célja, hogy megismertesse a hallgatókkal azokat a gráfelméleti foglamakat és algoritmusokat, amelyekre az informatikai tanulmányaik során feltétlenül szükségük van. A szemináriumokon a tanult foglamakat és algoritmusokat elmélyítik konkrét feladatok megoldásával. A gyakorlati órákon ezen algoritmusok egy részét programozzák és tesztelik. 	

IV. A tantárgy tartalma
Alapfogalmak.
Legrövidebb utak problémája A kritikus út módszere és alkalmazásai 
Euler- és bejárás Hamilton-bejárás 
Fák és ligetek. Alkalmazások 
Síkgráfok 
Folyamfeladatok és alkalmazások 
Párosítás páros gráfokban (magyar módszer, alkalmazások)
Extrémális feladatok a gráfelméletben (Ramsey- és Turán-típusú feladatok)
Függgetlen ponthalmazok, színezések	

V. Könyvészet
1. Andrásfai Béla, Gráfelmélet, Polygon Kiadó Szeged , 1994. 
2. Bege Antal, Kása Zoltán: Algoritmikus kombinatorika és számelmélet, Ed. Presa Univ. Clujeana, 2006
3. Katona Gyula Y., Recski András, Szabó Csaba: Gráfelmélet, algoritmuselmélet és algebra, Budapest, Egyetemi jegyzet, 1997. 
4. Berge, C., Teoria grafurilor si aplicatiile ei, Ed. Tehnica, 1972
5. Tomescu, I., Introducere in combinatorica, Ed. Tehnica, 1972
6. Kása Zoltán: http://www.cs.ubbcluj.ro/~kasa
(A kari könyvtárban megtalálhatók)	

VI. Az oktatói tevékenység heti tematikája
1. előadás: Alapfogalmak. Milyen feladatok megoldásánál használhatunk gráfokat
2-3. előadás: Legrövidebb utak problémája (Dijkstra, Ford, Warhall-Floyd, Bellman-Kalaba algoritmusai)
4. előadás: A kritikus út módszere és alkalmazásai 
5. előadás: Euler-bejárás
6. előadás: Hamilton-bejárás 
7. előadás: Fák és ligetek. Alkalmazások 
8. előadás: Síkgráfok 
9-11.  előadás: Folyamfeladatok és alkalmazások (Ford–Fulkerson-algoritmus, általánosított folyamok, minimális költségű folyamok)
12. előadás: Párosítás páros gráfokban (magyar módszer, alkalmazások)
13. előadás: Extrémális feladatok a gráfelméletben (Ramsey- és Turán-típusú feladatok)
14. előadás: Függgetlen ponthalmazok, színezések

1. gyakorlat: Gráfok ábrázolása
2. gyakorlat: Távolsági mátrix kiszámítása, alkalmazás útkeresésre
3. gyakorlat: Dijsktra és Ford algoritmusa
4. gyakorlat: Bellman–Kalaba-algoritmus
5. gyakorlat: Kritikus út módszere
6-7. gyakorlat: Magyar módszer

VII. Alkalmazott didaktikai módszerek
kifejtés, problematizálás	

VIII. Értékelés
Évközi tevékenység és írásbeli vizsga.  A végleges jegyben 
50% súllyal szerepel az írásbeli vizsga, 
25% súllyal a szemináriumi és 
25% súllyal a laboratóriumi tevékenység.	

IX. Kiegészítő könyvészet
1. Cataranciuc, S., Iacob,  M. E., Toadere, T., Probleme de teoria grafelor, Lito. Univ. Cluj-Napoca, 1994
2. Kása, Z., Tartia, C., Tâmbuilea, L., Culegere de probleme de teoria grafelor, Lito. Univ. Cluj-Napoca, 1979
3. Gondran M., Minoux, M., Graphes et algorithmes, Paris, 1979
4. Rosu, A., Teoria grafurilor, algoritmi, aplicatii. Ed. Militara, 1974
5. Lovász, L., Kombinatorikai problémák és feladatok, Typotex Kiadó, 1999
6. Toadere, T., Elemente de teoria grafelor, Lito. Univ. Cluj-Napoca, 1992
7. Tomescu, I., Probleme de combinatorica si teoria grafurilor, Ed. did. si ped., Bucurest
(A kari könyvtárban megtalálhatók).	

	Dátum,						Az előadás felelőse,
       2009. ápr. 13.					Dr. KÁSA Zoltán, egyetemi tanár