Matroid

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

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

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

Podzbiór $A$ należący do ${\mathcal {I}}$ nazywamy podzbiorem niezależnym. $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ą).

Bibliografia

• Thomas H.T.H. Cormen Thomas H.T.H. i inni, Wprowadzenie do algorytmów, wyd. VII, Wydawnictwo Naukowe PWN, 2012, ISBN 978-83-01-16911-4 .

Linki zewnętrzne

• Ilustracja przedstawiająca przykład matroidu grafowego