Покрытия, закрытые множества

Покрытие

Определение:

Пусть [math]M =\; \langle X,I \rangle[/math] — матроид. Тогда покрытие (англ. span) множества [math]A \subseteq X[/math] — это множество [math] span(A) = \mathcal {f} x \in X \; |\; r(A) = r(A \cup x) \mathcal {g}[/math]

Определение:

[math] span(A) = A \cup \mathcal {f} x \in X \; |\; \forall S \subseteq A \setminus x,\ S \in I,\ |S| = r(A) :\ S \cup x \notin I \mathcal {g} [/math]

Утверждение:

Эти определения эквивалентны.

[math]\triangleright[/math]

Понятно, что элементы из [math] A [/math] подходят под оба определения. Для остальных же [math] x [/math] равенство [math] \ r(A) = r(A \cup x) [/math] означает, что не найдётся множеств [math] S' \subseteq A \cup x :\ S' \in I,\ |S'| \gt r(A). [/math] Для такого [math] S' [/math] обязательно будет выполнено [math] x \in S', [/math] в противном случае [math] S' \subseteq A, [/math] откуда следует [math] r(A) \geqslant |S'|. [/math] Следовательно для [math] S = S' \setminus x [/math] верно [math] S \subseteq A,\ S \in I. [/math] Из последнего получается, что [math] r(A) \geqslant |S|, [/math] и учитывая [math] r(A) \lt |S'|,\ |S| + 1 = |S'| [/math] имеем [math] r(A) = |S|. [/math] Иначе говоря, не должно существовать множеств [math] S \subseteq A,\ x \notin S,\ S \in I,\ |S| = r(A):\ S' = S \cup x \in I. [/math]

[math]\triangleleft[/math]

Утверждение:

Определения замыкания и покрытия похожи (???)

[math]\triangleright[/math]

Покажем, что следующее определение замыкания равносильно тому, которое было дано ранее: [math]\langle A \rangle = A \cup \mathcal {f} x \in X \; |\; \exists H \subseteq A \setminus x, \; H \in I , \; |H| = r(A) :\ H \cup x \notin I \mathcal {g}[/math] По сравнению со старым определением появилось два ограничения, нужно убедится в том, что они не существены. Сначала рассмотрим [math] |H| = r(A). [/math] Пусть [math] \exists H \subseteq A :\ H \in I ,\; H \cup x \notin I, [/math] но [math] |H| \lt r(A). [/math] По определению ранга [math] \exists D \subseteq A ,\; D \in I :\ |D| = r(A). [/math] Поскольку [math] |H| \lt |D| [/math], можно применить 3-ю аксиому матроидов несколько раз и получить [math] H' \subseteq A :\ H \subseteq H' ,\; H' \in I ,\; |H'| = r(A). [/math] [math] H' \cup x \notin I [/math] также будет выполнено, поскольку в противном случае [math] H \cup x \notin I [/math] будет неверно (в силу 2-ой аксиомы матроидов). Второе ограничение — [math] H \subseteq A \setminus x [/math] вместо [math] H \subseteq A [/math] — вытекает само собой, поскольку в случае [math] x \in H [/math] не могут одновременно выполнятся [math] H \in I [/math] и [math] H \cup x \notin I. [/math] В соответствии с этим определением, замыкание множества [math] A [/math] — это, кроме всех элементов [math] A [/math], все такие [math] x, [/math] что какое-то из максимальных по мощности независимых подмножеств [math] A [/math] нельзя дополнить [math] x [/math]-ом, оставив это множество независимым. Определение покрытия отличается только квантором — вместо "какое-то" нужно поставить "любое".

[math]\triangleleft[/math]

Теорема:

Покрытие обладает следующими свойствами: [math] A, B \in X;\ A \subseteq span(B) \ \Rightarrow \ span(A) \subseteq span(B) [/math] [math] A \in X,\ p \in X \setminus A,\ q \in span(A \cup p) \Rightarrow p \in span(A \cup q) [/math]

Закрытые множества

Определение:

Множество [math]A \subseteq X[/math] называется закрытым (англ. closed set, flat), если [math] span(A) = A. [/math] Класс закрытых множеств обозначается [math] \mathcal L. [/math]

Теорема:

Замкнутые множества обладают следующими свойствами: [math] A, B \in \mathcal L \ \; \Rightarrow \ A \cap B \in \mathcal L [/math] Если [math] F \in \mathcal L,\ p \in X \setminus A [/math] и [math] F' [/math] — наименьшее по включению закрытое множество, содержащее [math] F \cup p, [/math] тогда не существует [math] F'' \in \mathcal L :\ F \subseteq F'' \subseteq F'. [/math]