A tantárgy adatlapja
1.	A képzési program adatai
1.1 Felsőoktatási intézmény	Babeş-Bolyai Tudományegyetem	
1.2 Kar 	Matematika és Informatika	
1.3  Intézet	Magyar Matematika és Informatika	
1.4 Szakterület	Informatika	
1.5 Képzési szint	Alap	
1.6 Szak / Képesítés	Informatika  és Matematika-informatika 	

2.	A tantárgy adatai
2.1 A tantárgy neve	Gráfelmélet	
2.2 Az előadásért felelős tanár neve	Dr. Kása Zoltán	
2.3 A szemináriumért felelős tanár neve	Dr. Gaskó Noémi	
2.4 Tanulmányi év	3	2.5 Félév	1	2.6 Értékelés módja	vizsga	2.7 Tantárgy típusa	Informatika kötelező –alap
Matematika-informatika opcionális 	

3.	Teljes becsült idő (az oktatási tevékenység féléves óraszáma)
3.1 Heti óraszám	4	melyből: 3.2 előadás	2	3.3 szeminárium/labor	2	
3.4 Tantervben szereplő össz-óraszám	56	melyből: 3.5 előadás	28	3.6 szeminárium/labor	28	
A tanulmányi idő elosztása:	óra	
A tankönyv, a jegyzet, a szakirodalom vagy saját jegyzetek tanulmányozása	38	
Könyvtárban, elektronikus adatbázisokban vagy terepen való további tájékozódás	7	
Szemináriumok / laborok, házi feladatok, portofóliók, referátumok, esszék kidolgozása	36	
Egyéni készségfejlesztés (tutorálás)	7	
Vizsgák	6	
Más tevékenységek: ..................		
3.7 Egyéni munka össz-óraszáma	94	
3.8 A félév össz-óraszáma	150	
3.9 Kreditszám	6 (M), ill. 4 (MI)	
.
4.	Előfeltételek (ha vannak)
4.1 Tantervi	•	Nincsen	
4.2 Kompetenciabeli	•	A gráfelmélet alapkompetenciái	

5.	Feltételek (ha vannak)
5.1 Az előadás lebonyolításának feltételei	•	Táblával és videoprojektorral felszerelt előadó	
5.2 A szeminárium / labor lebonyolításának feltételei	•	Számítógépes terem	

6.	Elsajátítandó jellemző kompetenciák
Szakmai kompetenciák	•	A gráfelmélet alapfogalmainak ismerete és használata.
•	A gráfelmélet alaptételeinek és algoritmusainak ismerete és megfelelő használata.
•	Egyszerű feladatok programozása.
	
Transzverzális kompetenciák 	•	A gráfelmélet gyakorlati alkalmazása

7.	A tantárgy célkitűzései (az elsajátítandó jellemző kompetenciák alapján)
7.1 A tantárgy általános célkitűzése	•	Modellezési, feladatmegoldói, matematikai szövegértési és a megfelelő programozási készségek, jártasságok fejlesztése 	
7.2 A tantárgy sajátos célkitűzései

	•	A gráfelmélet alapfogalmainak és alaptételeinek megismerése, megértése.
•	Feladatok matematikai modellezése és megfelelő algoritmusok tervezése.
•	A  gráfelmélet  alkalmazhatóságának megismerése.	

8.	A tantárgy tartalma
8.1 Előadás	Didaktikai módszerek	Megjegyzések	
1. Alapfogalmak	előadás		
2. Gráfok bejárása	előadás		
3. Utak a gráfban. Legrövidebb utak algoritmusai: Moore-Dijkstra, Bellman-Kalaba, Ford, Floyd-Warshall. Kritikus út. Euler- és Hamilton-gráfok.	előadás		
4. Fák és ligetek, feszítőfák. Kruskal és Prim algoritmusa	előadás		
5. Síkba rajzolható gráfok	előadás		
6. Folyamfeladatok, Ford-Fulkerson algoritmus, minimális 	előadás		
7. Páros gráfok	előadás		
8. Extrémgráfok (Ramsey és Turán tétele)	előadás		
9. Gráfok színezése	előadás		
Könyvészet
1. BERGE C., Graphes et hypergraphes, Dunod, Paris 1970.
2. B. ANDRÁSFAI: Ismerkedés a gráfelmélettel, Tankönyvkiadó, Budapest 1971, 1973, 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, 1994
7. CORMEN, LEISERSON, RIVEST: 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. ROSU A.: Teoria grafelor, algoritmi, aplicatii. Ed. Milit.1974 
10. Kása Zoltán: Gráfelmélet (eletromikus jegyzet a saját honlapon)	
8.2 Szeminárium / Labor	Didaktikai módszerek	Megjegyzések	
Szeminárium: 
Az előadás anyagának áttekintése, konkrét feladatok megoldása
	Feladatok megoldása		
Laboratóriumi gyakorlatok:			
1. Gráfok  ábrázolása csúcsmátrix és listák segítségével.	Feladatok programozása		
2. Gráf távolsági mátrixának kiszámítása. 			
3. Legrövidebb út keresése gráfban (Dijsktra, Ford, Bellman)			
4. Kritikus út keresése			
Könyvészet	
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.

9.	A tantárgy tartalmának összhangba hozása az episztemikus közösségek képviselői, a szakmai egyesületek és a szakterület reprezentatív munkáltatói elvárásaival.
•	 A tantárgy tartalma megegyezik az egyetemi oktatásban a fontosabb egyetemeken oktatott elméleti mechanika bevezető tárgy hagyományos tartalmával.
•	A tárgy keretében figyelembe vesszük a számítógép használata nyújtotta lehetőségeket a problémák vizsgálatában. 	

10.	Értékelés
Tevékenység típusa	10.1 Értékelési kritériumok	10.2 Értékelési módszerek	10.3 Aránya a végső jegyben	
10.4 Előadás 	Alapfogalmak és alaptételek ismerete	Szóbeli vizsga	50 %	
				
10.5 Szeminárium / Labor	Feladatmegoldások helyessége	Évközi értékelés	50 %	
				
10.6 A teljesítmény minimumkövetelményei	
•	A gráfelmélet legalapvetőbb fogalmainak ismerete
•	A gráfelmélet legalapvetőbb  algoritmusainak ismerete
•	Tudjon megoldani és programozni egyszerű  gráfelméleti feladatokat	

Kitöltés dátuma			Előadás felelőse			Szeminárium felelőse
2012. szept. 8. 			Dr. Kása Zoltán                                  Dr. Gaskó Noémi			...................................

Az intézeti jóváhagyás dátuma				Intézetigazgató,	
2012. szept. 28.						Dr. Szenkovits Ferenc, egyet. docens
..........................