Fisa disciplinei MI042

Universitatea "Babeş-Bolyai" din Cluj-Napoca

Facultatea de Matematică şi Informatică
FISA DISCIPLINEI

Convexitate în grafe şi reţele Convexity in graphs and networks

Cod Semes-
trul Ore: C+S+L Credite Tipul Sectia

MI042 4 2+1+0 5 optionala Tehnologie Informatică
(College of Computer Technology)

MI042 6 2+1+0 5 optionala Informatică
(Computer Science)

Cadre didactice indrumatoare Teaching Staff in Charge

Conf. Dr. TOADERE Teodor, toadere@cs.ubbcluj.ro

Obiective Aims

Formarea unei gandiri abstracte si familiarizarea cu domeniul analizei convexe in spatii metrice finite, grafe si retele. Cursul este conceput ca o paralela intre rezultatele din literatura, obtinute pentru grafe si cele obtinute de autor pentru retele, in domeniul analizei convexe.
To achieve basic knowledges in the domain of convex analysis on metric spaces, finite metric spaces, graphs and networks. The lessons are conceived to be a parallel between the results obtained for graphs in convex analysis and the same theory in networks.

Continut

1. Grafe, Retele: definitii, tipuri, reprezentari;
2. Matrici asociate unui graf;
3. Distanta in grafe si retele. Segmente metrice.
4. Multimi d-convexe in grafe si retele, invelitoarea convexa a unei multimi de virfuri;
5. Puncte extremale si puncte expuse, Proprietati de separare;
6. Clase de functii convexe pe grafe si pe retele, Proprietati supremale, de aditivitate si de separare;
7. Algoritmi de minimizare a functiilor convexe pe grafe si retele;
8. Probleme de optim pe grafe si retele.

Bibliografie

1. H.-J. Bandelt, Graphs with intrinsec S3 Convexities, J. Graph Theory, 13(2), 1989, 215-228.
2. P.M. Dearing, R.L. Francis, T.J. Lowe, Convex loction problems on tree networks, Oper. Res., 24, 1976, 628-634.
3. P. Duchet, H. Meyniel, Ensemble Convexes dans les Graphes. Theoremes de Helly et de Radon pour Graphes et Surfaces, Europ. J. Combinatorics, 4, 1983, 127-132.
4. M.G. Everett, S.B. Seidman, The hull number of a graph, Disc. Math., 57, 1985, 217-223.
5. M. Farber, R.E. Jamison, Convexity in graphs and hypergraphs, SIAM J. Alg. Disc. Meth., 7, 1986, 433-444.
6. M. Farber, R.E. Jamison, On local convexity in graphs, Disc. Math., 66, 1987, 231-247.
7. M. Gondran, M. Minoux, Graphes et Algorithmes, Eyrolles, Paris, 1979.
8. F. Harary, J. Nieminen, Convexity in graphs, J. Diff. Geom., 16, 1981, 185-190.
9. M.E. Iacob, Convexitate, Aproximare si Optimizare pe Retele, Teza de doctorat, Universitatea Babes-Bolyai, 1997.
10. V.P. Soltan, V.D. Chepoi, Some classes of convex functions in graphs, Dokl. Akad. Nauk. SSSR, 273, 1983, 1314-1317.
11. A. Sochirca, V.P. Soltan, d-Convex functions in graphs, Mat. Issled, 11, 1988, 93-106.
12. V.P. Soltan, Introduction to Axiomatic Convexity Theory, Stiinta, Chisinau, 1984 (rusa).
13. V.P. Soltan Some properties of convex functions I, II, Amer. Math. Transl., 134 (2), 1987, 39-51.
14. V.P. Soltan, Metric convexity in graphs, Studia Univ. Babes-Bolyai Math., XXXVI (4), 1991, 3-43.

Evaluare Assessment

Nota este media aritmetica a unei note pe care studentul o obtine in urma sustinerii unui examen oral la sfarsitul semestrului si a unei note pe care studentul o obtine in urma prezentarii in cursul semestrului la seminar a unui referat pe o tema data cu bibliografie precizata.
Each student must get two marks: one for the presentation of an essay on a given subject (using a given bibliography) during the semester and the other for an exam at the end of the semester. The final mark is the mean value of the previous two marks.