Universitatea Babeş-Bolyai Cluj-Napoca
Facultatea de Matematică şi Informatică
Ciclul de studii: Licenţă
Domeniul: Informatică
Programul de studii: Informatică - linia de studiu română
Limba de predare: Română

SYLLABUS

I. Date generale
Codul	Disciplina	
MIG0001	Algoritmica grafelor	

Semestrul	Ore: C+S+L+P	Categoria	Statutul	
5	2+1+1+0	specialitate	obligatorie	

II. Cadre didactice cu norma de bază în Universitate
Numele şi	Titlul	Gradul	Catedra	Tipul activităţii	
prenumele	ştiinţific	didactic		C	S	L	
TOADERE Teodor	Dr. 	Conf.	Sisteme Informatice	*			

Cadre didactice asociate
Numele şi	Titlul	Instituţia	Tipul	Tipul activităţii	
prenumele	ştiinţific		postului	C	S	L	

III. Obiectivele disciplinei
- Prezentarea notiunilor de teoria grafelor
- Dobandirea de catre studenti a unui instrument de modelare a problemelor din diferite domenii.
- Insusirea si programarea unor algorimi din teoria grafelor.	

IV. Conţinutul disciplinei
1. Notiuni de baza: multigraf orientat, neorientat, graf, subgraf, graf partial, drum, circuit, lant, ciclu (simplu, elementar, eulerian, hamiltonian), reprezentari ale grafelor (geometric, matricial, cu dictionare), grafe tare conexe, conexe (alg. pentru determinarea componentelor conexe).
2. Drumuri in grafe: lungimea unui drum (matricea distantelor, centru, raza, diametru), valoarea unui drum, optimizari in multimea drumurilor, algoritmul lui Moore-Dijkstra, algoritmul lui Bellman-Kalaba, algoritmul lui Ford, algoritmi matriceali (Floyd-Hu, Dantzig, Floyd-Hu-Warshall), drum critic, drumuri Euleriene, drumuri Hamiltoniene.
3. Numere fundamentale in teoria grafelor: numar de stabilitate interna, algoritm pentru determinarea multimilor interior stabile, numar de stabilitate externa, algoritm pentru determinarea multimilor exterior stabile, numar cromatic, numar ciclomatic.
4. Arbori si paduri: notiuni generale, algoritmii lui Kruskal si Prim. 
5. Grafe planare
6. Fluxuri in retele de transport: definitii de baza, algoritmul lui Ford-Fulkerson, extensii ale algoritmului lui Ford-Fulkerson, fluxuri de cost minim.
7. Cuplaje in grafe: definitii, algoritm pentru determinarea cuplajului maxim, algoritm pentru determinarea cuplajului de pondere maxima.
8. Probleme extremale (teoremele lui Ramsey si Turán)
9. Probleme de numarare si enumerare.	

V. Bibliografie
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.

VI. Tematica activităţilor didactice pe săptămâni
Laborator:
1.	Conversia reprezentarii unui graf dintr-o forma in alta forma;
2.	Dererminarea: valorii minime/maxime a drumurilor de la  vf. p la vf.q folosind si diferiti algorimi (Moore-Dijkstra, Bellman-Kalaba, Ford, Yen, Floyd-Warshall-Hu)  sau determinarea numarului de drumuri de lungime min/max de la vf. p la vf. q folosind si diferiti algorimi;
3.	Determinarea razei, diametrului sau centrului unui graf, unui ciclu hamiltonian de valoare minima, graficului de realizare a activitatilor unui obiectiv pentru problema ordonantarii, a activitatilor critice sau a unui drum critic;
4.	Determinarea unei MIS/MES maxime(maximala)/minima(minimala), a tuturor MIS/MES sau a numerelor de stabilitate interna/externa
5.	Determinarea unui arbore de pondere minima cu unul din cei cinci algoritmi predati la curs;
6.	Determinarea unui flux maxim, taieturi de capacitate minima sau program de transport de cost minim;
7.	Determinarea unui cuplaj maxim.	

VII. Metode didactice folosite

VIII. Evaluare
Verificare in timpul anului + examen scris
Nota finala:
  nota la seminar si lucrari de laborator  40%
  nota la examen scris                     60%	

IX. Bibliografie suplimentară

	Decan,							Sef de catedra,

	Data,							Titular curs,
								Conf. Dr.  TOADERE Teodor