Материал из Викиконспекты
| Определение: |
| Пусть [math]M =\; \langle X,I \rangle[/math] — матроид. Тогда замыкание (англ. closure) множества [math]A \subseteq X[/math] — это множество [math]\langle A \rangle \subseteq X[/math] такое, что [math]\langle A \rangle = A \cup \{ x \in X \; |\; \exists H \subseteq A :\ H \in I ,\; H \cup x \notin I \}[/math] |
Другими словами, замыкание множества [math] A [/math] — это все элементы из [math] A, [/math] а также такие [math] x \in X, [/math] которые при добавлении к некоторым независимым подмножествам [math] A [/math] не оставляют их независимыми.
| Лемма: |
Пусть [math]M =\; \langle X,I \rangle[/math] — матроид, [math]A \subseteq X[/math]. Тогда [math]r(A) = r(\langle A \rangle),[/math] где [math]r[/math] — ранг. |
| Доказательство: |
| [math]\triangleright[/math] |
|
Пусть существуют множества [math]B, D \in I:\ B \subseteq A,\ D \subseteq \langle A \rangle,\ |B| = r(A) \lt r(\langle A \rangle) = |D|.[/math] Тогда по 3-ей аксиоме [math]\exists p \in D \setminus B :\ B \cup p \in I.[/math] Так как [math]B[/math] — максимальное независимое множество из [math] A [/math], то [math]p \notin A,[/math] то есть [math] p \in \langle A \rangle \setminus A. [/math] Согласно определению замыкания возьмём максимальное по мощности множество [math]H \subseteq A:\ H \in I,\ H\cup p \notin I.[/math] Поскольку [math] |H| \leqslant |B| \lt |B \cup p|,[/math] то по аксиоме замены существует [math]q \in (B \cup p)\setminus H :\ H \cup q \in I.[/math]
Если [math]q \in B,[/math] то [math](H \cup q) \subseteq A,\ [/math] но [math] (H \cup q) \cup p \notin I [/math] в силу [math] H \cup p \notin I [/math] (противоречие с максимальностью множества [math]H[/math]). Если [math]q = p,[/math] то [math](H \cup p) \in I[/math] (противоречит выбору множества [math]H[/math]). |
| [math]\triangleleft[/math] |
| Определение: |
| Пусть [math]M =\; \langle X,I \rangle[/math] — матроид. Тогда замыкание (англ. closure) множества [math]A \subseteq X[/math] — это множество [math]\langle A \rangle \subseteq X[/math] такое, что [math]\langle A \rangle = \{ x \in X \; |\; r(A \cup x) = r(A) \}[/math], где [math]r: 2^X \to \mathbb{N}[/math] - ранговая функция |
| Лемма: |
Данное определение эквивалентно предыдущему |
| Доказательство: |
| [math]\triangleright[/math] |
|
Пусть [math]\langle A \rangle_1[/math] — замыкание [math]A[/math] в смысле первого определения, [math]\langle A \rangle_2[/math] — замыкание [math]A[/math] в смысле второго определения.
Покажем, что [math]\langle A \rangle_1 = \langle A \rangle_2[/math]
- [math]\langle A \rangle_1 \subseteq \langle A \rangle_2[/math]
По предыдущей лемме, [math]r(A) = r(\langle A \rangle_1)[/math], а значит, [math]\forall a \in \langle A \rangle_1 : r(A \cup a) = r(A)[/math], а значит, [math]a \in \langle A \rangle_2[/math].
В силу произвольности [math]a[/math], [math]\langle A \rangle_1 \subseteq \langle A \rangle_2[/math].
- [math]\langle A \rangle_2 \subseteq \langle A \rangle_1[/math]
Рассмотрим [math]a \in \langle A \rangle_2 : r(A \cup a) = r(A)[/math]. Возьмем [math]B \subseteq A, \; B \in I[/math] — наибольшее независимое подмножество [math]A[/math]. Тогда [math]B \cup a \notin I[/math], так как иначе [math]r(A \cup e) = |B \cup e| \gt |B| = r(A)[/math].
Следовательно, [math]b \in \langle A \rangle_1[/math], и в силу произвольности [math]b[/math], [math]\langle A \rangle_2 \subseteq \langle A \rangle_1[/math]
|
| [math]\triangleleft[/math] |
| Теорема: |
Оператор замыкания для матроидов обладает следующими свойствами:
- [math]A \subseteq B \Rightarrow \langle A \rangle \subseteq \langle B \rangle[/math]
- [math]q \notin \langle A \rangle,\; q \in \langle A \cup p \rangle \Rightarrow p \in \langle A \cup q \rangle[/math]
- [math]e \in \langle A \rangle \Rightarrow \langle A \cup e \rangle = \langle A \rangle[/math]
- [math]\langle \langle A \rangle \rangle = \langle A \rangle [/math]
|
| Доказательство: |
| [math]\triangleright[/math] |
- Положим [math]x \in \langle A \rangle.[/math] В соответствии с первым определением оператора замыкания есть 2 случая:
- [math] x \in A. [/math] Тогда [math] x \in B [/math], и следовательно [math] x \in \langle B \rangle. [/math]
- [math]\exists H \subseteq A :\ H \in I,\ H \cup x \notin I.[/math] Для такого [math] H [/math] также верно [math]H \subseteq B,[/math] потому [math]x \in \langle B \rangle.[/math]
- Опять два случая:
- [math] q \in A \cup p. [/math] Зная, что [math] q \notin \langle A \rangle, [/math] приходим к [math] q = p, [/math] чего нам более чем достаточно.
- [math] \exists H \subseteq A \cup p :\ H \in I,\ H \cup q \notin I. [/math]
- Заметим, что [math] p \in H [/math], иначе бы [math] H [/math] подходило для [math] q \in \langle A \rangle, [/math] поэтому запишем имеющееся у нас иначе, положив [math] H' = H \setminus p: [/math]
- [math] \exists H' \subseteq A:\ H' \cup p \in I,\ H' \cup p \cup q \notin I. [/math]
- [math] H' \cup q \in I [/math], в противном случае в силу [math] H' \in I [/math] было бы [math] q \in \langle A \rangle. [/math]
- Как видим, множество [math] H' \cup q [/math] подходит под определение [math] p \in \langle A \cup q \rangle. [/math]
- По первому свойству очевидно, что [math]\langle A \rangle \subseteq \langle A \cup e \rangle[/math]. Докажем обратное: [math]\langle A \cup e \rangle \subseteq \langle A \rangle[/math].
Воспользуемся вторым определением оператора замыкания. Рассмотрим [math]f \in \langle A \cup e \rangle[/math]. По полумодулярности ранговой функции имеем:
[math]r(A \cup e) + r(A \cup f) \geqslant r(A \cup e \cup f) + r((A \cup e) \cap (A \cup f)) \geqslant r(A \cup e \cup f) + r(A)[/math].
Но [math]r(A \cup e) = r(A)[/math] (так как [math]e \in \langle A \rangle[/math]), значит, [math]r(A \cup f) \geqslant r(A \cup e \cup f)[/math], что в свою очередь влечет [math]r(A \cup f) = r(A \cup e \cup f)[/math].
Но так как [math]f \in \langle A \cup e \rangle[/math] и [math]e \in \langle A \rangle[/math], то имеем [math]r(A) = r(A \cup e) = r(A \cup e \cup f) = r(A \cup f)[/math].
Следовательно, по определению, [math]f \in \langle A \rangle[/math].
В силу произвольности [math]f: \langle A \cup e \rangle \subseteq \langle A \rangle[/math].
- Следует из третьего свойства: [math]\forall e \in \langle A \rangle : \langle A \cup e \rangle = \langle A \rangle[/math], а значит, [math]\langle \langle A \rangle \rangle = \langle A \cup \langle A \rangle \rangle = \langle A \cup e_1 \cup e_2 \cup e_3 \cup ... \rangle = \langle A \rangle[/math] (где [math]e_1, e_2, ...\in \langle A \rangle[/math])
|
| [math]\triangleleft[/math] |
