Kriptomorfizmi matroida

master's thesis

• Author: Marija Ivančić
• Mentor: Vedran Krčadinac (mentor)
• Committee member: Vedran Krčadinac (predsjednik povjerenstva)
• Committee member: Sanja Varošanec (član povjerenstva)
• Committee member: Mea Bombardelli (član povjerenstva)
• Committee member: Juraj Šiftar (član povjerenstva)
• Granter: University of Zagreb; Faculty of Science; (Department of Mathematics); Zagreb
• Defense date and country: 2015-09-24, Croatia
• Scientific / art field, discipline and subdiscipline: NATURAL SCIENCES; Mathematics

Abstract

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.

Abstract (english)

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.

• Keywords: matroid; nezavisni skupovi; baze; ciklusi; funkcija ranga; ravnine; hiperravnine; operator zatvarača; kriptomorfizam; greedy algoritam
• Keywords (english): matroid; independent sets; bases; cycles; rank function; planes; hyperplanes; closure operator; cryptomorphism; greedy algorithm
• Language: croatian
• URN:NBN: urn:nbn:hr:217:196403
• Study programme: Title: Mathematics Education; specializations in: Mathematics Education; Course: Mathematics Education; Study programme type: university; Study level: graduate; Academic / professional title: magistar/magistra edukacije matematike (magistar/magistra edukacije matematike)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Open access
• Created on: 2019-01-30 13:14:57