Matroid

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

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:

  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[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:

  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[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:

  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[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:

  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[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 na 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.