Meno študenta: Jakub Vaňko
Email: vankojakub17@gmail.com
Vedúci projektu: doc. RNDr. Robert Lukoťka, PhD.
Email: lukotka@dcs.fmph.uniba.sk
Názov projektu: Hľadanie hamiltonovských a skoro hamiltonovských kružníc v kubických grafoch
Špecifikácia projektu (zimný semester):
Základným cieľom projektu je prehľadať všetky kubické planárne beztrojuholníkové grafy do 26 vrcholov a vyhľadať v nich dvojice (G, e) s vlastnosťou -
žiadna hamiltonovská kružnica v G neobsahuje e (všetky planárne grafy do 26 vrcholov majú hamiltonovskú kružnicu).
Na tomto výrazne zredukovanom zozname následne vykonať niekoľko podobných výpočtov (napr. nájsť takmer hamiltonovskú kružnicu vynechávajúcu daný vrchol).
Zmenená špecifikácia projektu (letný semester): Základným cieľom projektu je prehľadať všetky 3-súvislé a 4-súvislé bipartitné grafy do určitého počtu vrcholov, ktorý bude závisieť od dostupnej výpočtovej sily. Pri vyšších počtoch vrcholov grafov by sa prehľadávanie mohlo uskutočňovať niekoľko dní, či týždňov. My sa uspokojíme s časom prehľadávania radovo v hodinách. V každom takomto bipartitnom grafe budeme hľadať hranu, ktorá sa nenachádza v žiadnom hamiltonovskom cykle daného grafu.
Report
GitHub
Ukážka vygenerovaných 4-súvislych bipartitných kubických grafov
Ukážka vygenerovaných 3-súvislych bipartitných kubických grafov a ich hamiltonovských cyklov