Независимые множества матроида

Независимые множества матроида (Independent sets of a matroid) — семейство [math]\displaystyle{ {\mathcal I} }[/math] подмножеств элементов из [math]\displaystyle{ E }[/math], удовлетворяющих следующим аксиомам:

(I0) [math]\displaystyle{ \emptyset \in {\mathcal I} }[/math];

(I1) если [math]\displaystyle{ X \in {\mathcal I} }[/math] и [math]\displaystyle{ Y \subseteq X }[/math], то [math]\displaystyle{ Y \in {\mathcal I} }[/math];

(I2) если [math]\displaystyle{ X, \, Y }[/math] --- элементы из [math]\displaystyle{ {\mathcal I} }[/math] такие, что [math]\displaystyle{ |X| = |Y| + 1 }[/math], то существует [math]\displaystyle{ x \in X \setminus Y }[/math] такой, что [math]\displaystyle{ Y \cup \{x\} \in {\mathcal I} }[/math].

Подмножество из [math]\displaystyle{ E }[/math], не принадлежащее [math]\displaystyle{ {\mathcal I} }[/math], называется {\it зависимым}.

Так как (I0) следует из (I1), то в качестве системы аксиом можно взять (I1) (I2). Кроме того, существуют варианты аксиомы (I'2), (I2), эквивалентные (I2):

(I'2) Если [math]\displaystyle{ X, Y \in {\mathcal I} }[/math] и [math]\displaystyle{ |Y| \lt |X| }[/math], то в [math]\displaystyle{ X \setminus Y }[/math] существует элемент [math]\displaystyle{ x }[/math] такой, что [math]\displaystyle{ Y \cup \{x\} \in {\mathcal I} }[/math].

(I"2) Если [math]\displaystyle{ X, Y \in {\mathcal I} }[/math] и [math]\displaystyle{ |Y| \lt |X| }[/math], то в [math]\displaystyle{ X }[/math] существует такое подмножество [math]\displaystyle{ Z }[/math], что [math]\displaystyle{ Y \cup Z \in {\mathcal I} }[/math] и [math]\displaystyle{ |Y \cup Z| = |X| }[/math].

Литература

• Лекции по теории графов / В.А.Емеличев, О.И.Мельников, В.И.Сарванов, Р.И.Тышкевич. — М.: Наука, 1990.

• Welsh D.J.A. Matroid Theory. — New York: Academic Press, 1976.