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]1">upraviť | upraviť zdroj

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]

Zdrojeupraviť | upraviť zdroj

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-04-30. Dostupné online. (anglický)

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