"Babes-Bolyai" University of Cluj-Napoca
Faculty of Mathematics and Computer Science

Data structures and graph algorithms
Code
Semes-
ter
Hours: C+S+L
Credits
Type
Section
MI014
5
2+1+1
5
optional
Matematică-Informatică
MI014
5
2+1+1
5
optional
Matematică-Informatică
Teaching Staff in Charge
Prof. KASA Zoltan, Ph.D., kasa@cs.ubbcluj.ro
Assoc.Prof. TOADERE Teodor, Ph.D., toadere@cs.ubbcluj.ro
Aims
The main objective is to introduce the students in the graph theoretical and data structures concepts and using these concepts in the problem modelling. The second one is the presentation and programming of the main graph threoretical algorithms.

Content
0. Elementary data structures.
1. Introductory grahs notions
2. Paths problems: shortest path problem.
3. Fundamental numbers in graph theory (internal stability number, external stability number, algoritms, 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
References
1. 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.
2. Berge C., Graphes et hypergraphes, Dunod, Paris 1970.
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: Matematica discreta, UBB, Cluj, 2001.
6. Rosu A.: Teoria grafelor, algoritmi, aplicatii. Ed. Milit.1974
7. Andrásfai Béla: Gráfelmélet, Polygon Kiadó, Szeged, 1994.
8. B. Andrásfai: Introductory graph theory, Akadémiai Kiadó - North Holland, 1987.
9. Andrásfai Béla: Gráfok. Mátrixok és folyamok, Akadémiai Kiadó, Budapest, 1983.
10. T. Toadere, I. Lazar: Structuri de date si grafe, UBB. Cluj, 2001

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
Oral exam.