Изворни код странице Matroid

'''Matroid''' je [[uređeni par]] <math>M = (S, \mathcal{I} ) </math> formiran na sledeći način:
# [[Skup]] <math>S</math> je konačan.
# Neka je <math> \mathcal{I} </math> neprazna familija podskupova skupa <math>S</math> (koji se nazivaju nezavisnim podskupovima) takva da ako je <math> B \in \mathcal{I} </math> i <math> A \subseteq B </math>, tada je <math> A \in \mathcal{I} </math>. Ako familija <math> \mathcal{I} </math> zadovoljava ovu osobinu tada je nazivamo nasleđenom (''Hereditary''). Primetimo da prazan skup <math> \varnothing </math> obavezno pripada familiji <math>\mathcal{I} </math>.
# Ako je <math>A \in \mathcal{I}, B \in \mathcal{I} </math> i <math>|A| < |B|</math>, tada postoji element <math> x \in B \setminus A </math>, takav da je <math> A \cup \{ x \} \in \mathcal{I} </math>. Govorimo da struktura <math> M </math> zadovoljava osobinu zamene.

Termin „matroid“ je uveo Vitni Hasler. On je proučavao matrične matroide, čiji su elementi <math> S </math> redovi zadate matrice. Skup redova je nezavisan, 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 [[graf]]a <math> M_G = (S_G, \mathcal{I}_G) </math>, koji je definisan pomoću pojma neorijentisanog grafa <math>G = (V, E)</math>, gde je:
* <math> S_G </math> skup <math> E </math> ivica grafa <math> G </math>,
* Ako je <math> A </math> podskup skupa <math> E </math>, tada je <math> A \in \mathcal{I}_G </math> ako i samo ako je <math> A </math> necikličan tj, skup ivica <math> A </math> je nezavisan ako i samo ako podgraf <math> G_A = (V, A) </math> obrazuje šumu.

== Teorema 1 ==
Ako je <math>G = (V, E)</math> neorijentisan konačan graf tada je <math> M_G = (S_G, \mathcal{I}_G) </math> matroid.

=== Dokaz ===
:Očigledno je da je <math>S_G = E</math> konačan skup. Osim toga <math> \mathcal{I}_G </math> je nasledna familija jer 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 <math> M_G </math> odgovara osobini zamene. Pretpostavimo da su <math>G_A = (V, A)</math> i <math>G_B = (V, B)</math> šume grafa <math>G</math> i da je <math> |A| < |B| </math> , tj. <math>A</math> i <math>B</math> su aciklični skupovi ivica, i da u skupu <math>B</math> ima više ivica nego u skupu <math>A</math>. Iz jedne od teorema koje su ranije razmatrane sledi da šuma u kojoj imamo <math>k</math> ivica ima tačno <math>|V| - k</math> drveta. Da to dokažemo pođimo od <math>|V|</math> 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 <math>G_A</math> ima <math>|V| - |A|</math> drveta, a šuma <math>G_B</math> ima <math>|V| - |B|</math> drveta.

:Kako šuma <math>G_B</math> ima manje drveta od šume <math>G_A</math> tada u šumi <math>G_B</math> postoji ivica <math>(u, v)</math> takva da se vrhovi <math>u</math> i <math>v</math> nalaze u dva različita drveta šume <math>G_A</math>. Pošto ova ivica spaja vrhove dvaju različitih drveta šume <math>G_A</math> tada je možemo dodati u šumu <math>G_A</math> ne obrazujući krug na taj način. Na taj način struktura <math>M_G</math> zadovoljava osobinu zamene, čime se završava dokaz da je <math>M_G</math> matroid.

Za zadati matroid <math>M = (S, \mathcal{I} ) </math> definišimo element <math>x \in A</math> kao proširenje skupa <math>A \in \mathcal{I} </math>, ako je njega moguće dodati u <math>A</math> bez narušavanja nezavisnosti tj. <math>x</math> je proširenje skupa <math>A</math> ako je <math>A \cup \{ x \} \in \mathcal{I} </math>. Kao primer razmotrimo matroid grafa <math>M_G</math>. Ako je <math>A</math> nezavisan skup ivica, tada je ivica <math>e</math> proširenje skupa <math>A</math> ako i samo ako ne pripada tom skupu i ako njeno dodavanje skupu ne dovodi do stvaranja ciklusa.

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

== Teorema 2 ==
Svi maksimalni nezavisni podskupovi matroida imaju istu veličinu. 

