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,ℐ)$, kde E je konečná množina a $ℐ$ je nejaká trieda podmnožín množiny E, pričom sú splnené nasledujúce podmienky:

1. $\mathrm{\varnothing }\in ℐ$
2. Ak $I\in ℐ$ a $I^{\prime }\subseteq I,$ potom $I^{\prime }\in ℐ.$
3. Ak $I_1\in ℐ$ a $I_2\in ℐ$, pričom $|I_1|<|I_2|$, tak existuje prvok $e\in I_2$ tak, že $I_1\cup \{e\}\in ℐ.$