Dalyko sando kodas

GRTE3124

Dalyko sando pavadinimas

Grafų teorija

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

Doc. dr. Gintaras Skersys

Katedra, centras

Informatikos katedra

Fakultetas, padalinys

Matematikos ir informatikos fakultetas

Dalyko sando lygis

pirmosios pakopos

Semestras

rudens (5) 

ECTS kreditai

4,5

VU kreditai

3

Auditorinės valandos

viso dalyko 48

Paskaitų 32

seminarų

pratybų 16

laboratorinių darbų

konsultacijų

Reikalavimai

Nėra 

Dėstomoji kalba

lietuvių

Dalyko sando tikslai ir numatomi gebėjimai

Studentas pagilins grafų teorijos žinias, mokės taikyti teoriją praktiniams uždaviniams spręsti.

Dalyko sando turinys

Pagrindinės sąvokos, pavyzdžiai. Grafų veiksmai. Grafo parametrų sąryšiai. Grafo vaizdavimo kompiuteryje būdai. Grafo viršūnių peržiūros metodai. Oilerio ciklai. Keliaujančiojo pirklio uždavinys. Minimalaus tinklo uždaviniai. Chromatinis skaičius. Nepriklausomumo ir dominavimo skaičiai. Optimalių kelių ieškojimas. Jungumas. Maksimalaus suporavimo uždavinys. Grafo viršūnių laipsnių sekos.

Pagrindinės literatūros sąrašas

1.    K.Plukas, E.Mačikėnas, B.Jarašiūnaitė, I.Mikuckienė. Taikomoji diskrečioji matematika. Technologija, Kaunas, 2002.

2.    P.Tannenbaumas, R.Arnoldas, Kelionė į šiuolaikinę matematiką, TEV, Vilnius, 1995.

3.    E.Manstavičius. Grafų teorija. Paskaitų konspektas, Vilnius, 1999. http://www.mif.vu.lt/katedros/ttsk/bylos/man/man.html

4.    O.Ore. Graps and their uses. The Mathematical Association of America, Washington, 1990.

Papildomos literatūros sąrašas

1.    R.Wilson, Introduction to Graph Theory, Longman, 1985.

2.      F.A.Novikov. Diskrečioji matematika programuotojams. Piter, Sankt – Peterburgas, 2001(rusų k.).

3.      F.S.Roberts. Applied Combinatorics. Prentice – Hall, New Jersey, 1984.

Mokymo metodai

Dalį užsiėmimų veda dėstytojas, o dalis yra seminarų formos, kai studentai pristato kurią nors temą.

Lankomumo reikalavimai

-

Atsiskaitymo reikalavimai

Egzaminas, uždavinių sprendimas raštu.

Vertinimo būdas

Egzamino laikymas vertinamas iki 10 balų, seminaro vedimas – iki 2 balų. Galutinis įvertinimas yra tų dviejų įvertinimų suma (jei viršija 10, įvertinama 10).

Aprobuota katedros

2006 08 31

Patvirtinta Studijų programos komiteto

2006 09 25