Matroid

Из Википедије, слободне енциклопедије

Matroid je 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.

Temin „matroid“ je uveo Vitni Hasler. 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 MG=(SG,IG), koji je definisan pomoću pojma neorijentisanog grafa G=(V,E), gde je:

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

Teorema 1[уреди]

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

Dokaz[уреди]

Očigledno je da je SG=E – konačan skup. Osim toga IG – 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.
Na taj način ostaje nam da pokažemo da struktura MG odgovara osobini zamene. Pretpostavimo da su GA=(V,A) i GB=(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 GA ima V| - |A| drveta, a šuma GB ima V| - |B| drveta.
Ukoliko šuma GB ima manje drveta od šume GA tada u šumi GA postoji drvo T čiji vrh (pripada) predstavlja kraj dva različita drveta šume GA. 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 GA. Ukoliko ivica (u,v) spaja vrhove dvaju različitih drveta šume GA tada je možemo dodati u šumu GA ne obrazujući krug na taj način. Na taj način strutura MG zadovoljava osobinu zamene, čime se završava dokaz da je MG – matroid.
Za zadati matroid M=(S,I) definišimo elemenat x∈A kao proširenje, 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 MG. 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.
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 MG vezanog sa neorijentisanim grafom G. Svaki maksimalni nezavisni podskup matroida MG 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 grafa G.
Kažemo da je matroid M=(S,I) težinski, 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:
w(A)= ∑ w(x), x∈A, za proizvoljni podskup A⊆S,
npr. ako sa w(e) označimo dužinu ivice e matroida grafa MG, 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 978-0-262-53016-3, MR0290980 .
  • Geelen, Jim; Gerards, A. M. H.; Whittle, Geoff (2007), „Towards a matroid-minor structure theory“, in 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, pp. 72-82 .
  • 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, pp. 287-296 .
  • Kung, Joseph P. S., ed. (1986), A Source Book in Matroid Theory, Boston: Birkhäuser, ISBN 0-8176-3173-9 .
  • 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, 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, 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 .
  • 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, ed. (1986), Theory of Matroids, Encyclopedia of Mathematics and its Applications, 26, Cambridge: Cambridge University Press, ISBN 978-0-521-30937-0 .
  • White, Neil, ed. (1992), Matroid Applications, Encyclopedia of Mathematics and its Applications, 40, Cambridge: Cambridge University Press, ISBN 978-0-521-38165-9 .
  • 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“, Journal of Combinatorial Theory Series B 65 (2): 222-261, DOI:10.1006/jctb.1995.1052 .