Naslov
Savršeni grafovi
(Perfect graphs)

Autori
Dadić, Sara

Vrsta, podvrsta i kategorija rada
Ocjenski radovi, diplomski rad, diplomski

Fakultet
Prirodoslovno-matematički fakultet

Mjesto
Zagreb

Datum
06.09

Godina
2012

Stranica
38

Mentor
Krčadinac, Vedran

Ključne riječi
bojanje grafova ; kromatski broj ; savršen graf
(graph colouring ; chromatic number ; perfect graph)

Sažetak
Nakon iznošenja za ovaj rad nužnih pojmova teorije grafova, dokazana je veza između kromatskog broja i broja bridova. Opisan je algoritam bojanja koji neće koristiti više od $(\Delta + 1)$ boja te algoritam numeriranja koji omogućuje bojanje s ne više od $col(G)$ boja. Dana je karakterizacija broja $col(G)$ te dokazan Brooksov teorem koji tvrdi da za povezan graf koji nije potpun niti neparni ciklus vrijedi $\Xi(G)<=\Delta(G)$. Glavni dio rada odnosi se na savršene grafove za koje vrijedi da postižu trivijalnu donju ocjenu $\omega(G)$. Dani su primjeri savršenih i nesavršenih grafova te je pokazano za klasu bipartitnih i trianguliranih grafova da su savršene. Dokazan je teorem o savršenom grafu koji tvrdi da je svaki graf savršen ako i samo ako je njegov komplement savršen te je iznesen jedan od najznačajnijih rezultata u teoriji grafova koji kaže da savršene grafove možemo karakterizirati pomoću samo dva tipa zabranjenih induciranih podgrafova - neparnih ciklusa duljine barem 5 i njihovih komplemenata.

Izvorni jezik
Hrvatski

Znanstvena područja
Matematika

POVEZANOST RADA