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ų             32

Seminarų            

Pratybų              

laboratorinių darbų           

Konsultacijų                 

Kontroliniai darbai -

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 grafus.

Dalyko sando turinys

1. Kombinatorika ir grafų teorija.

Matematinės indukcijos principas. Dauginimo taisyklė. Gretiniai, kėliniai ir deriniai. Kartotiniai gretiniai ir deriniai. Binominių koeficientų tapatybės. Rėčio principas. Netvarkų uždavinys. Siurjekcijų skaičius. Stirlingo skaičiai. Skirtumo operatorius. Laipsninė generuojanti funkcija. Katalano skaičiai. Eksponentinė generuojanti funkcija. Rekurentieji sąryšiai. Fibonačio skaičiai. Bendra rekurenčiųjų sąryšių teorija. Sudėtinių funkcijų Tayloro koeficientai. Grandininės trupmenos.

2. Grafų teorija.

Pagrindinės sąvokos. Miškas ir medžiai. Optimizavimo problemų pavyzdžiai. Grafo parametrų ryšiai. Grafo planarumas. Grafo viršūnių spalvinimo problema. Medžių skaičius. Priūferio kodas. Gretimumo ir incidentumo matricos. Grafų teorijos ir algebros sąryšiai. Srauto tinkle problema.

Pagrindinės literatūros sąrašas

1.      M. Bloznelis, Kombinatorikos paskaitų ciklas, Vilniaus universiteto leidykla, 1996

2.      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ė

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

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

Papildomos literatūros sąrašas

1.      E.Manstavičius, Analizinė ir tikimybinė kombinatorika, Vilnius, TEV, 2008, 1 skyrius

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

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

Mokymo metodai

Paskaitos, jų metu pateikiami pavyzdžiai ir tipinių uždavinių sprendimas

Lankomumo reikalavimai

Pageidautina

Atsiskaitymo reikalavimai

Egzaminas. Mokėti įrodyti suformuluotus  teiginius, spręsti tipinius uždavinius ir žinoti pagrindines kombinatorinių objektų savybes bei pavyzdžius

Vertinimo būdas

Už pateiktų dviejų teiginių įrodymus po -3 balus, už uždavinį – 2, už apibrėžimus, testus ar pavyzdžius po 1 b.; egzamino pažymys lygus surinktų balų sumai.

Aprobuota katedros

2006 12 23

Patvirtinta Studijų programos komiteto

2007 04 23