Dalyko sando kodas

KGTE7124

Dalyko sando pavadinimas

Grafų teorija

Dėstytojo (-jų) pedagoginis vardas, mokslo laipsnis, vardas ir pavardė

prof. hab. dr. Eugenijus Manstavičius

Katedra, centras

Tikimybių teorijos ir skaičių teorijos

Fakultetas, padalinys

Matematikos ir informatikos fakultetas

Dalyko sando lygis

antrosios pakopos

Semestras

rudens (1)

ECTS kreditai

4,5

VU kreditai

3

Auditorinės valandos

viso dalyko 48

Paskaitų 48

seminarų

pratybų

laboratorinių darbų

konsultacijų

Reikalavimai

Kombinatorika

Dėstomoji kalba

lietuvių

Dalyko sando tikslai ir numatomi gebėjimai

Supažindinti su šiuolaikiniais asimptotiniais ir tikimybiniais metodais

Dalyko sando turinys

1. Pagrindinės grafų teorijos sąvokos. Keliai, grandys, Eulerio ir Hamiltono grafai.
2. Medżiai ir jų charakteristikų skaičiavimas.
3. Grafų plokštumas ir dualumas. Eulerio formulė. Grafai paviršiuose. Begaliniai grafai.
4. Grafų spalvinimo problemos. Chromatiniai skaičiai. Bruko teorema. šiuolaikiniai chromatinių indeksų įverčiai. Atvaizdžių spalvinimas. Chromatiniai polinomai.
4. Orentuotieji grafai. Eulerio digrafai ir turnyrai.
5. Grafų teorijos ryšiai su Markovo grandinėmis.
6. Partnerių parinkimo problemos. Holo teorema.
7. Transversalumo teorija. Mengerio teorema.
8. Tinklai ir jų srautai.
9. Matroidų teorijos pradmenys. Jų ryšiai su grafais bei transversalumo teorija.
10. Šiuolaikiniai asimptotiniai ir tikimybiniai metodai grafų teorijoje bei kombinatorioje

Pagrindinės literatūros sąrašas

1.    R.WiIson, Introduction to Graph Theory, Longman, New York, 3rd edition, 1985.

2.    V.N.Sačkov, Įvadas į Kombinatorinius Diskrečios Matematikos Metodus, Nauka, Maskva, 1982 (rusų k.).

3.    P.Flajolet, A.Odlyzko, Singularity analysis of generating functions, SIAM J. of Discrete Math., 1990, (2), 216--240.

4.    E.Manstavičius, Additive and multiplicative functions on random permutations, Lietuvos Matem. Rink., 1996, bf 36(4), 501-511.

Papildomos literatūros sąrašas

C.Berge, Graphs, North-Holland, 1985

Mokymo metodai

paskaitos

Lankomumo reikalavimai

Pageidautina

Atsiskaitymo reikalavimai

Egzaminas raštu.

Vertinimo būdas

Atsakymų į egzamino klausimus teisingumo ir išsamumo vertinimas.

Aprobuota katedros

2004 10 04

Patvirtinta Studijų programos komiteto

2004 11 09