Покрытие
| Определение: |
| Пусть [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]
|
Смотри также
Оператор замыкания для матроидов
Источники информации
- Асанов М. О., Баранский В. А., Расин В. В. — Дискретная математика: Графы, матроиды, алгоритмы. ISBN 978-5-8114-1068-2
- sensagent.com — Matroid
