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] upraviť

Matroid M je usporiadaná dvojica  , kde E je konečná množina a   je nejaká trieda podmnožín množiny E, pričom sú splnené nasledujúce podmienky:

  1.  
  2. Ak   a   potom  
  3. Ak   a  , pričom  , tak existuje prvok   tak, že  [2]


Zdroje upraviť

  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-02-27]. Dostupné online. (anglický)