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.
Definice matroidů
[editovat | editovat zdroj]Matroidy mohou být definovány několika různými způsoby.
Nezávislé množiny
[editovat | editovat zdroj]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:
- Prázdná množina je nezávislá, neboli .
- Každá podmnožina nezávislé množiny je nezávislá, tedy pro každé platí Tato vlastnost se nazývá vlastnost dědičnosti.
- 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
[editovat | editovat zdroj]Kružnice jsou v inkluzi minimální závislé množiny. Množina všech kružnic má následující vlastnosti:
- Prázdná množina není kružnice.
- Pokud A i B jsou kružnice a A je podmnožinou B, pak A=B (jedinečnost v inkluzi).
- 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
[editovat | editovat zdroj]Báze jsou v inkluzi maximální nezávislé množiny. Množina všech bází má následující vlastnosti:
- Nějaká báze existuje.
- 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
[editovat | editovat zdroj]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:
- (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
[editovat | editovat zdroj]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ů
[editovat | editovat zdroj]Vektorový matroid
[editovat | editovat zdroj]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): (Ir|D), přičemž prvních r prvků odpovídá prvkům B.
Duální matroid takovéhoto matroidu odpovídá matici (DT|In-r), kde n značí počet prvků nosné množiny.
Grafový matroid
[editovat | editovat zdroj]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.