Matroid

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.

Bežná definícia

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}.$