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 cyklicky-4-súvislé grafy, 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, 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 nehemiltonovksé grafy. Keďže plantri generuje triangulácie, musel som problém previesť
do triangulácii. Planárna triangulácia obsahuje hamiltonovský cyklus vtedy a len vtedy ak vrcholy jej duálneho grafu
sa 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 drobnosti (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 sa ď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 -
neznedbateľ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.
Link na Github: https://github.com/FilipSivicek/plantri-nonhamiltonian/tree/main