Dalyko sando kodas

KGTE2114

Dalyko sando pavadinimas

Kombinatorika ir grafų teorija

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

Profesorius, habilituotas daktaras

Eugenijus Manstavičius

Katedra, centras

Tikimybių teorijos ir skaičių teorijos

Fakultetas, padalinys

Matematikos ir informatikos fakultetas

Dalyko sando lygis

Pirmosios pakopos

Semestras

Pavasario (2) 

ECTS kreditai

3

VU kreditai

2

Auditorinės valandos

viso dalyko         32

Paskaitų             16

Seminarų            

Pratybų               16

laboratorinių darbų           

Konsultacijų                 

Kontroliniai darbai - 1

Koliokviumai -

Reikalavimai

Matematinės analizės ir algebros pradmenys

Dėstomoji kalba

Lietuvių

Dalyko sando tikslai ir numatomi gebėjimai

Išmokyti kombinatorikos pradmenų, pagrindinius kombinatorinių objektų suskaičiavimo bei sąryšių analizės principus. Suteikti pagrindinių žinių apie grafusir digrafus

Dalyko sando turinys

Matematinės indukcijos principas. Dauginimo taisyklė. Gretiniai, kėliniai ir deriniai. junginiai su pasikartojančiais elementais. Binominių koeficientų tapatybės. Rėčio principas. Netvarkų uždavinys. Siurjekcijų skaičius. Stirlingo skaičiai. Rutulių-dėžių problemos. Laipsninės generuojančios funkcijos. Katalano skaičiai. Fibonačio skaičiai. Bendra tiesinių rekurenčiųjų sąryšių teorija.

Pagrindinės sąvokos. Miškas ir medžiai. Oilerio ir Hamiltono grafai. Optimizavimo problemų pavyzdžiai. Grafo parametrų ryšiai. Grafo planarumo ir viršūnių spalvinimo problemos. Medžių skaičius. Priūferio kodas. Ciklomatis digrafo skaičius. Gretimumo ir incidentumo matricos. Srauto tinkle problema.

Pagrindinės literatūros sąrašas

1.      E. Manstavičius, Diskrečioji matematika (kombinatorikos ir grafų teorijos pradmenys): paskaitų konspektas, Matematikos ir informatikos fakultetas Tikimybių teorijos ir skaičių teorijos katedra, 2000; e-svetainė.

2.      E.Manstavičius, Analizinė ir tikimybinė kombinatorika, Vilnius, TEV, 2007, 1 dalis.

3.      K.Plukas, E.Mačikėnas, B.Jarašiūnienė, I.Mikuckienė, Taikomoji diskrečioji matematika, Technologija, Kaunas, 2005.

4.  G.P.Gavrilov, A.A. Sapoženko, Diskrečiosios matematikos uždavinynas, Nauka, Maskva, 1977 (rusų k.)

Papildomos literatūros sąrašas

1.      N.L.Biggs, Discrete Mathematics, Oxford Univ. Press, 2nd edn, 2002.

2.      P.J. Cameron, Combinatorics: Topics, Techniques, Algorithms, Cambridge Univ. Press, 1994; http://www.maths.qmul.ac.uk/pjc/comb.

3.      R. Wilson, Introduction to Graph Theory, Longman, 1985 (yra vertimas į rusų k.)

4.  V.N. Sačkov, Įvadas į kombinatorinius diskrečios matematikos metodus, Nauka, Maskva, 1982 (rusų k.)

Mokymo metodai

Paskaitų metu išdėstomi pagrindiniai teoriniai klausimai; pratybų metu studentai sprendžia tipinius uždavinius.

Lankomumo reikalavimai

Privaloma 90%

Atsiskaitymo reikalavimai

Egzaminas raštu. Mokėti įrodyti suformuluotą teiginį, spręsti tipinius uždavinius ir žinoti pagrindines kombinatorinių objektų savybes bei pavyzdžius.

Vertinimo būdas

Už pateikto teiginio įrodymą –3 balai, už uždavinius – 1 ar 2 balai, už apibrėžimus, testus ar pavyzdžius po 1 b.. Egzamine iki 2 balų įskaitoma už kontrolinį ir 1 balas –už gerą pasirodymą pratybų metu.

Aprobuota katedros

2006 12 23

Patvirtinta Studijų programos komiteto

2010 03 22