Naslov
Problem maksimalnih klika i Kellerova slutnja
(The maximum clique problem and Keller's conjecture)

Autori
Smoljak, Ksenija

Vrsta, podvrsta i kategorija rada
Ocjenski radovi, diplomski rad

Fakultet
Prirodoslovno matematički fakultet - Matematički odjel

Mjesto
Zagreb

Datum
10.07

Godina
2007

Stranica
42

Mentor
Krčadinac, Vedran

Ključne riječi
maksimalna klika ; Kelerova slutnja
(maximum clique ; Keller's conjecture)

Sažetak
U prvom poglavlju opisan je problem maksimalnih klika. Poglavlje započinje definicijom problema i opisom ekvivalentnih formulacija problema, te opisom njegove težine. U nastavku se navode važnije primjene i algoritmi za računanje maksimalnih klika. Na kraju poglavlja opisan je jedan konkretan algoritam i rezultati njegovog testiranja na slučajnim grafovima. Drugo poglavlje posvećeno je jednoj od primjena problema maksimalnih klika, Kellerovoj slutnji. Veći dio ovog poglavlja posvećen je svođenju Kellerove slutnje na problem maksimalnih klika. Poglavlje zaključuje testiranje algoritma, opisanog u prvom poglavlju, na Kellerovim grafovima. Radu je priložen dodatak u kojem je dana implementacija algoritma u programskom jeziku C++.

Izvorni jezik
Hrvatski

Znanstvena područja
Matematika

POVEZANOST RADA