نمایش مبدأ برای میتروید

{{short description|ساختار مجردی که استقلال خطی را مدلسازی کرده و تعمیم می دهد}}
در [[ترکیبیات]]، '''مِیتروید''' {{به انگلیسی|Matroid}} {{IPAc-en|ˈ|m|eɪ|t|r|ɔɪ|d}} (ممکن است در ترجمه ها به آن متروید، ماتروید و... هم گفته شود) ساختاری است که مفهوم [[استقلال خطی]] در [[فضای برداری|فضاهای برداری]] را تجرید سازی کرده و تعمیم می دهد. از نظر [[اصل موضوع (منطق)|اصول موضوعه]] منطقی، روش های بسیاری برای تعریف یک میتروید وجود دارد که مهم ترین آن ها ازین قرارند: براساس مجموعه ها؛ پایه ها و مدارها؛ توابع رتبه؛ عملگرهای بستار؛ مجموعه های بسته یا فلت‌ها. به زبان مجموعه های مرتب جزئی، یک میتروید متناهی معادل با مشبکه هندسی است.

نظریه میتروید به طور گسترده از واژگان [[جبر خطی]] و [[نظریه گراف]] وام گرفته، چرا که تجرید عمده مفاهیم مرکزی در این شاخه ها ما را به میتروید ها می رساند. میترویدها کاربردهایی در [[هندسه]]، [[توپولوژی]]، [[بهینه‌سازی ترکیبیاتی|بهینه سازی ترکیبیاتی]]، [[نظریه شبکه]] و [[نظریه کدگذاری|نظریه کد]] پیدا کرده اند.<ref name=Neel2009>{{cite journal|last1=Neel|first1=David L.|last2=Neudauer|first2=Nancy Ann|author2-link=Nancy Neudauer|title=Matroids you have known|journal=Mathematics Magazine|date=2009|volume=82|issue=1|pages=26–41|url=http://www.maa.org/sites/default/files/pdf/shortcourse/2011/matroidsknown.pdf|access-date=4 October 2014|doi=10.4169/193009809x469020|archive-date=۱۳ فوریه ۲۰۲۲|archive-url=https://web.archive.org/web/20220213204955/https://www.maa.org/sites/default/files/pdf/shortcourse/2011/matroidsknown.pdf|url-status=dead}}</ref><ref name=Kashyap2009>{{cite web|last1=Kashyap|first1=Navin|last2=Soljanin|first2=Emina|last3=Vontobel|first3=Pascal|title=Applications of Matroid Theory and Combinatorial Optimization to Information and Coding Theory|url=https://www.birs.ca/workshops/2009/09w5103/report09w5103.pdf|website=www.birs.ca|access-date=4 October 2014}}</ref>

==تعاریف==<!-- [[خاصیت موروثی (میتروید)]] به این زیربخش تغییر مسیر می دهد-->
طرق متنوعی برای تعریف میتروید (متناهی) وجود دارد که با هم [[رمزریختی|رمزریخت]] (کریپتومورف) هستند:<ref name="oxley">منبع استانداردی برای تعاریف و نتایج پایه در مورد میتروید، Oxley (1992) است. یک منبع قدیمی تر Welsh (1976) است. ضمیمه Brylawski را در White (1986)، صفحات 298-302 را برای لیستی از دستگاه های اصول موضوعه ای معادل ببینید.</ref>

===مجموعه‌های مستقل===
برحسب استقلال، یک میتروید متناهی <math>M</math> شامل زوج مرتب <math>(E,\mathcal{I})</math> است که <math>E</math> مجموعه ای متناهی (که به آن '''مجموعه زمینه''' گفته می شود) و <math>\mathcal{I}</math> خانواده ای از زیرمجموعه های <math>E</math> (که به آن '''مجموعه های مستقل''' گفته می شود) است که دارای خواص زیر باشد:<ref name="w7-9">{{harvtxt|Welsh|1976}}, Section 1.2, "Axiom Systems for a Matroid", pp. 7–9.</ref>

#[[مجموعه تهی]] مستقل است، یعنی <math>\emptyset\in\mathcal{I}</math>. یا به عباری، حداقل یکی از زیرمجموعه های <math>E</math> مستقل است، یعنی <math>\mathcal{I}\neq\emptyset</math>.
#هر زیرمجموعه از یک مجموعه مستقل، مستقل است، یعنی برای هر <math>A'\subseteq A\subseteq E</math>، اگر <math>A\in\mathcal{I}</math> آنگاه <math>A'\in\mathcal{I}</math>. این خاصیت را برخی مواقع '''خاصیت موروثی'''، یا خاصیت '''بسته از پایین''' نیز می گویند.
#اگر <math>A</math> و <math>B</math> دو [[مجموعه مستقل]] باشند (یعنی، هر مجموعه مستقل باشند) و <math>A</math> از <math>B</math> عناصر بیشتری داشته باشد، آنگاه وجود دارد <math>x\in A\setminus B</math> چنان که <math>B \cup \{x\}</math> در <math>\mathcal{I}</math> است. برخی اوقات به این خاصیت '''خاصیت افزودگی''' یا '''خاصیت تبادل مجموعه مستقل''' نیز می گویند. 

دو خاصیت اول ساختاری ترکیبیاتی به نام دستگاه استقلال (یا [[مجتمع سادکی]] مجرد) تعریف می کنند.

== نمونه‌ها ==
[[پرونده:Graf num edges letter nodes.png|بندانگشتی|مرتبط ]]
در [[نظریهٔ گراف]] می‌توانید یک گراف را بردارید و مجموعهٔ پس‌زمینه را مجموعهٔ گره‌های آن برداشته و یک مجموعه از این گره‌ها را وابسته در نظر بگیرید هر گاه یک دور در [[زیرگراف]] القا شده از این گره‌ها وجود داشته باشد. به این میتروید، میتروید گرافی می‌گویند.
در [[جبرخطی]] می‌توانید یک [[فضای برداری]] اتنخاب کرده و یک مجموعه بردار دلخواه از این فضا را به عنوان مجموعهٔ پس‌زمینه بردارید. یک مجموعه از این بردارها را وابسته گوئیم هر گاه وابستهٔ خطی باشند یعنی یک [[ترکیب خطی]] نابدیهی از آن‌ها صفر شود. به این میتروید، میتروید ماتریسی می‌گوئیم. علت این نامگذاری این است که می‌توان نمایش برداری این  بردارها را در نظر گرفته و با کنار هم قرار دادن آن‌ها یک ماتریس داشت که آنگاه مجموعهٔ پس‌زمینهٔ ما گردایهٔ ستون‌های این ماتریس است.
در [[جبرجابجایی]] می‌توان رابطهٔ وابستگی میتروید را وابستگی جبری در نظر گرفت.

== کاربرد ==
به‌طور کلی داشتن ساختار میترویدی در یک بحث ریاضی باعث می‌شود که ابزارها و قضایای زیادی را از جبرخطی و نظریهٔ گراف که مرتبط با ساختار میترویدی‌شان است را به مبحث موردنظر انتقال داد. مسئلهٔ مهم دیگر مطالعهٔ چرخه‌ها و پایه‌ها است. در بسیاری از موارد ریاضیدانان به دنبال یافتن بزرگترین‌ها و کوچکترین‌های صادق در یک سری شرایط هستند که به شناخت برخی اشیاء ریاضی و کار کردن با آن‌ها کمک می‌کند.

==پانویس==
{{پانویس|2}}


* {{یادکرد-ویکی
|پیوند = https://en.wikipedia.org/wiki/Matroid
|عنوان = Matroid
|زبان = انگلیسی}}

== منابع ==
{{چپ‌چین}}
*{{citation
 | last1 = Bruhn | first1 = Henning
 | last2 = Diestel | first2 = Reinhard
 | last3 = Kriesell | first3 = Matthias
 | last4 = Pendavingh | first4 = Rudi
 | last5 = Wollan | first5 = Paul
 | arxiv = 1003.3919
 | doi = 10.1016/j.aim.2013.01.011
 | journal = Advances in Mathematics
 | mr = 3045140
 | pages = 18–46
 | title = Axioms for infinite matroids
 | volume = 239
 | year = 2013| s2cid = 10436077
 }}.
*{{citation|last1=Bryant|first1=Victor|last2=Perfect|first2=Hazel|author2-link=Hazel Perfect|year=1980|title=Independence Theory in Combinatorics|publisher=Chapman and Hall|location=London and New York|isbn=978-0-412-22430-0}}.
*{{citation|last=Brylawski|first=Thomas H.|author-link=Thomas H. Brylawski|year=1972|title=A decomposition for combinatorial geometries|journal=Transactions of the American Mathematical Society|volume=171|pages=235&ndash;282|doi=10.2307/1996381|jstor=1996381|doi-access=free}}.
*{{citation|last=Crapo|first=Henry H.|author-link=Henry Crapo (mathematician)|year=1969|title=The Tutte polynomial|journal=[[Aequationes Mathematicae]]|volume=3|issue=3|pages=211&ndash;229|doi=10.1007/BF01817442|s2cid=119602825}}.
*{{citation|last1=Crapo|first=Henry H.|author-link=Henry Crapo (mathematician)|last2=Rota|first2=Gian-Carlo|author2-link=Gian-Carlo Rota|year=1970|title=On the Foundations of Combinatorial Theory: Combinatorial Geometries|publisher=M.I.T. Press|location=Cambridge, Mass.|isbn=978-0-262-53016-3|mr=0290980|url=https://archive.org/details/onfoundationsofc00crap}}.
*{{citation|last1=Geelen|first1=Jim|last2=Gerards|first2=A. M. H.|last3=Whittle|first3=Geoff|year=2007|contribution=Towards a matroid-minor structure theory|editor=Grimmett, Geoffrey|title=Combinatorics, Complexity, and Chance: A Tribute to Dominic Welsh|series=Oxford Lecture Series in Mathematics and its Applications|volume=34|pages=72&ndash;82|publisher=Oxford University Press|location=Oxford|display-editors=etal}}.
*{{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 Its Applications]]|volume=114/115|pages=207&ndash;212|doi=10.1016/0024-3795(89)90461-8}}.
*{{citation|last1=Kahn|first1=Jeff|last2=Kung|first2=Joseph P. S.|year=1982|title=Varieties of combinatorial geometries|journal=Transactions of the American Mathematical Society|volume=271|pages=485&ndash;499|doi=10.2307/1998894|issue=2|jstor=1998894|doi-access=free}}.
*{{citation|last1=Kingan|first1=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&ndash;296}}.
*{{citation|editor-last=Kung|editor-first=Joseph P. S.|title=A Source Book in Matroid Theory|publisher=Birkhäuser|isbn=978-0-8176-3173-4|location=Boston|year=1986|mr=0890330|doi=10.1007/978-1-4684-9199-9|url=https://archive.org/details/sourcebookinmatr0000kung}}.
*{{citation|last=Mac Lane|first=Saunders|author-link=Saunders Mac Lane|year=1936|title=Some interpretations of abstract linear dependence in terms of projective geometry|journal=American Journal of Mathematics|volume=58|pages=236–240|doi=10.2307/2371070|issue=1|jstor=2371070}}.
*{{citation|last=Minty|first=George J.|title=On the axiomatic foundations of the theories of directed linear graphs, electrical networks and network-programming|journal=Journal of Mathematics and Mechanics|volume=15|year=1966|pages=485–520|mr=0188102}}.
*{{citation|mr=2516551|zbl=1163.01001|title=A lost mathematician, Takeo Nakasawa. The forgotten father of matroid theory|editor-first=Hirokazu |editor-last=Nishimura |editor2-first=Susumu |editor2-last=Kuroda|publisher= Birkhäuser Verlag|place= Basel|year= 2009|isbn= 978-3-7643-8572-9|doi=10.1007/978-3-7643-8573-6}}.
*{{citation|last=Oxley|first=James | author-link = James Oxley|year=1992|title=Matroid Theory|publisher=Oxford University Press|location=Oxford|isbn=978-0-19-853563-8|mr=1207587|zbl=0784.05002}}.
*{{citation|last=Recski|first=András|year=1989|title=Matroid Theory and its Applications in Electric Network Theory and in Statics|volume=6|publisher=Springer-Verlag and Akademiai Kiado|location=Berlin and Budapest|isbn=978-3-540-15285-9|mr=1027839|doi=10.1007/978-3-662-22143-3|series=Algorithms and Combinatorics|url-access=registration|url=https://archive.org/details/matroidtheoryits0000recs}}.
*{{springer|id=M/m062870|first=A.A.|last= Sapozhenko}}
*{{citation|last=Seymour|first=Paul D.|author-link=Paul Seymour (mathematician)|year=1980|title=Decomposition of regular matroids|journal=Journal of Combinatorial Theory, Series B|volume=28|issue=3|pages=305&ndash;359|doi=10.1016/0095-8956(80)90075-1|zbl=0443.05027|hdl=10338.dmlcz/101946|hdl-access=free}}.
*{{citation|last=Truemper|first=Klaus|title=Matroid Decomposition|publisher=Academic Press|location=Boston|year=1992|isbn=978-0-12-701225-4|url=http://www.emis.de/monographs/md/index.html|mr=1170126}}.
*{{citation|last=Tutte|first=W. T.|author-link=W. T. Tutte|year=1959|title=Matroids and graphs|journal=Transactions of the American Mathematical Society|volume=90|pages=527–552|doi=10.2307/1993185|issue=3|mr=0101527|jstor=1993185|doi-access=free}}.
*{{citation|last=Tutte|first=W. T.|author-link=W. T. Tutte|year=1965|title=Lectures on matroids|journal=Journal of Research of the National Bureau of Standards Section B|volume=69|pages=1&ndash;47}}.
*{{citation | zbl=0231.05027 | last=Tutte | first=W.T. | author-link=W. T. Tutte | title=Introduction to the theory of matroids | series=Modern Analytic and Computational Methods in Science and Mathematics | volume=37 | location=New York | publisher=American Elsevier Publishing Company | year=1971 }}.
*{{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|volume=18|pages=403–408|doi=10.1112/jlms/s2-18.3.403|issue=3}}.
*{{citation|last=van der Waerden|first=B. L.|author-link=Bartel Leendert van der Waerden|year=1937|title=Moderne Algebra}}.
*{{citation|last=Welsh|first=D. J. A.|year=1976|title=Matroid Theory|publisher=Academic Press|isbn=978-0-12-744050-7|zbl=0343.05002|series=L.M.S. Monographs | volume=8}}.
*{{citation|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|zbl=0579.00001|url-access=registration|url=https://archive.org/details/theoryofmatroids1986unse}}.
*{{citation | editor-last=White | editor-first=Neil | title=Combinatorial geometries | series=Encyclopedia of Mathematics and its Applications | volume=29 | location=Cambridge | publisher=[[Cambridge University Press]] | year=1987 | isbn=978-0-521-33339-9 | zbl=0626.00007 | url-access=registration | url=https://archive.org/details/combinatorialgeo0000unse }}
*{{citation|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|zbl=0742.00052|url-access=registration|url=https://archive.org/details/matroidapplicati0000unse}}.
*{{citation|last=Whitney|first=Hassler|author-link=Hassler Whitney|year=1935|title=On the abstract properties of linear dependence|journal=American Journal of Mathematics|volume=57|pages=509–533|doi=10.2307/2371182|issue=3|mr=1507091|jstor=2371182|hdl=10338.dmlcz/100694|hdl-access=free}}. Reprinted in {{harvtxt|Kung|1986}}, pp.&nbsp;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|pages=222&ndash;261|url=http://eprints.kfupm.edu.sa/39296/1/39296.pdf|doi=10.1006/jctb.1995.1052}}{{dead link|date=March 2018 |bot=InternetArchiveBot |fix-attempted=yes }}.
{{پایان چپ‌چین}}

== پیوندهای بیرونی ==
{{چپ‌چین}}
* {{springer|title=Matroid|id=p/m062870}}
* Kingan, Sandra : [http://userhome.brooklyn.cuny.edu/skingan/matroids/ Matroid theory]. A large bibliography of matroid papers, matroid software, and links.
* Locke, S. C. : [http://euler.math.fau.edu/locke/Greedy.htm Greedy Algorithms].
* Pagano, Steven R. : [http://www.math.binghamton.edu/zaslav/Pagano/Matridx.htm Matroids and Signed Graphs].
* Mark Hubenthal: [https://web.archive.org/web/20100812232232/http://www.math.washington.edu/~hubenjm/matroid2.pdf A Brief Look At Matroids] ([[PDF]]) (contain proofs for statements of this article)
* James Oxley : [https://www.math.lsu.edu/~oxley/survey4.pdf What is a matroid?] (PDF)
* Neil White : [https://books.google.com/books?id=uD2H-RAcBpwC&lpg=PA285&ots=JL6z3p--j8&dq=greedoid%20theory&pg=PP1#v=onepage&q=greedoid%20theory&f=false Matroid Applications]
{{پایان چپ‌چین}}

{{شاخه‌های اصلی ریاضیات}}


[[رده:نظریه میتروید| ]]
[[رده:عملگرهای بستار]]
[[رده:خانواده مجموعه‌ها]]