Matroid

Z Multimediaexpo.cz

Aktuální verze z 14. 8. 2022, 14:52

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.

Definice matroidů

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

Nezávislé množiny

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 \(\emptyset\in I\).
2. Každá podmnožina nezávislé množiny je nezávislá, tedy pro každé \(A'\subseteq A\subseteq S\) platí \(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

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

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

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. \(0 \le r(X) \le |X|\)
2. \(X \subseteq Y \Rightarrow r(X) \le r(Y)\)
3. \(r(X \cup Y)+r(X \cap Y) \le 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.

Dualita

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.

Základní typy matroidů

Vektorový matroid

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.

Grafový matroid

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.