Kombinatorika (7)

Įvadas. Grafai. Bendros žinios apie grafus. Bendrieji elementai bei teiginiai. Grafų duomenų struktūros. Grafų saugojimo būdai. Nekryptinių grafų saugojimo ypatumai. Tinklinių uždavinių tipai. Minimalios kainos srauto uždaviniai (minimum cost problem). Maksimalaus srauto problema (max flow). Trumpiausio kelio problema. Porų kombinacijų radimo uždaviniai. Tarpusavio ryšys tarp uždavinių. Algoritmo projektavimas ir analizė. Sudėtingumo analizė. Empirinė analizė. Apibendrinto vidutiniško atvejo analizė. Blogiausio atvejo analizės metodas. Susietumas algoritmo sudėtingumo su sprendžiama problema. Potencinės funkcijos metodo taikymas algoritmų sudėtingumo analizei. Parametrų balansavimo metodas. Jo taikymas algoritmų sudėtingumo analizei. Polinominiai ir eksponentiniai algoritmai. Algoritmų analizės ypatumai. Sveikas skaitmeninis tiesinis programavimas (SSTP). Apribojimų matricos unimoduliarumas. Tiesinio programavimo algoritmų taikymas kombinatorikos uždavinių sprendimui. Minimalaus karkaso uždaviniai. Įvadas. Bendrasis uždavinio formulavimas. Teoriniai algoritmų kūrimo pagrindai. Minimalaus karkaso radimo algoritmai. Kruskalo algoritmas. Primo algoritmas. Sollin algoritmas. Trumpiausio kelio uždavinių klasė. Pagrindinės prielaidos. Trumpiausių kelių užd. tipai. Dvi pagrindinės algoritmų grupės. Algoritmų kūrimo teorinės prielaidos. Dikstros algoritmas. Algoritmo sudėtingumas. Atbulinis Disktros algoritmas. Dvikryptis Dikstros algoritmas. Trumpiausi keliai: žymių korekcijos algoritmai. Žymių korekcijos algoritmų kūrimo teorinės prielaidos. Apibendrintas žymių korekcijos algoritmas. Modifikuotas žymių korekcijos algoritmas. Žymių korekcijos algoritmas, k-io sudėtingumas o(nm). Neigiamų ciklų išaiškinimas. Minimalaus kainos ir laiko santykio uždavinio sprendimas. Algoritmo sudarymo strategijos. Visų trumpiausių kelių uždavinių grupė (all pairs shortest path). Teorinės algoritmo kūrimo prielaidos. Floyd - Worshall algoritmas visų porų trumpiausiems keliams rasti. Maksimalūs srautai. Uždavinio formulavimas. Teorinės prielaidos. Kelio ieškojimo mechanizmas. Žymėjimo algoritmas maksimaliam srautui rasti. Ford-Fulhemon algoritmas.