=== Dokaz: ===
:Teoremu dokazujemo metodom svođenja na protivrečnost. Pretpostavimo da je <math>A</math> maksimalan nezavisan podskup matroida <math>M</math> i da postoji drugi maksimalni nezavisni podskup <math>B</math> matroida <math>M</math> čija je veličina veća od veličine podskupa <math>A</math>. Tada iz osobine zamene sledi da skup <math>A</math> možemo proširiti do većeg nezavisnog skupa <math>A \cup \{ x \} </math> pomoću nekog elementa <math> x \in B \setminus A </math> što je suprotno pretpostavci o maksimalnosti skupa <math>A</math>.

Kao ilustraciju primene ove teoreme razmotrimo primenu na matroid grafa <math>M_G</math> vezanog za neorijentisani povezani graf <math>G</math>. Svaki maksimalni nezavisni podskup matroida <math>M_G</math> mora da bude (da predstavlja) slobodno drvo koje ima tačno <math>|V| - 1</math> ivica koje spajaju vrhove grafa <math>G</math>. Takvo drvo se zove osnovno drvo grafa <math>G</math>.

Kažemo da je matroid <math>M = (S, \mathcal{I} ) </math> težinski, ako je sa njim povezana težinska funkcija <math>w</math> koja svakom elementu <math>x \in S</math> pridružuje strogo pozitivnu težinu <math>w(x)</math>. Težinska funkcija <math>w</math> se uopštava na podskupove skupa <math>S</math> putem sumiranja:

:<math>w(A) = \sum_{x \in A} w(x) </math> za proizvoljni podskup <math>A \subseteq S</math>.

Na primer, ako sa <math>w(e)</math> označimo dužinu ivice <math>e</math> matroida grafa <math>M_G</math>, tada je <math>w(A)</math> ukupna dužina svih ivica koje pripadaju skupu <math>A</math>.

== Види још ==
* [[Теорија графова]]
* [[Похлепни алгоритам]]

