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

Ak  a  potom 
Ak  a , pričom , tak existuje prvok  tak, že

Zdroje 

Lineárna algebra
Kombinatorika