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ę ${\displaystyle (S,{\mathcal {I}}),}$ która musi spełniać następujące warunki^[2]:

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

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

Przypisy

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