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