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.^[1]

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

1. ${\displaystyle \emptyset \in {\mathcal {I}$
2. Ak ${\displaystyle I\in {\mathcal {I}$ a ${\displaystyle I'\subseteq I,}$ potom ${\displaystyle I'\in {\mathcal {I}.}$
3. Ak ${\displaystyle I_{1}\in {\mathcal {I}$ a ${\displaystyle I_{2}\in {\mathcal {I}$, pričom ${\displaystyle |I_{1}|<|I_{2}|}$, tak existuje prvok ${\displaystyle e\in I_{2}$ tak, že ${\displaystyle I_{1}\cup \{e\}\in {\mathcal {I}.}$^[2]

1. ↑ ^{a b} Oxley, J. G.: Matroid Theory. Oxford University Press, 1992.
2. ↑ NEEL, David L.. Matroids you have known [online]. Mathematics Magazine: https://www.maa.org, 2014, [cit. 2019-01-11]. Dostupné online. Archivované 2019-06-07 z originálu. (anglický)

Tento článok týkajúci sa matematiky je zatiaľ „výhonok“. Pomôž Wikipédii tým, že ho doplníš a rozšíriš.