| Algoritmica grafelor | Algorithms of graphs theory |
trul |
|||||
(Mathematics Economics) |
| Cadre didactice indrumatoare | Teaching Staff in Charge |
| Prof. Dr. KASA Zoltan, kasa@cs.ubbcluj.ro Conf. Dr. TOADERE Teodor, toadere@cs.ubbcluj.ro |
| Obiective | Aims |
|
- Prezentarea notiunilor de teoria grafurilor - Dobandirea de catre studenti a unui instrument de modelare a problemelor din diferite domenii (productie sau stiinta). - Insusirea unor algorimi utili informaticienilor si nu numai lor. - Dezvoltarea calitatilor de programator prin realizarea de programe pentru algoritmi de rezolvare a unor probleme din teoria grafelor. |
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.
|
|
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, 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, 5. Fluxuri si retele de transport: definitii de baza, algoritmul lui Ford-Fulkerson, extensii ale algoritmului lui Ford-Fulkerson, fluxuri de cost minim. 6. Cuplaje in grafe: definitii, algoritm pentru determinarea unui arbore alternant, algoritm pentru determinarea cuplajului maxim, algoritm pentru determinarea cuplajului de pondere maxima. LABORATOR 1. Program pentru un algoritm de conversie a reprezentarii unui graf; 2. Program pentru un algoritm de optimizare pe multime de drumuri intr-un graf; 3. Rezolvarea unei probleme de ordonantare; 4. Program pentru determinarea unui arbore de acoperire si de pondere minima pentru un graf dat; 5. Program pentru determinarea unui flux maxim intr-un graf; 6. Procedura pentru determinarea unui arbore alternant de radacina data intr-un graf; 7. Program pentru determinarea unui cuplaj maxim intr-un graf. |
|
1. Berge C., Graphes et hypergraphes, Dunod, Paris 1970.
2. Berge C., Teoria grafurilor si aplicatiile ei, Ed. Tehnica, 1972 3. Cataranciuc S., Iacob M.E., Toadere T., Probleme de teoria grafelor, Lito. Univ. Cluj-Napoca, 1994. 4. Croitoru C., Optimizare multicriteriala, Ed.Univ."Al.I.Cuza", Iasi 1992. 5. Gondran M., Minoux, M.: Graphes et algorithmes, Paris 1979. 6. Moldovan Gr.: Bazele Informatice II, Lito. Univ. Cluj-Napoca. 7. Rosu A.: Teoria grafelor, algoritmi, aplicatii. Ed. Milit.1974 8. Kasa Z., Tartia C., Tambulea L.: Culegere de probleme de teoria grafelor, Lito. Univ. Cluj-Napoca 1979. 9. Toadere T: Elemente de teoria grafelor, Lito. Univ. "Babes-Bolyai" din Cluj-Napoca 1992. 10. Tomescu I., Introducere in combinatorica.Ed. Tehica 1972 11. Tomescu I., Grafuri si programare liniara. Introducere elementara. Ed. Did. si Pedag. Bucuresti 1975. 12. Tomescu I., Probleme de combinatorica si teoria grafurilor. Ed. Did. si Pedag. Bucuresti 1981. |
| Evaluare | Assessment |
|
Examen oral. Nota este obtinuta reflecta gradul de insusire a teoriei predate, a deprinderilor de aplicare a algoritmilor si activitatea de laborator (corectitudinea si consistenta programelor, elaborarea documentatiilor). |
Exam. |