Matroid

z Wikipédie, slobodnej encyklopédie
Prejsť na: navigácia, hľadanie

Matroid je matematická štruktúra, ktorá zovšeobecňuje pojem lineárnej nezávislosti v lineárnych priestoroch, a ktorá zohráva dôležitú úlohu v lineárnej algebre a teórii grafov. Existuje relatívne veľký počet rôznych ekvivalentných definícii pojmu matroid.[1]

Bežná definícia[1][upraviť | upraviť zdroj]

Matroid M je usporiadaná dvojica (E,\mathcal{I}), kde E je konečná množina a \mathcal{I} je nejaká trieda podmnožín množiny E, pričom sú splnené nasledujúce podmienky:

  1. \emptyset \in \mathcal{I}
  2. Ak I \in \mathcal{I} a I' \subseteq I, potom I' \in \mathcal{I}.
  3. Ak I_1 \in \mathcal{I} a I_2 \in \mathcal{I}, pričom |I_1| < |I_2|, tak existuje prvok e \in I_2 tak, že I_1 \cup \{e\} \in \mathcal{I}.

Zdroje[upraviť | upraviť zdroj]

  1. a b Oxley, J. G.: Matroid Theory. Oxford University Press, 1992.