Universitatea Babeş-Bolyai Cluj-Napoca
Facultatea de Matematică şi Informatică
Ciclul de studii: Licenţă

FISA DISCIPLINEI

Codul
Denumirea disciplinei
MIG0001 Algoritmica grafelor
Specializarea
Semestrul
Ore: C+S+L+P
Statutul
Informatică
3
2+1+1+0
obligatorie
Matematică informatică - linia de studiu maghiară
Matematică informatică - linia de studiu română
5
2+1+1+0
optionala
Titularii de disciplina
Prof. Dr. KASA Zoltan,  kasacs.ubbcluj.ro
Conf. Dr. TOADERE Teodor,  toaderecs.ubbcluj.ro
Lect. Dr. LUPSA Radu,  rlupsacs.ubbcluj.ro
Lect. Dr. OLAH-GAL Robert,  robert.olah-galcs.ubbcluj.ro
Lect. Dr. EGRI Edith,  egrieditcs.ubbcluj.ro
Obiective
- 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.
Célkitűzések
- Gráfelméleti alapokkal való megismerkedés
- A különbözo területeken fellépo problémák gráfok segítségével való modellezésének elsajátítása
- A gráfelméletben fellépo egyes algoritmusok ismertetése és azok programozása
Aims
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.
Continutul
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.

Laborator:
Conversia reprezentarii unui graf dintr-o forma in alta forma;
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;
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;
Determinarea unei MIS/MES maxime(maximala)/minima(minimala), a tuturor MIS/MES sau a numerelor de stabilitate interna/externa
Determinarea unui arbore de pondere minima cu unul din cei cinci algoritmi predati la curs;
Determinarea unui flux maxim, taieturi de capacitate minima sau program de transport de cost minim;
Determinarea unui cuplaj maxim.
Tartalom
1. Gráfokkal modellezheto feladatok, alapfogalmak: irányított és irányítatlan gráf, egyszeru gráf, részgráf, séta, vonal, út, kör, lánc, Euler kör, Hamilton kör, gráfok ábrázolása (grafikusan, mátrixokkal, listával), összefüggo gráf, erosen összefüggo gráf (összefüggo komponensek algoritmusa), útmátrix, centrum, sugár, átméro.
Gráfok mélységi és szélességi bejárásainak algoritmusai
3. Legrövidebb utak nem súlyozott gráfokban (Moore algoritmusa). Legrövidebb utak súlyozott gráfokban: egy csúcsból minden csúcsba (Dijkstra, ill. Ford algoritmusa).
4. Legrövidebb utak súlyozott gráfokban: minden csúcsból egy csúcsba (Bellman-Kalaba), minden csúcsból minden csúcsba (Floyd-Warshall) Az algoritmusok bonyolultsága.
5. A kritikus út módszere
6. Euler- és Hamilton gráfok (Fleury algoritmusa, Hamilton út és kör keresése)
7. Fák és ligetek. Gyökeres fák, bináris fák, gazdaságos feszítofák. Kruskal algoritmusa minimális feszítofa meghatározására. Prim algoritmus
8. Prüfer-kód. Huffman algoritmusa.
9. Síkba rajzolható gráfok. Kuratowski tétele. Duális gráfok. Keresztezési szám.
10. Folyamfeladatok: a hálózati folyam és a vele kapcsolatos fogalmak ismertetése. Ford-Fulkerson algoritmus és elemzése.
11. Általánosított folyam. Minimális költségu maximális folyam. Busacker-Saaty tétele.
12. Páros gráfok, optimális hatásfokú foglalkoztatás. Módszerek maximális párosítás keresésére páros gráfokban: alternatív utak módszere, folyam segítsége, független 1-esek módszere. Minmális értéku maximális párosítás.
13. Szélsoérték feladatok - extrémgráfok. Bennfoglalás és kizárás elve. Zarankiewicz, Ramsey és Turán tétele.
14. Gráfok színezése, függetlencsúcs-halmazok, kromatikus polinom.
Content
basic graph theory definitions (graph, multigraph, directed graph/multigraph, walk, trail, path), representations; week 1-2.
path-related problems: connected and strongly-connected graphs, connected components, shortest path, Moore, Bellman-Kalaba, Dijkstra, Floyd-Warshal algorithms; week 3-4.
partial ordering, critical path; topological sorting and PERT method; week 5-6.
trees and forests; Kruskal and Prim algorithms; graph traversal and applications; week 7.
hard problems (clique, independent set, vertex covering, coloring, Hamiltonian cycle, traveling salesman problem); weeks 8-9
Eulerian cycle; week 10
planar graph; week 10
transport networks and flows; maximum flow problems; matching problems; week 11-12
counting and enumerating problems; week 13-14
extremal problems; week 14
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, Mtszaki 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.
Evaluare
Verificare in timpul anului + examen scris
Nota finala:
nota la seminar si lucrari de laborator 40%
nota la examen scris 60%
Felmérés
év közben
félévi zárthelyi dolgozat írása
labor feladatok idobeni leadása, szemináriumi tevékenység értékelése (óránként)
félév végén: írásbeli és gyakorlati vizsga
Végso jegy: az év közben szerzett jegy, illetve a félév végén kapott jegy egyenlo arányban számít bele
Assessment
Practical work + exam
1/3 practical work
2/3 written exam
See also: http://www.cs.ubbcluj.ro/~rlupsa/edu/grafe/requirements.html
Syllabus-urile tuturor disciplinelor