Tekst źródłowy strony Matroid

'''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 |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>.

Formalna definicja matroidu jest następująca. Matroidem nazywamy parę <math>(S, \mathcal{I}),</math> która musi spełniać następujące warunki{{odn|Cormen|Leiserson|Rivest|Stein|2012|s=443}}:
* <math>S</math> jest [[Zbiór skończony|zbiorem skończonym]],
* <math>\mathcal{I}</math> jest taką niepustą [[rodzina zbiorów|rodziną podzbiorów]] <math>S,</math> że jeśli <math>B \in \mathcal{I}</math> oraz <math>A \subseteq B,</math> to <math>A \in \mathcal{I}</math> ([[zbiór pusty]] zawsze należy do <math>\mathcal{I}</math>),
* jeśli <math>A</math> i <math>B</math> należą do <math>\mathcal{I}</math> oraz <math>|A| < |B|,</math> to istnieje taki element <math>x \in B \setminus A,</math> że <math>A \cup \{x\} \in \mathcal{I}</math> (jest to '''własność wymiany''').

Podzbiór <math>A</math> należący do <math>\mathcal{I}</math> nazywamy podzbiorem '''niezależnym'''{{odn|Cormen|Leiserson|Rivest|Stein|2012|s=443}}. <math>A</math> jest '''bazą''' matroidu, jeśli jest maksymalnym [[Podzbiór|podzbiorem]] niezależnym (nie zawiera się w żadnym innym podzbiorze niezależnym). W każdym matroidzie można znaleźć bazę (zazwyczaj więcej niż jedną)<ref name=oxley />{{odn|Cormen|Leiserson|Rivest|Stein|2012|s=444}}.

== Przypisy ==
{{Przypisy}}

== Bibliografia ==
* {{cytuj |autor=Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein |tytuł=Wprowadzenie do algorytmów |wydawca=[[Wydawnictwo Naukowe PWN]] |data=2012 |wydanie=VII |isbn=9788301169114 |odn = tak}}

== Linki zewnętrzne ==
* [http://algorytmy.ency.pl/plik/matroid_mst.png Ilustracja przedstawiająca przykład matroidu grafowego]

{{Kontrola autorytatywna}}

[[Kategoria:Algebra liniowa]]
[[Kategoria:Kombinatoryka]]
[[Kategoria:Geometria]]