Universitatea "Babes-Bolyai" Cluj-Napoca
Facultatea de Matematica si Informatica
FISA DISCIPLINEI

Structuri de date şi algoritmica grafelor
Cod
Semes-
trul
Ore: C+S+L
Credite
Tipul
Sectia
MI014
5
2+1+1
5
optionala
Matematică-Informatică
MI014
5
2+1+1
5
optionala
Matematică-Informatică
Cadre didactice indrumatoare
Prof. Dr. KASA Zoltan, kasa@cs.ubbcluj.ro
Conf. Dr. TOADERE Teodor, toadere@cs.ubbcluj.ro
Obiective
- Prezentarea notiunilor de teoria grafurilor si a structurilor de adte
- Dobandirea de catre studenti a unui instrument de modelare a problemelor din diferite domenii.
Continut
0. Principalele structuri de date.
1. Notiuni de baza in teoria grafurilor.
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, algoritmul lui Kruskal. Aplicatii la structuri de date.
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 unui arbore alternant, algoritm pentru determinarea cuplajului maxim, algoritm pentru determinarea cuplajului de pondere maxima.
Bibliografie
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.
Evaluare
Examen oral.