Gomory-Hu drevesaŠETINA, TOMAŽ (Avtor) Fijavž, Gašper (Mentor) Gomory-Hu drevomaksimalni pretokminimalni prerezminimalni k-prerezdinamični grafiKlasični Ford-Fulkersonov rezultat zlepi problema maksimalnega u-v pretoka in minimalnega u-v prereza med izbranima vozliščema u in v v omrežju - uteženem grafu. V diplomski nalogi se ukvarjamo s problemom Gomory-Hu drevesa, ki v eni sami drevesni strukturi hrani informacijo o vseh minimalnih prerezih v grafu. Natančneje, iskanje minimalnega prereza med poljubnima vozliščema u in v v omrežju lahko predstavimo z iskanjem drevesne povezave z najmanjšo vrednostjo prepustnosti na edini poti med istima vozliščema v Gomory-Hu drevesu. V delu implementiramo Gusfieldov algoritem za izračun Gomory-Hu drevesa in ga časovno ovrednotimo. Zaradi velike časovne zahtevnosti izračuna Gomory-Hu drevesa implementiramo algoritem za dinamičen izračun novega drevesa iz obstoječega drevesa pri spremembi prepustnosti posamezne povezave v grafu G. Izkaže se, da je algoritem za izračun drevesa pri povečanju prepustnosti povezave v grafu G hitrejši v primerjavi z osnovnim algoritmom. V primeru zmanjšanja prepustnosti povezave ne pride do kvalitativnih razlik.20182018-05-18 11:50:03Diplomsko delo/naloga101264sl