Optimizacija na matroidu

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.In this thesis we introduced the basics of theory of matroids with emphasis on its application in optimization. We showed that a matroid, a structure based on an abstract notion of independence, is the natural structure behind the greedy algorithm. By showing that every matrix and graph is a matroid, we were able to define some optimization problems in terms of matroid theory and solve them by using appropriate variants of the greedy algorithm. Furthermore, by using duality theory in matroids, we defined the blue rule - red rule algorithm, an abstract variant of many greedy algorithms, especially useful in graph theory. To conclude, we introduced matroid intersection and described it in terms of graph theory and proved König's theorem