Meno študenta:
Filip Siviček
Email:
sivicek3 zavinac uniba bodka sk
Meno školiteľa:
Mgr. Matúš Matok
Email:
matus bodka matok zavinac fmph bodka uniba bodka sk
Názov projektu:
Generovanie nehamiltonovských cyklicky-4-súvislých planárnych kubických grafov
Špecifikácia projektu:
V tomto ročníkovom projekte generujem grafy s určitými vlastnosťami.
Na generovanie grafov používam plantri.
Plantri je program, ktorý dokáže vygenerovať všetky planárne tirangulácie, veľkosti n.
Medzi grafmi, ktoré vygeneruje plantri sa nenachádzajú izomorfné grafy.
Ku každej planárnej triangulácii je jednoznačne určený duálny kubický graf.
Plán projektu: Najskôr som sa oboznámil s problematikou hamiltonovských grafov. Oboznámil som sa s nutnými a postačujúcimi podmienkami hamiltonovskosti grafom. Postačujúce podmienky hamiltonovskosti sa zameriavajú na husté grafy, takže sa nedajú aplikovať na kubické grafy. Overovať pomocou nutnej podmienky má časovu zložitosť O(2^(n/2)). Keďže sa zaoberám cyklicky-4-súvislými grafmi, tak určite nebudú mať most (hamiltonovské grafy nemôžu obsahovať mosty). Hamiltonovskosť nie je lokálna vlastnosť - keď si zoberiem ľubovoľný graf G, viem k nemu pridať vrcholy a hrany tak, aby nebol hamiltonovský (pridám 1 vrchol, ktorý spojím iba s jedným ďalším vrcholom) alebo tak, aby bol hamiltonovský (pridám V(G) + 1 vrcholov, ktoré spojím všetky medzi sebou a všetkými pôvodnými vrcholmi grafu).
Postup v projekte
Najskôr som sa naučil robiť s plantri. Keď už som vedel robiť s plantri, tak som spravil filter do plantri,
ktorý odfiltruje všetky nehemiltonovské grafy. Keďže plantri generuje triangulácie, musel som problém upraviť na ekvivalentný
problém pre trianglácie. Planárna triangulácia obsahuje hamiltonovský cyklus vtedy a len vtedy ak sa vrcholy jej duálneho grafu
dajú rozložiť na dva indukované stromy, zjednotenie ktorých vrcholov je celý duálny graf.
Na základe tohto som implementoval riešenie.
Rozdelenie na dva stromy som hľadal najskôr iba pomocou backtrackingu.
Vyskúšal som viacero iterácii - zmenil som v nich rôzne drobností (napr. posielam som informácie ako array vs ako int).
Potom som skúsil spraviť riešenie pomocou union-findu. Toto riešenie bolo oveľa rýchlejšie ako môj doterajší postup,
takže som ďalej pokračoval s ním. Filter mám momentálne dokončený. Využil som pri tom aj špecifiká plantri -
vďaka tomu ako plantri ukladá informácie o vrcholoch viem o niektrocých vrcholoch rýchlo povedať do ktorého stromu
musia patriť.
Momentálne analyzujem vnútornú štruktúru plantri aby som mohol mohol upraviť spôsob, akým plantri generuje planárne triangulácie -
nezanedbateľné množstvo plnanárnych triangulácii totiž obsahuje konfigurácie, ktoré určite nemôžu viesť k hamiltonovským grafom a chcel by
som sa vyhnúť ich generovaniu. Toto je práca na letný semester.
Letný semester V letnom semestri som sa detailnejšie zoznamoval s vnútornou štruktúrou a funkcionalitou plantri. Plantri rozpoznáva rovnaké triangulácie na základe toho, že majú rovnaký kanonický kód. Preštudoval som si, ako plantri vypočítava kanonický kód a naimplementoval som si vlastnú funkciu, ktorá ho počíta podobným spôsobom. Aby som sa lepšie naučil pracovať s plantri, naprogramoval som si vlastný filter na odfiltrovanie symetrických grafov, v ktorom som používal funkcie plantri na výpočet kanonického kódu. Podarilo sa mi nájsť neškodný memory leak, ktorý bol v plantri (zabudli zavrieť súbor, do ktorého zapisovali). Začal som pracovať na funkciach, ktorá budú generovať triedu grafov, v ktorej hľadám. Tých funkcií je 8 a začal s tým, že som sa pokúsil naprogramovať najťažšiu z nich, ktorá má interný názov operácia b. Momentálne sa snažím naprogramovať ju. Dokončiť všetky operácie (vrátane operácie b) bude práca na bakalárku.
Link na Github: https://github.com/FilipSivicek/plantri-nonhamiltonian/tree/main