Naslov
Kriptomorfizmi matroida
(Cryptomorphisms of matroids)

Autori
Ivančić, Marija

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

Fakultet
Prirodoslovno-matematički fakultet- Matematički odsjek

Mjesto
Zagreb

Datum
24.09

Godina
2015

Stranica
73

Mentor
Krčadinac, Vedran

Ključne riječi
matroid ; kriptomorfizam
(matroid ; cryptomorphism)

Sažetak
U ovom diplomskom radu proučavamo razne definicije pojma matroida. Za definicije koje su međusobno ekvivalentne, ali ta ekvivalencija nije očita, kažemo da su kriptomorfne. Za matroid M definiramo sedam ključnih pojmova: nezavisni skupovi, baze, ciklusi, funkcija ranga, ravnine, hiperravnine i operator zatvarača. Najprije definiramo matroid preko nezavisnih skupova i upoznajemo matroide nastale iz matrica i iz grafova. Zatim uspostavljamo kriptomorfizam između nezavisnih skupova i baza i na taj način pokazujemo da matroid možemo definirati i preko baza. Navodimo i kriptomorfizme između nezavisnih skupova i ciklusa, između nezavisnih skupova i funkcije ranga, funkcije ranga i operatora zatvarača, ravnina i operatora zatvarača, ravnina i hiperravnina. Uspostavljanjem kriptomorfizma između tih pojmova pokazujemo da se svaki od tih pojmova može koristiti kao polazište u definiranju matroida. U posljednjem poglavlju, nezavisne skupove matroida definiramo preko greedy algoritma. Ta veza daje nam dodatan uvid u važnost i posebnost matroida.

Izvorni jezik
Hrvatski

Znanstvena područja
Matematika

POVEZANOST RADA