Matroid

z Wikipédie, slobodnej encyklopédie
Prejsť na: navigácia, hľadanie

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

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. Ak a potom
  2. Ak a , pričom , tak existuje prvok tak, že

Zdroje[upraviť | upraviť zdroj]

  1. a b Oxley, J. G.: Matroid Theory. Oxford University Press, 1992.