Matroid

Matroid – struktura stosowana w kombinatoryce. Pojęcie to zostało wprowadzone w 1935 roku przez angielskiego matematyka Hasslera Whitneya^[1].

Formalna definicja matroidu jest następująca. Matroidem nazywamy parę ( S , I ) , {\displaystyle (S,{\mathcal {I}}),} która musi spełniać następujące warunki^[2]:

• S {\displaystyle S} jest zbiorem skończonym,
• I {\displaystyle {\mathcal {I}}} jest taką niepustą rodziną podzbiorów S , {\displaystyle S,} że jeśli B ∈ I {\displaystyle B\in {\mathcal {I}}} oraz A ⊆ B , {\displaystyle A\subseteq B,} to A ∈ I {\displaystyle A\in {\mathcal {I}}} (zbiór pusty zawsze należy do I {\displaystyle {\mathcal {I}}} ),
• jeśli A {\displaystyle A} i B {\displaystyle B} należą do I {\displaystyle {\mathcal {I}}} oraz | A | < | B | , {\displaystyle |A|<|B|,} to istnieje taki element x ∈ B ∖ A , {\displaystyle x\in B\setminus A,} że A ∪ { x } ∈ I {\displaystyle A\cup \{x\}\in {\mathcal {I}}} (jest to własność wymiany).

Podzbiór A {\displaystyle A} należący do I {\displaystyle {\mathcal {I}}} nazywamy podzbiorem niezależnym^[2]. A {\displaystyle A} jest bazą matroidu, jeśli jest maksymalnym 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ą)^[1][3].

• Thomas H.T.H. Cormen Thomas H.T.H., Charles E.Ch.E. Leiserson Charles E.Ch.E., Ronald L.R.L. Rivest Ronald L.R.L., CliffordC. Stein CliffordC., Wprowadzenie do algorytmów, wyd. VII, Wydawnictwo Naukowe PWN, 2012, ISBN 978-83-01-16911-4 .

• Ilustracja przedstawiająca przykład matroidu grafowego