Matroid

Matroid uređeni par M=(S,I) formiran na sledeći način:

1. Skup S je konačan.
2. Neka je I – neprazna familija podskupova skupa S ( koji se nazivaju nezavisnim podskupovima ) takvih da ako je B∈I i A⊆B, tada je A∈I. Ako familija I zadovoljava ovu osobinu tada je nazivamo nasleđenom (HERADITARY). Primetimo da prazan skup Ø obavezno pripada familiji I.
3. Ako je A∈I, B∈I i |A| < |B|, tada postoji element x∈A-B, tako da je A∪{x}∈I. Govorimo da struktura M zadovoljava osobinu zamene (EXCHANGE PROPETY).

Temin “MATROID” je uveo Vitni Hasler (HASSLER WHITNEY). On je proučavao matrične matroide, čiji su elementi S redovi zadate matrice. Skup redova je nazavistan, ako su oni linearno nezavisni u običnom smislu. Lako se pokazuje da ova struktura definiše matroid.

Kao suštinu drugog primera matroida razmotrimo matroid grafa M_G=(S_G,I_G), koji je definisan pomoću pojma neorijentisanog grafa G=(V,E), gde je:

• S_G – skup E ivica grafa G,
• Ako je A – podskup skupa E, tada je A I_G tada i samo tada kada je A necikličan tj, skup ivica A je nezavistan tada i samo tada kada podgraf G_A=(V,A) obrazuje šumu.

Teorema 1.

Ako je G=(V,E) – neorijentisani graf tada je MG=(S_G,I_G) – matroid.

Dokaz:

Očigledno je da je S_G=E – konačan skup. Osim toga I_G – je nasledna familija ukoliko je podskup šume takođe šuma. Drugim rečima, odstranjivanje ivica iz acikličnog skupa ivica grafa ne može dati cikličan skup.<br\>

Na taj način ostaje nam da pokažemo da struktura M_G odgovara osobini zamene. Pretpostavimo da su G_A=(V,A) i G_B=(V,B) šume grafa G i da je |A| < |B| , tj. A i B su aciklični skupovi ivica, i da u skupu B ima više ivica nego u skupu A. Iz jedne od teorema koje su ranije razmatrane sledi da šuma u kojoj imamo k ivica ima tačno {V} -k drveta . Da to dokažemo pođimo od |V| drveta od kojih svako ima samo jedan vrh i ne sadrži ni jednu ivicu. Tada svako rebro (ivica) koje se dodaje šumi, za jedan smanjuje broj drveta. Na taj način šuma G_A ima |V| - |A| drveta , a šuma G_B ima |V| - |B| drveta.<br\>

Ukoliko šuma G_B ima manje drveta od šume G_A tada u šumi G_A postoji drvo T čiji vrh (pripada) predstavlja kraj dva različita drveta šume G_A. Više od toga, ako je drvo T na taj način povezano, ono mora da sadrži ivicu (u,v) tako da vrhovi u i v pripadaju različitim drvima šume G_A. Ukoliko ivica (u,v) spaja vrhove dvaju različitih drveta šume G_A tada je možemo dodati u šumu G_A ne obrazujući krug na taj način. Na taj način strutura M_G zadovoljava osobinu zamene, čime se završava dokaz da je M_G – matroid.<br\>

Za zadati matroid M=(S,I) definišimo elemenat x∈A kao proširenje (EXTENSION)), skupa A∈I, ako je njega moguće dodati u A bez narušavanja nezavisnosti tj. x – je proširenje skupa A ako je A∪{x}∈I. Kao primer razmotrimo matroid grafa M_G. Ako je A – nezavisni skup ivica, tada je ivica e proširenje skupa A tada I samo tada ako ne pripada tom skupu i ako njeno dodavanje skupu ne dovodi do stavranja ciklusa.<br\>

Ako je A – nezavistan podskup u matroidu M, i ako u njemu nema proširenja (nisu moguća) tada kažemo da je A maksimalan skup. Na taj način, skup A je maksimalan ako se ne sadrži ni u jednom većem podskupu matroida M. Dole data osobina je često vrlo korisna.

Teorema 2.

Svi maksimalni nezavisni podskupovi matroida imaju istu veličinu.

Dokaz:

Teoremu dokazujemo metodom suprotnosti. Pretpostavimo da je A – maksimalan nezavistan podskup matroida M i da postoji drugi maksimalni nezavisni podskup B matroida M čija je veličina veća od veličine podskupa A. Tada iz osobine zamene sledi da skup A proširujemo do većeg nezavisnog skupa A∪{x} na račun nekog elementa x∈B-A što protivureči pretpostavci o maksimalnosti skupa A.

Kao ilustraciju primene ove teoreme razmotrimo primenu matroida grafa M_G vezanog sa neorijentisanim grafom G. Svaki maksimalni nezavisni podskup matroida M_G mora da bude (da predstavlja) slobodno drvo koje ima tačno |V| - 1 ivica koje spajaju vrhove grafa G. Takvo drvo se zove osnovno drvo (SPANNING TREE) grafa G.<br\>

