Universitatea Babeş-Bolyai Cluj-Napoca
Facultatea de Matematică şi Informatică
Ciclul de studii: Licenţă
Domeniul: Informatică
Programul de studii: Informatică - în limba engleză
Limba de predare: Engleză

SYLLABUS

I. General data
Code	Subject	
MIG0001	Algorithms of Graph Theory	

Semester	Hours: C+S+L+P	Category	Status	
5	2+1+1+0	speciality	compulsory	

II. Full status faculty members
Name and	Scientific	Didactic	Department	Type of activity	
surname	title	title		C	S	L	
LUPSA Radu	Ph.D.	Lect.	Computer Science	*			

Associated faculty members
Name and	Scientific	Institution	Type of	Type of activity	
surname	title		position	C	S	L	

III. Course objectives
The main objective is to introduce the students in the graph theoretical concepts and using these concepts in the problem modelling. The second one is the presentation and programming of the  main graph threoretical algorithms. 	

IV. Course contents
1. Introductory notions (grahs, directed graphs, subgrahs, paths, cycles, circuits, conectivity)
2. Paths problems: shortest path problem (algorithms: Moore-Dijkstra, Bellman-Kalaba, Ford, Floyd-Hu, Dantzig, Floyd-Hu-Warshall), Critical Path Method, Eulerian path, Hamiltonisan path. 
3. Fundamental numbers in graph theory (internal stability number, external stability number, algorithms, cromatic number, cyclomatic number)
4. Tress and forests (Kruskal's and Prim's algorithms) 
5. Planarity in graphs
6. Flows in networks  (algorithm of Ford-Fulkerson, extensions).
7. Matching problems
8. Extremal problems (theorems of Ramsey and Turán)
9. Counting and enumerating problems	

V. Bibliography
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. Thematic of didactic activities per weeks
•	basic graph theory definitions (graph, multigraph, directed graph/multigraph, walk, trail, path), representations; week 1-2.
•	path-related problems: connected and strongly-connected graphs, connected components, shortest path, Moore, Bellman-Kalaba, Dijkstra, Floyd-Warshal algorithms; week 3-4.
•	partial ordering, critical path; topological sorting and PERT method; week 5-6.
•	trees and forests; Kruskal and Prim algorithms; graph traversal and applications; week 7.
•	hard problems (clique, independent set, vertex covering, coloring, Hamiltonian cycle, traveling salesman problem); weeks 8-9
•	Eulerian cycle; week 10
•	planar graph; week 10
•	transport networks and flows; maximum flow problems; matching problems; week 11-12
•	counting and enumerating problems; week 13-14
•	extremal problems; week 14	

VII. Didactic methods used

VIII. Assessment
Practical work + exam
1/3 practical work
2/3 written exam
See also: http://www.cs.ubbcluj.ro/~rlupsa/edu/grafe/requirements.html	

IX. Additional references
http://www.cs.ubbcluj.ro/~rlupsa/edu/grafe/	

	Dean,							Department head,

	Date,							Course responsible,
								Lect. LUPSA Radu, Ph.D.