|
'''Matroid''' – struktura stosowana w [[kombinatoryka|kombinatoryce]]. Pojęcie to zostało wprowadzone w [[1935]] roku przez angielskiego matematyka [[Hasslera Whitney]]a<ref name=oxley>{{Cytuj pismo | autor = James Oxley | tytuł = What is a matroid? | url = http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.69.9393&rep=rep1&type=pdf}}</ref>.
{{dopracować|źródła=2014-06}}
'''Matroid''' to obiekt stanowiący uogólnienie [[przestrzeń liniowa|przestrzeni liniowej]] wraz z istniejącym w niej pojęciem niezależności liniowej{{fakt|data=2014-06}}. Matroidy bada się głównie w takich działach [[matematyka|matematyki]], jak [[algebra]], [[geometria]] czy [[matematyka dyskretna]]{{fakt|data=2014-06}}. Pojęcie to zostało wprowadzone w [[1935]] roku przez angielskiego matematyka [[Hasslera Whitney]]a{{odn|Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein|s=392}}.
Formalna definicja matroidu jest następująca. Matroidem nazywamy parę <math>(S, I)</math>, która musi spełniać następujące warunki{{odn|Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein|s=392443}}. Matroidem nazywamy parę (X, cl), gdzie X jest [[zbiór|zbiorem]] skończonym, zaś cl [[Funkcja|funkcją]] odwzorowującą zbiór wszystkich podzbiorów zbioru X w siebie. Przy tym funkcja cl, którą nazywa się operatorem domknięcia, musi spełniać następujące warunki:
* <math>S</math> jest zbiorem skończonym,
* ''A'' zawiera się w ''cl(A)''
* <math>I</math> jest taką niepustą [[rodzina zbiorów|rodziną podzbiorów]] <math>S</math>, że jeśli <math>B \in I</math> oraz <math>A \subseteq B</math>, to <math>A \in I</math> ([[zbiór pusty]] zawsze należy do <math>I</math>),
* ''cl(cl(A))''=''cl(A)''
* jeśli <math>A</math> i <math>B</math> należą do <math>I</math> oraz <math>|A| < |B|</math>, to istnieje taki element <math>x \in B \ A</math>, że <math>B \cup \{x\} \in I</math> (jest to ''własność wymiany'').
* jeśli ''A'' zawiera się w ''B'', to ''cl(A)'' zawiera się w ''cl(B)''
* jeśli ''b'' należy do ''cl(Aa)'', lecz nie należy do ''cl(A)'', to ''a'' należy do ''cl(Ab)'' (jest to tak zwany '''aksjomat wymiany Steinitza''')
dla dowolnych podzbiorów ''A, B'' zbioru ''X'' oraz dowolnych elementów ''a, b'' zbioru ''X'' (przez Aa rozumiemy sumę zbiorów A i {a}).
Podzbiór ''<math>A''</math> matroidunależący ''X''do <math>I</math> nazywamy podzbiorem '''niezależnym''',{{odn|Thomas jeśliH. dlaCormen, każdegoCharles elementuE. a ze zbioru ''A'' element ''a'' nie należy do zbioru cl(A\{a}) (czyliLeiserson, mówiącRonald zwykłymL. językiemRivest, elementClifford a jest niezależny od zbioru A\{aStein|s=443}}). Natomiast ''<math>A''</math> jest '''bazą''' matroidu ''X'', jeśli ''A'' jest maksymalnym podzbiorem niezależnym podzbiorem(nie ''X''.zawiera Dziękisię aksjomatowiw wymianyżadnym możnainnym udowodnić,podzbiorze żeniezależnym). wW każdym matroidzie można znaleźć bazę (zazwyczaj więcej niż jedną)<ref name=oxley />{{odn|Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein|s=444}}.
Nietrudno sprawdzić, że jeśli ''X'' jest skończoną przestrzenią liniową, zaś ''cl'' operatorem liniowego domknięcia w ''X'', to para (X, cl) spełnia wszystkie wyżej wymienione [[aksjomat]]y matroidu. Innym przykładem matroidu jest dowolne skończone [[ciało (matematyka)|ciało]] wraz z operatorem algebraicznego domknięcia. Rozważa się też matroidy nieskończone, stosując w stosunku do nich nazwę '''pregeometria'''.
== Przypisy ==
== Bibliografia ==
* {{cytuj książkę |autor=Thomas H. Cormen |autor2=Charles E. Leiserson |autor3=Ronald L. Rivest |autor4=Clifford Stein |tytuł=Wprowadzenie do algorytmów |wydawca=WNT[[Wydawnictwo Naukowe PWN]] |rok=20072012 |wydanie=VII |odn isbn=9788301169114 {{|odn/id|Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford= Stein}}tak}}
== Linki zewnętrzne ==
* [http://algorytmy.ency.pl/plik/matroid_mst.png Ilustracja przedstawiająca przykład matroidu grafowego]
[[Kategoria:Algebra liniowa]]
| 