308
правок
Изменения
м
Нет описания правки
{{Определение
|definition = Пусть <tex>M =\; \langle X,I \rangle</tex> {{---}} [[Определение матроида|матроид]]. Тогда '''замыкание (closure)''' множества <tex>A \subseteq X</tex> {{---}} это множество <tex>\langle A \rangle \subseteq X</tex> такое, что <tex>\langle A \rangle = A \cup \mathcal {f} x\in X \; |\; \exists B H \subseteq A :\ B H \in I ,\; B H \cup x \notin I \mathcal {g}</tex>
}}
|statement = Пусть <tex>M =\; \langle X,I \rangle</tex> {{---}} матроид, <tex>A \subseteq X</tex>. Тогда <tex>r(A) = r(\langle A \rangle),</tex> где <tex>r</tex> {{---}} [[Ранговая функция, полумодулярность|ранг]].
|proof =
Пусть существуют множества <tex>B, C \in I:\ B \subseteq A, C \subseteq \langle A \rangle, |B| = r(A) < r(\langle A \rangle) = |C|.</tex> Тогда по аксиоме замен<ref>[[Определение матроида | Определение матроида]], 3-я аксиома</ref> <tex>\exists p \in C \setminus B :\ B \cup p \in I.</tex> Так как <tex>B</tex> {{---}} максимально, то <tex>p \in \langle A \rangle \setminus A.</tex> По определению замыкания существует множество <tex>D H \subseteq A:\ D H \in I,\ DH\cup p \notin I.</tex> В силу аксиомы наследования<ref>[[Определение матроида | Определение матроида]], 2-я аксиома</ref> можно считать, что <tex>|DH| = |B|.</tex> Тогда <tex>r(A) = |DH| < |B \cup p|.</tex> По аксиоме замены существует <tex>q \in (B \cup p)\setminus D H :\ D H \cup q \in I.</tex>
Если <tex>q \in B,</tex> то <tex>(D H \cup q) \subseteq A</tex> (противоречит максимальности множества <tex>DH</tex>). Если <tex>q = p,</tex> то <tex>(D H \cup p) \in I</tex> (противоречит выбору множества <tex>DH</tex>).
}}
# <tex>\langle \langle A \rangle \rangle = \langle A \rangle </tex>
|proof =
# Положим <tex>x \in \langle A \rangle.</tex> Тогда по определению В соответствии с определением оператора замыкания есть 2 случая:#* <tex>x \exists C in A. </tex> Тогда <tex> x \in IB </tex>, C и следовательно <tex> x \in \langle B \rangle. </tex> #* <tex>\exists H \subseteq A :\ C H \in I,\ H \cup x \notin I.</tex> Но Для такого <tex> H </tex> также верно <tex>C H \subseteq B,</tex> поэтому потому <tex>x \in \langle B \rangle.</tex> # Так как Опять два случая: #* <tex>q \in \langle A \cup p \rangle . </tex> и Зная, что <tex>q p \notin \langle A \rangle,</tex> то существует независимое множество приходим к <tex> q = p, </tex> чего нам более чем достаточно.#* <tex>B :\ B exists H \subseteq A \cup p:\ H \in I, B \ H \cup q \notin I.</tex> Так как #*: Заметим что <tex> p \in H </tex>, иначе бы <tex> H </tex> подходило для <tex>q \notin in \langle A \rangle,</tex> то поэтому запишем данное нам иначе: #*:: <tex>\exists H' \subseteq A:\ H' \cup p \in BI, \ (B H' \setminus cup p)\cup q \in notin I.</tex> Тогда #*: <tex>((B \setminus p)H' \cup q) \cup p in I </tex>, в противном случае в силу <tex> H' \notin in I,</tex> то было бы <tex> q \in \langle A \rangle. </tex>#*: Как видим, у нас есть всё необходимое чтобы сказать, что <tex>p \in \langle A \cup q \rangle.</tex>
# Из определения понятно, что <tex> \langle A \rangle \subseteq \langle \langle A \rangle \rangle </tex>. Предположим <tex>\exists p \in \langle \langle A \rangle \rangle \setminus \langle A \rangle.</tex> Возьмем максимальное по мощности множество <tex>B \in I :\ B \subseteq A.</tex> Так как <tex>p \notin \langle A \rangle,</tex> то по определению замыкания <tex>B \cup p \in I.</tex> Тогда, последовательно применив вышеуказанную лемму, дважды [[Ранговая функция, полумодулярность | определение ранга]] и снова лемму, получим <tex>r(\langle A \rangle) = r(\langle \langle A \rangle \rangle) \geqslant |B \cup p| = r(A) + 1 = r(\langle A \rangle) + 1,</tex> что невозможно.
}}
