| Meno: | Peter
|
|---|
| Priezvisko: | Glaus
|
|---|
| Názov: | Minimálne hranové rezy v hyperkockách
|
|---|
| Vedúci: | Doc. RNDr. Rastislav Kráľovič, PhD.
|
|---|
| Rok: | 2007
|
|---|
| Kľúčové slová: | delenie grafu na k častí, minimálny rez hyperkocky, heuristika, distribuované výpočty
|
|---|
| Abstrakt: | V úlohe nájdenia minimálneho k-rezu grafu sa snažíme rozdelit graf na k
súvislých komponentov odobraním hrán najmenšej váhy. Pri neohodnotenom
grafe sa snažíme minimalizovat pocet odobraných hrán. V tejto práci
sa zameriame na neohodnotené grafy a na konkrétnu podmnožinu grafov -
hyperkocky. Dalšie zúženie problému bude spocívat vo velkosti komponentov.
Snažíme sa nájst minimálne rozdelenie n-rozmernej hyperkocky na k
komponentov, ktorých velkost sa líši o konštantu. Ciastocne nadviažeme na
výsledky z [Bez96], kde teóriou dokázali dolné ohranicenie a pre niektoré k
aj zodpovedajúce horné ohranicenie.
V práci sú použité dva rôzne algoritmické prístupy k riešeniu úlohy. Jeden
je heuristické simulované žíhanie prispôsobené na problém minimálneho
delenia. Druhý problém využíva optimálne podgrafy, ktoré sa snaží ukladat
do hyperkocky. Pre vhodné n tieto výsledky doplnajú teoretické výsledky z
práce Sergeia Bezrukova [Bez96].
|
|---|