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.      P. Tannenbaumas, R. Arnoldas, Kelionės šiuolaikinę matematiką, TEV, Vilnius, 1995.

Mokymo metodai

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

Lankomumo reikalavimai

Pageidautina

Atsiskaitymo reikalavimai

Įskaita. 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ždavinį – 2, už apibrėžimus, testus ir pavyzdžius po 1 b.; įskaita – už 4 balus.

Aprobuota katedros

2004 10 04

Patvirtinta Studijų programos komiteto

2004 11 09