== Литература ==
{{Литература|2}}
* {{citation |last=Bruhn |first=Henning |last2=Diestel |first2=Reinhard |last3=Kriesell |first3=Matthias |last4=Wollan |first4=Paul |class=math.CO |title=Axioms for infinite matroids |year=2010}}.
* {{Cite book|ref=harv|last=Bryant|first=Victor|last2=Perfect|first2=Hazel|year=1980|title=Independence Theory in Combinatorics|url=https://archive.org/details/independencetheo0000brya|publisher=Chapman and Hall|location=London and New York|isbn=978-0-412-22430-0|pages=}}.
* {{citation|last=Brylawski|first=Thomas H.|year=1972|title=A decomposition for combinatorial geometries|journal=Transactions of the American Mathematical Society|volume=171|doi=10.2307/1996381|url=http://jstor.org/stable/1996381|publisher=American Mathematical Society|pages=235-282}}.
* {{citation|last=Crapo|first=Henry H.|year=1969|title=The Tutte polynomial|journal=Aequationes Mathematicae|volume=3|issue=3|doi=10.1007/BF01817442|pages=211-229}}.
* {{Cite book|ref=harv|last=Crapo|first=Henry H.|last2=Rota|first2=Gian-Carlo|year=1970|title=On the Foundations of Combinatorial Theory: Combinatorial Geometries|url=https://archive.org/details/onfoundationsofc00crap|publisher=M.I.T. Press|location=Cambridge, Mass.|isbn=978-0-262-53016-3|id={{MR|0290980}}|pages=}}.
* {{citation|last=Geelen|first=Jim|last2=Gerards|first2=A. M. H.|last3=Whittle|first3=Geoff|year=2007|contribution=Towards a matroid-minor structure theory|editor=Grimmett, Geoffrey (ed.) |title=Combinatorics, Complexity, and Chance: A Tribute to Dominic Welsh|series=Oxford Lecture Series in Mathematics and its Applications|volume=34|publisher=Oxford University Press|publication-place=Oxford|pages=72-82}}. 
* {{citation|last=Gerards|first=A. M. H.|year=1989|title=A short proof of Tutte's characterization of totally unimodular matrices|journal=Linear Algebra and Applications|volume=114/115|doi=10.1016/0024-3795(89)90461-8|pages=207-212}}.
* {{citation|last=Kahn|first=Jeff|last2=Kung|first2=Joseph P. S.|year=1982|title=Varieties of combinatorial geometries|journal=Transactions of the American Mathematical Society|volume=271|doi=10.2307/1998894|url=http://jstor.org/stable/1998894|issue=2|publisher=American Mathematical Society|pages=485-499}}.
* {{citation|last=Kingan|first=Robert|last2=Kingan|first2=Sandra |year=2005|contribution=A software system for matroids|title=Graphs and Discovery|series=DIMACS Series in Discrete Mathematics and Theoretical Computer Science|pages=287-296}}.
* {{Cite book|ref=harv|editor-last=Kung|editor-first=Joseph P. S.|title=A Source Book in Matroid Theory|url=https://archive.org/details/sourcebookinmatr0000kung|publisher=Birkhäuser|id={{MR|0890330}}|isbn=978-0-8176-3173-4|location=Boston|year=1986|pages=}}.
* {{citation|last=Mac Lane|first=Saunders|year=1936|title=Some interpretations of abstract linear dependence in terms of projective geometry|journal=American Journal of Mathematics|volume=58|doi=10.2307/2371070|url=http://jstor.org/stable/2371070|issue=1|publisher=The Johns Hopkins University Press|pages=236-240}}.
* {{Cite book|ref=harv|last=Oxley|first=James|year=1992|title=Matroid Theory|url=https://archive.org/details/matroidtheory0000oxle|publisher=Oxford University Press|location=New York|isbn=978-0-19-853563-8|id={{MR|1207587}}|pages=}}.
* {{Cite book|ref=harv|last=Recski|first=Andr&aacute;s|year=1989|title=Matroid Theory and its Applications in Electric Network Theory and in Statics|url=https://archive.org/details/matroidtheoryits0000recs|publisher=Springer-Verlag and Akademiai Kiado|location=Berlin and Budapest|isbn=978-3-540-15285-9|id={{MR|1027839}}|pages=}}.
* {{citation|last=Seymour|first=Paul D.|year=1980|title=Decomposition of regular matroids|journal=Journal of Combinatorial Theory, Series B|volume=28|issue=3|doi=10.1016/0095-8956(80)90075-1|pages=305-359}}.
* {{Cite book|ref=harv|last=Truemper|first=Klaus|title=Matroid Decomposition|publisher=Academic Press|id={{MR|1170126}}|location=Boston|year=1992|isbn=978-0-12-701225-4|url=http://www.emis.de/monographs/md/index.html|pages=}}.
* {{citation|last=Tutte|first=W. T.|year=1959|title=Matroids and graphs|journal=Transactions of the American Mathematical Society|volume=90|id={{MR|0101527|pages=527-552}}|doi=10.2307/1993185|url=http://jstor.org/stable/1993185|issue=3|publisher=American Mathematical Society}}.
* {{citation|last=Tutte|first=W. T.|year=1965|title=Lectures on matroids.|journal=Journal of Research of the National Bureau of Standards (U.S.A.), Sect. B|volume=69|pages=1-47}}. 
* {{citation|last=Tutte|first=W. T.|year=1971|title=Introduction to the Theory of Matroids|location=New York|publisher=American Elsevier}}.
* {{citation|last=Vámos|first=Peter|year=1978|title=The missing axiom of matroid theory is lost forever|journal=Journal of the London Mathematical Society, II. Ser.|volume=18|doi=10.1112/jlms/s2-18.3.403|pages=403-408}}.
* {{citation|last=van der Waerden|first=B. L.|year=1937|title=Moderne Algebra}}.
* {{Cite book|ref=harv|editor-last=White|editor-first=Neil|year=1986|title=Theory of Matroids|series=Encyclopedia of Mathematics and its Applications|volume=26|publisher=Cambridge University Press|location=Cambridge|isbn=978-0-521-30937-0|pages=}}.
* {{Cite book|ref=harv|editor-last=White|editor-first=Neil|year=1992|title=Matroid Applications|series=Encyclopedia of Mathematics and its Applications|volume=40|publisher=Cambridge University Press|location=Cambridge|isbn=978-0-521-38165-9|pages=}}.
* {{citation|last=Whitney|first=Hassler|year=1935|title=On the abstract properties of linear dependence|journal=American Journal of Mathematics|volume=57|id={{MR|1507091|pages=509-533}}|doi=10.2307/2371182|url=http://jstor.org/stable/2371182|issue=3|publisher=The Johns Hopkins University Press|pages=55–79}}.
* {{citation|last=Whittle|first=Geoff|year=1995|title=A characterization of the matroids representable over ''GF''(3) and the rationals|journal=Journal of Combinatorial Theory Series B|volume=65|issue=2|url=http://eprints.kfupm.edu.sa/39296/1/39296.pdf|doi=10.1006/jctb.1995.1052|pages=222-261}}{{Мртва веза|date=08. 2018. |bot=InternetArchiveBot |fix-attempted=yes }}.
{{рефенд}}

{{normativna kontrola}}

{{СОРТИРАЊЕ:Матроид}}
[[Категорија:Linearna algebra]]
[[Категорија:Теорија матроида]]