Matroid

Matroid je struktura v kombinatorice, která zobecňuje koncept „nezávislosti“, jehož konkrétním příkladem je například lineární nezávislost ve vektorových prostorech.

Nejpříbuznějšími obory k teorii matroidů jsou lineární algebra a teorie grafů, ze kterých také teorie matroidů přebírá mnoho ze své terminologie.

Matroidy mohou být definovány několika různými způsoby.

Jednou ze základní definice je definice pomocí nezávislosti: Matroid M je dvojice (S,I), kde S je konečná množina (zvaná nosná množina) obsahující prvky matroidu a I je množina podmnožin S (nazývaných nezávislé (pod)množiny) splňující následující vlastnosti:

1. Prázdná množina je nezávislá, neboli ${\displaystyle \emptyset \in I}$.
2. Každá podmnožina nezávislé množiny je nezávislá, tedy pro každé ${\displaystyle A'\subseteq A\subseteq S}$ platí ${\displaystyle A\in I\Rightarrow A'\in I.}$ Tato vlastnost se nazývá vlastnost dědičnosti.
3. Pokud A a B jsou dvě nezávislé množiny z I a A má více prvků než B, pak existuje takový prvek z A, který není v B a po jehož přidání do B nepřestane být B nezávislé. Tato vlastnost se nazývá výměnná vlastnost

Kružnice jsou v inkluzi minimální závislé množiny. Množina všech kružnic má následující vlastnosti:

1. Prázdná množina není kružnice.
2. Pokud A i B jsou kružnice a A je podmnožinou B, pak A=B (jedinečnost v inkluzi).
3. Pokud A i B jsou kružnice a e je v jejich průniku, pak existuje kružnice ve sjednocení A a B, která neobsahuje e.

Množina splňující tyto podmínky navíc matroid jednoznačně definuje -- nezávislé množiny jsou právě ty, které neobsahují žádnou kružnici. Jedná se tedy o alternativní definici.

Kružnicím velikosti 1 se říká smyčky, kružnicím velikosti 2 se říká paralelní elementy.

Báze jsou v inkluzi maximální nezávislé množiny. Množina všech bází má následující vlastnosti:

1. Nějaká báze existuje.
2. Pokud mám báze A a B a prvek e z A \ B, pak existuje f z B \ A takový, že A-e+f je báze.

Množina splňující tyto podmínky navíc matroid jednoznačně definuje -- nezávislé množiny jsou právě podmnožiny bází. Jedná se tedy o alternativní definici.

Ranková funkce matroidu je zobrazení z podmnožin nosné množiny do přirozených čísel definovaná jako velikost největší nezávislé podmnožiny. Splňuje následující vlastnosti:

1. ${\displaystyle 0\leq r(X)\leq |X|}$
2. ${\displaystyle X\subseteq Y\Rightarrow r(X)\leq r(Y)}$
3. ${\displaystyle r(X\cup Y)+r(X\cap Y)\leq r(X)+r(Y)}$ (submodularita)

Navíc ranková funkce jednoznačně definuje matroid, nezávislé množiny jsou právě takové X, že |X| = r(X). Jedná se tedy o alternativní definici.

Rank matroidu je r(S), tedy velikost báze.

Když se pomocí matroidu M vytvoří nový matroid tak, že jeho báze jsou doplňky bází M, potom je to duální matroid k M a značí se M*. Zjevně M** = M.

Sloupce nějaké matice je možné chápat jako prvky nosné množiny. Nezávislé množiny jsou pak právě ty, které jsou lineárně nezávislé. Snadno se ověří, že se jedná o matroid.

Báze tohoto matroidu jsou právě báze sloupcového prostoru, což zdůvodňuje použití tohoto termínu.

Následující operace nemění vlastnosti vektorového matroidu:

• Vynásobení řádku nenulovou hodnotou
• Přičtení lineární kombinace některých řádků k jinému řádku
• Odstranění nulového řádku
• Vynásobení sloupce nenulovou hodnotou
• Prohození sloupců (příslušně se však změní korespondence mezi prvky matroidu a sloupci)

Pomocí těchto operací se dá matice převést do základního tvaru pro nějakou bázi B (r je rank matroidu): (I_r|D), přičemž prvních r prvků odpovídá prvkům B.

Duální matroid takovéhoto matroidu odpovídá matici (D^T|I_n-r), kde n značí počet prvků nosné množiny.

Pokud se za nosnou množinu vezmou hrany (multi)grafu a za nezávislé množiny se prohlásí ty, které tvoří acyklický podgraf, vznikne takzvaný grafový matroid.

Je-li graf souvislý, báze matroidu odpovídají právě kostrám.

Kružnice tohoto matroidu jsou právě kružnice v grafu, což zdůvodňuje použití tohoto termínu.

V případě rovinných grafů duální matroid odpovídá právě grafovému matroidu duálního grafu.