Kažemo da je matroid M=(S,I) težinski (WEIGHTED), ako je sa njim povezana težinska funkcija w koja svakom elementu x∈S određuje strogo pozitivnu težinu w(x). Težinska funkcija w se uopštava na podskupove skupa S putem sumiranja:<br\>

w(A)= ∑ w(x), x∈A, za proizvoljni podskup A⊆S,<br\>

npr. ako sa w(e) označimo dužinu ivice e matroida grafa M_G , tada je w(A) – ukupan dužina svih ivica koje pripadaju skupu A.

Види још

• Теорија графова
• Похлепни алгоритам

Литература

• Bruhn, Henning; Diestel, Reinhard; Kriesell, Matthias; Wollan, Paul (2010), Axioms for infinite matroids .
• Bryant, Victor; Perfect, Hazel (1980), Independence Theory in Combinatorics, London and New York: Chapman and Hall, ISBN 0-412-22430-5 .
• Brylawski, Thomas H. (1972), „A decomposition for combinatorial geometries”, Transactions of the American Mathematical Society, American Mathematical Society, 171: 235–282, doi:10.2307/1996381 .
• Crapo, Henry H. (1969), „The Tutte polynomial”, Aequationes Mathematicae, 3 (3): 211–229, doi:10.1007/BF01817442 .
• Crapo, Henry H.; Rota, Gian-Carlo (1970), On the Foundations of Combinatorial Theory: Combinatorial Geometries, Cambridge, Mass.: M.I.T. Press, ISBN 9780262530163, MR0290980 .
• Geelen, Jim; Gerards, A. M. H.; Whittle, Geoff (2007), „Towards a matroid-minor structure theory”, Ур.: Grimmett, Geoffrey (ed.); et al., Combinatorics, Complexity, and Chance: A Tribute to Dominic Welsh, Oxford Lecture Series in Mathematics and its Applications, 34, Oxford: Oxford University Press, стр. 72–82 CS1 одржавање: Експлицитна употреба et al. (веза)CS1 одржавање: Текст вишка: списак уредника (веза).
• Gerards, A. M. H. (1989), „A short proof of Tutte's characterization of totally unimodular matrices”, Linear Algebra and Applications, 114/115: 207–212, doi:10.1016/0024-3795(89)90461-8 .
• Kahn, Jeff; Kung, Joseph P. S. (1982), „Varieties of combinatorial geometries”, Transactions of the American Mathematical Society, American Mathematical Society, 271 (2): 485–499, doi:10.2307/1998894 .
• Kingan, Robert; Kingan, Sandra (2005), „A software system for matroids”, Graphs and Discovery, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, стр. 287–296 .
• Kung, Joseph P. S., ур. (1986), A Source Book in Matroid Theory, Boston: Birkhäuser, ISBN 0-8176-3173-9, MR0890330 .
• Mac Lane, Saunders (1936), „Some interpretations of abstract linear dependence in terms of projective geometry”, American Journal of Mathematics, The Johns Hopkins University Press, 58 (1): 236—240, doi:10.2307/2371070 .
• Oxley, James (1992), Matroid Theory, New York: Oxford University Press, ISBN 0-19-853563-5, MR1207587 .
• Recski, András (1989), Matroid Theory and its Applications in Electric Network Theory and in Statics, Berlin and Budapest: Springer-Verlag and Akademiai Kiado, ISBN 3-540-15285-7, MR1027839 .
• Seymour, Paul D. (1980), „Decomposition of regular matroids”, Journal of Combinatorial Theory, Series B, 28 (3): 305–359, doi:10.1016/0095-8956(80)90075-1 .
• Truemper, Klaus (1992), Matroid Decomposition, Boston: Academic Press, ISBN 0-12-701225-7, MR1170126 .
• Tutte, W. T. (1959), „Matroids and graphs”, Transactions of the American Mathematical Society, American Mathematical Society, 90 (3): 527—552, doi:10.2307/1993185, MR0101527 .
• Tutte, W. T. (1965), „Lectures on matroids.”, Journal of Research of the National Bureau of Standards (U.S.A.), Sect. B, 69: 1–47 .
• Tutte, W. T. (1971), Introduction to the Theory of Matroids, New York: American Elsevier .
• Vámos, Peter (1978), „The missing axiom of matroid theory is lost forever”, Journal of the London Mathematical Society, II. Ser., 18: 403—408, doi:10.1112/jlms/s2-18.3.403 .
• van der Waerden, B. L. (1937), Moderne Algebra .
• White, Neil, ур. (1986), Theory of Matroids, Encyclopedia of Mathematics and its Applications, 26, Cambridge: Cambridge University Press, ISBN 9780521309370 .
• White, Neil, ур. (1992), Matroid Applications, Encyclopedia of Mathematics and its Applications, 40, Cambridge: Cambridge University Press, ISBN 9780521381659 .
• Whitney, Hassler (1935), „On the abstract properties of linear dependence”, American Journal of Mathematics, The Johns Hopkins University Press, 57 (3): 509—533, doi:10.2307/2371182, MR1507091 . pp. 55–79.
• Whittle, Geoff (1995), „A characterization of the matroids representable over GF(3) and the rationals” (PDF), Journal of Combinatorial Theory Series B, 65 (2): 222–261, doi:10.1006/jctb.1995.1052 .