| Meno: | Matúš
|
|---|
| Priezvisko: | Kókai
|
|---|
| Názov: | 1-faktorizácie na hyperkockách a star grafoch
|
|---|
| Vedúci: | doc. RNDr. Rastislav Královič PhD.
|
|---|
| Rok: | 2010
|
|---|
| Blok: | INF
|
|---|
| Kľúčové slová: | 1-faktorizácia, semi-perfektnosť, hyperkocka, star graf, izomorfizmus, heuristika
|
|---|
| Abstrakt: | V diplomovej práci sa zaoberáme problematikou generovania neizomorfných 1-faktorizácií (t.j. partícií hrán na perfektné párovania, 1-faktory) na regulárnych grafoch. Práca prináša základný prehľad pojmov, techník a dosiahnutých výsledkov v oblasti. Špeciálne sa zameriavame na hyperkocky a star grafy. Našim hlavným cieľom je navrhnutie algoritmov pre generovanie perfektných a semi-perfektných 1-faktorizácii na hyperkockách a star grafoch nižších dimenzií, ako aj implementácia heuristických metód do navrhnutých algoritmov. Na základe výsledkov testovania rôznych heuristík následne navrhujeme ich optimálnu kombináciu pre uvažované grafy vyšších dimenzií. Ďalším cieľom práce je nájdenie semi-perfektných a perfektných 1-faktorizacii na hyperkockách a star grafoch pomocou našich
algoritmov. Súčasťou práce je aj program vhodný na testovanie a vyhodnocovanie účinnosti jednotlivých heuristických metód.
|
|---|