Ročníkový projekt

Študent: Adrián Goga
email: adriangoga0 AT gmail DOT com

Vedúci projektu: RNDr. Robert Lukoťka PhD.
email: lukotka AT dcs DOT fmph DOT uniba DOT sk

Téma

Grafy bez indukovaných cyklov danej dĺžky

Cieľ

Nech G je graf a nech A V(G). Graf G[A], ktory obsahuje vrcholy z A a hrany, ktoré majú obidva konce v A, sa nazýva indukovaný podgraf G indukovaný množinou vrcholov A.

Indukovaná kružnica v grafe G je kružnica, ktorá je zároveň indukovaným podgrafom G.

Cieľom ročníkového projektu je vytvoriť program pomocou ktorého bude na malych grafoch možné overiť platnosť nasledujúcich hypotéz:
1. Ak G nemá indukovanú kružnicu dĺžky 3k, pre žiadne k N, tak potom existuje hrana e E(G) taká, že G-e nemá indukovanú kružnicu dĺžky 3k, pre žiadne k N.
2. Ak G nemá indukovanú kružnicu dĺžky 2k+1, pre žiadne k N, tak potom existuje hrana e E(G) taká, že G-e nemá indukovanú kružnicu dĺžky 2k+1, pre žiadne k N.

Špecifikácia

Tento program má zároveň umožovať nasledujúce veci:

- Generovať všetky grafy na danom počte vrcholov, ktoré nemajú indukováné kružnice daných dĺžok (ideálne generovať iba neizomorfné grafy).

- Pre daný graf overiť, či obsahuje indukovanú kružnicu s dĺžkou z X, kde X je množina hodnôt daná na vstupe

- Pre daný graf G nájsť hranu e, takú, že G-e neobsahuje indukovanú kružnicu s dĺžkou z X , kde X je množina hodnôt daná na vstupe


Zdrojový kód:

github