Babes-Bolyai University of Cluj-Napoca
Faculty of Mathematics and Computer Science
Study Cycle: Graduate

SUBJECT

Code
Subject
MIG0001 Algorithms of Graph Theory
Section
Semester
Hours: C+S+L
Category
Type
Computer Science
3
2+1+1
speciality
compulsory
Teaching Staff in Charge
Prof. KASA Zoltan, Ph.D.,  kasacs.ubbcluj.ro
Assoc.Prof. TOADERE Teodor, Ph.D.,  toaderecs.ubbcluj.ro
Lect. LUPSA Radu, Ph.D.,  rlupsacs.ubbcluj.ro
Aims
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.

Content
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
References
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

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.
Assessment
Practical work + exam
50% practical work
50% written exam
Links: Syllabus for all subjects
Romanian version for this subject
Rtf format for this subject