Universitatea Babeş–Bolyai, Cluj–Napoca
Facultatea de Matematică şi Informatică
Anul universitar 2006-2007
Semestrul I

I.	General informations on course, practical work, and seminar :
Titlul disciplinei: Algorithms on Graphs
Codul: MIG0001
Numărul de credite: 5
Locul de desfăşurare:
Programarea în orar a activităţilor:

II.	Informations about titular professor :

Nume, titlul ştiinţific: Lupşa Radu-Lucian, lect. dr.
Informaţii de contact (adresă e-mail, eventual nr. de telefon): rlupsa@cs.ubbcluj.ro
Ore de audienţă:

III.	Description: 
Objectives: to learn to use the graphs as a modeling tool for problems, and to know the main graph theory problems and their solutions (algorithms). Also, to develop algorithmical thinking.
Content:
•	basic graph theory definitions (graph, multigraph, directed graph/multigraph, walk, trail, path), representations;
•	path-related problems: connected and strongly-connected graphs, connected components, shortest path, Moore, Bellman-Kalaba, Dijkstra, Floyd-Warshal algorithms; Eulerian path and Hamiltonian path;
•	partial ordering, critical path; topological sorting and PERT method;
•	trees and forests; Kruskal and Prim algorithms; graph traversal and applications;
•	internal and external stability problems; coloring problem; planar graphs;
•	transport networks and flows; maximum flow problems; coupling problems;
IV.	Bibliography:
1.	Toadere T., Grafe. Teorie, Algoritmi si Aplicatii, Ed. Albastra, Cluj-Napoca, 2002;
2.	Th. Cormen, R. Rivest, Ch. Leiserson. Introduction to Algorithms. Massachusetts Institute of Technology, 1990
3.	Th. Cormen, R. Rivest, Ch. Leiserson. Introducere in algoritmi. trad. Computer Libris Agora, 2000

V.	Materials:
Pencil and paper, computer with a programing environment (Pascal, C or C++)
VI.	Timetable/Calendar of the meetings and intermediate examinations:
No intermediate examinations.
Meetings according to the Faculty timetable.

VII.	Evaluation:
•	laboratory practical works for 1/3 of the final mark
•	written exam for 2/3 of the final mark

VIII.	Organization, special cases:
according to the Faculty internal regulations

IX.	Optional bibliography:
1.	KÁSA Z., TARTIA C., TAMBULEA L.: Culegere de probleme de teoria grafelor, Lito. Univ. Cluj-Napoca 1979. 
CATARANCIUC S., IACOB M.E., TOADERE T., Probleme de teoria grafelor, Lito. Univ. Cluj-Napoca, 1994.
2.	Livovschi L., Georgescu H. Algoritmi si grafe.
3.	TOMESCU I., Probleme de combinatorica si teoria grafurilor. Ed. Did. si Pedag. Bucuresti 1981.
4.	Tomescu I., Ce este teoria grafurilor? Ed.St. si Enciclopedica, Bucuresti 1982.
5.	Tomescu I., Grafuri si programare liniara (Introducere elementara), Ed. Tehnica, Bucuresti 1975.