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

Convexitate în grafe şi reţele
Cod
Semes-
trul
Ore: C+S+L
Credite
Tipul
Sectia
MI042
6
2+1+0
5
optionala
Informatică
Cadre didactice indrumatoare
Conf. Dr. TOADERE Teodor, toadere@cs.ubbcluj.ro
Obiective
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.
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
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.