Search

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. This thesis is a study of various definitions of matroids. Definitions that are equivalent, but the equivalence is not obvious, are called cryptomorphic. For the matroid M the following seven key concepts are defined: independent sets, bases, cycles, rank function, planes, hyperplanes and closure operator. First we define matroids in terms of independent sets and elaborate matroids coming from matrices and graphs. Then, we explain cryptomorphism between independent sets and bases, thus showing that a matroid can be defined in terms of bases. Next, cryptomorphisms between independent sets and cycles, between independent sets and rank function, rank function and closure operator, planes and closure operator, planes and hyperplanes are established. By establishing cryptomorphisms between these concepts it is shown that each of them can be used as a starting point in defining matroids. In the last chapter, independent sets of matroids are defined through the greedy algorithm. This connection gives us further insight into the importance and uniqueness of matroids.