Naslov
Optimizacija na matroidu
(Optimization on matroids)

Autori
Badrov, Nikola

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

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

Mjesto
Zagreb

Datum
24.02

Godina
2017

Stranica
35

Mentor
Krčadinac, Vedran

Ključne riječi
matroid ; optimizacija
(matroid ; optimization)

Sažetak
U ovom smo radu izložili osnove teorije matroida s naglaskom na primjene u optimizaciji. Pokazali smo da je matroid, struktura utemeljena na apstrahiranom pojmu nezavisnosti, prirodna struktura u pozadini pohlepnog algoritma. Dokazavši da je svaka matrica i graf matroid, definirali smo neke optimizacijske probleme u terminima teorije matroida te ih riješili koristeći odgovarajuće varijante pohlepnog algoritma. Nadalje, koristivši dualnu teoriju matroida, definirali smo algoritam plavog pravila i crvenog pravila, apstrahiranu varijantu mnogih pohlepnih algoritama, naročito koristan u teoriji grafova. Na kraju smo uveli pojam presjeka matroida te ga protumačili u terminima teorije grafova te dokazali Königov teorem.

Izvorni jezik
Hrvatski

Znanstvena područja
Matematika

POVEZANOST RADA