20.500.12556/RUL-101264 Gomory-Hu drevesa Gomory-Hu trees Klasič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. The classical Ford-Fulkerson algorithm computes a maximum u-v flow and a minimum u-v cut between two selected nodes u, v from flow network - weighted graph. In this thesis we study Gomory-Hu trees which in one tree structure include information about all minimum in the graph. More precisely computing a minimum cut between a pair of nodes u and v nodes in flow network can be reduced to searching for an edge with smallest capacity in the unique u-v path in the Gomory-Hu tree. We implement and evaluate Gusfield algorithm for computing Gomory-Hu tree. The presented algorithm for computing Gomory-Hu trees has relatively high time complexity, so we also implement an algorithm for dinamically computing Gomory-Hu trees following a capacity change in the graph. It turns out that in the case of increasing capacity the dynamic approach outperforms the basic algorithm. However, we measure no substantial improvement in the case of reducing capacity of an edge. Gomory-Hu drevo maksimalni pretok minimalni prerez minimalni k-prerez dinamični grafi Gomory-Hu tree max flow min cut min k-cut dynamic graphs true false false Slovenski jezik Angleški jezik Diplomsko delo/naloga 2018-05-18 11:50:03 2018-05-18 11:50:06 2022-08-14 03:43:48 0000-00-00 00:00:00 2018 0 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 1970-01-01 21772 Setina_Tomaz_-_Gomory-Hu_drevesa.pdf Setina_Tomaz_-_Gomory-Hu_drevesa.pdf 1 02E10EB98EED23773A056011E88DF120 2cda5ce650c302547480f19de18a30ecd74865af1e69ac23d88b8716d6ca65f4 35cd3d55-a1b5-11eb-a523-00155dcfd717 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=111209 Fakulteta za računalništvo in informatiko 0 0 0