Независимые множества матроида: различия между версиями

'''Независимые множества матроида''' (''Independent sets of a matroid'') -  

семейство <math>{\cal I}</math> подмножеств элементов из <math>E</math>, удовлетворяющих

(I0) <math>\emptyset \in {\cal I}</math>;

(I1) если <math>X \in {\cal I}</math> и <math>Y \subseteq X</math>, то <math>Y \in {\cal I}</math>;

(I2) если <math>X, \, Y</math> --- элементы из <math>{\cal I}</math> такие, что <math>|X| = |Y| +

{\cal I}</math>.

Подмножество из <math>E</math>, не принадлежащее <math>{\cal I}</math>, называется {\it

(I'2) Если <math>X, Y \in {\cal I}</math> и <math>|Y| < |X|</math>, то в <math>X \setminus Y</math>

существует элемент <math>x</math> такой, что <math>Y \cup \{x\} \in {\cal I}</math>.

(I''2) Если <math>X, Y \in {\cal I}</math> и <math>|Y| < |X|</math>, то в <math>X</math> существует

такое подмножество <math>Z</math>, что <math>Y \cup Z \in {\cal I}</math> и <math>|Y \cup Z| =