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.Š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
Grafy bez indukovaných cyklov danej dĺžky
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.
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