Diskrētā matemātika

"Studiju kursa ietvaros studējošie apgūst tēmas: bināras attieksmes, kombinatorikas elementi, rekurentie

vienādojumi, grafu teorijas pamati. Kursa ietvaros studējošie pielieto iegūtās zināšanas praktisko

uzdevumu risināšanā."

"1. Kopas un attieksmes.

Kopas jēdziens. Kopu uzdošanas veidi. Operācijas ar kopām. Bināras attieksmes jēdziens.

Operācijas ar binārām attieksmēm. Bināru attieksmju veidi un īpašības. Ekvivalences un

kopu sadalījumi. Faktorkopas. Sakārtotas kopas. Elementu salīdzināšana sakārtotās kopās.

Funkcijas. Injekcija, sirjekcija un bijekcija. Kopas apjoms. Sanumurējamās kopas.

Kontinuālas kopas.

2. Kombinatorika.

Reizināšanas likums. Variācijas ar atkārtojumiem. Variācijas bez atkārtojumiem.

Permutācijas. Kombinācijas bez atkārtojumiem. Kombinācijas ar atkārtojumiem.

Substitūciju grupa. Binomiālkoeficienti un to īpašības. Binomiālā formula.

Veidotājfunkcijas. Ieslēgšanas un izslēgšanas formula. Rekurentie vienādojumi. Fibonači

un Lukasa skaitļi. Stirlinga skaitļi. Katalāna skaitļi. Nesakrišanu skaitļi. Sadalījumu skaitļi.

Bernulli un Eilera skaitļi.

3. Grafu teorija.

Grafa jēdziens. Grafu izomorfisms. Vienkāršākie objekti grafos. Grafu veidi. Operācijas ar

grafiem. Grafu pieraksts datorā. Grafi un bināras attieksmes.

Sakarīga grafa jēdziens. Sakarīguma komponentes. Virsotņu sakarīguma skaitlis. Šķautņu

sakarīguma skaitlis. Mezgls. Tilts. K-sakarīgi grafi. Menģera teorēma. Holla teorēma.

Maksimālā plūsma. Īsākais maršruts.

Koku jēdziens. Koku īpašības. Orientēti, sakārtoti un bināri koki. Koku pieraksts datorā.

Šķirošanas koki. Minimālā svara koks.

Eilera grafi. Eilera teorēma. Flerī algoritms. Eilera ķēde. Puseilera grafi. Puseilera grafa

kritērijs. Hamiltona grafi. Uzdevums par ceļojošo tirgoni.

Neatkarīgums un pārklājumi. Grafa minimālais pārklājums.

Grafa pareizs izkrāsojums. Hromatiskais skaitlis un tā novērtējumi. Planāru grafu virsotņu

krāsojums piecās krāsās. Četru krāsu problēma.

"