Gomory-Hu drevesa
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 prerez...
Main Author: | |
---|---|
Other Authors: | |
Format: | Bachelor Thesis |
Language: | Slovenian |
Published: |
2018
|
Subjects: | |
Online Access: | https://repozitorij.uni-lj.si/IzpisGradiva.php?id=101264 https://repozitorij.uni-lj.si/Dokument.php?id=111209&dn= |
id |
ftuniljubljanair:oai:repozitorij.uni-lj.si:IzpisGradiva.php-id-101264 |
---|---|
record_format |
openpolar |
spelling |
ftuniljubljanair:oai:repozitorij.uni-lj.si:IzpisGradiva.php-id-101264 2023-05-15T18:13:37+02:00 Gomory-Hu drevesa Gomory-Hu trees ŠETINA, TOMAŽ Fijavž, Gašper 2018-05-18 application/pdf https://repozitorij.uni-lj.si/IzpisGradiva.php?id=101264 https://repozitorij.uni-lj.si/Dokument.php?id=111209&dn= slv slv https://repozitorij.uni-lj.si/IzpisGradiva.php?id=101264 https://repozitorij.uni-lj.si/Dokument.php?id=111209&dn= info:eu-repo/semantics/openAccess 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 info:eu-repo/semantics/bachelorThesis info:eu-repo/semantics/publishedVersion 2018 ftuniljubljanair 2021-12-06T09:59:51Z 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. Bachelor Thesis sami Repository of the University of Ljubljana (RUL) |
institution |
Open Polar |
collection |
Repository of the University of Ljubljana (RUL) |
op_collection_id |
ftuniljubljanair |
language |
Slovenian |
topic |
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 |
spellingShingle |
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 ŠETINA, TOMAŽ Gomory-Hu drevesa |
topic_facet |
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 |
description |
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. |
author2 |
Fijavž, Gašper |
format |
Bachelor Thesis |
author |
ŠETINA, TOMAŽ |
author_facet |
ŠETINA, TOMAŽ |
author_sort |
ŠETINA, TOMAŽ |
title |
Gomory-Hu drevesa |
title_short |
Gomory-Hu drevesa |
title_full |
Gomory-Hu drevesa |
title_fullStr |
Gomory-Hu drevesa |
title_full_unstemmed |
Gomory-Hu drevesa |
title_sort |
gomory-hu drevesa |
publishDate |
2018 |
url |
https://repozitorij.uni-lj.si/IzpisGradiva.php?id=101264 https://repozitorij.uni-lj.si/Dokument.php?id=111209&dn= |
genre |
sami |
genre_facet |
sami |
op_relation |
https://repozitorij.uni-lj.si/IzpisGradiva.php?id=101264 https://repozitorij.uni-lj.si/Dokument.php?id=111209&dn= |
op_rights |
info:eu-repo/semantics/openAccess |
_version_ |
1766186198971187200 |