308
правок
Изменения
м
Нет описания правки
{{Определение
|definition = Пусть <tex>M =\; \langle X,I \rangle</tex> {{-- -}} [[Определение матроида|матроид]]. Тогда '''замыкание (closure)''' множества <tex>A \subset subseteq X</tex> {{--- }} это множество <tex>\langle A \rangle \subset subseteq X</tex> такое, что <tex>\langle A \rangle = A \cup \mathcal {f} x\; |\; \exists B \subset subseteq A : \ B \in I ,\; B \cup x \notin I \mathcal {g}</tex>
}}
{{Лемма
|statement = Пусть <tex>M =\; \langle X,I \rangle</tex> {{- --}} матроид, <tex>A \subset subseteq X</tex>. Тогда <tex>r(A) = r(\langle A \rangle),</tex> где <tex>r</tex> {{--- }} [[Ранговая функция, полумодулярность|ранг]].
|proof =
Пусть существуют такие множества <tex>B, C \in I: \ B \subset subseteq A, C \subset 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 \subset subseteq A: \ D \in I, D\cup p \notin I.</tex> В силу аксиомы наследования <ref>[[Определение матроида | Определение матроида]], 2-я аксиома</ref> можно считать, что <tex>|D| = |B|.</tex> Тогда <tex>r(A) = |D| < |B \cup p|.</tex> По аксиоме замены существует <tex>q \in (B \cup p)\setminus D : \ D \cup q \in I.</tex>
Если <tex>q \in B,</tex> то <tex>(D \cup q) \subset subseteq A</tex> (противоречит максимальности множества <tex>D</tex>). Если <tex>q = p,</tex> то <tex>(D \cup p) \in I</tex> (противоречит выбору множества <tex>D</tex>).
}}
|id = theorem
|statement = Оператор замыкания для матроидов обладает следующими свойствами:
# <tex>A \subset subseteq B \Rightarrow \langle A \rangle \subset subseteq \langle B \rangle</tex>
# <tex>q \notin \langle A \rangle,\; q \in \langle A \cup p \rangle \Rightarrow p \in \langle A \cup q \rangle</tex>
# <tex>\langle \langle A \rangle \rangle = \langle A \rangle </tex>
|proof =
# <tex>x \in \langle A \rangle.</tex> Тогда по определению оператора замыкания <tex>\exists C \in I, C \subset subseteq A : \ C \cup x \notin I.</tex> Но <tex>C \subset subseteq B,</tex> поэтому <tex>x \in \langle B \rangle.</tex> Ч.т.д.# Так как <tex>q \in \langle A \cup p \rangle </tex> и <tex>q \notin \langle A \rangle,</tex> то существует независимое множество <tex>B : \ B \subset subseteq A \cup p, B \cup q \notin I.</tex> Так как <tex>q \notin \langle A \rangle,</tex> то <tex>p \in B, (B \setminus p)\cup q \in I.</tex> Тогда <tex>((B \setminus p)\cup q) \cup p \notin I,</tex> то есть <tex>p \in \langle A \cup q \rangle.</tex># Пусть <tex>\exists p \in \langle \langle A \rangle \rangle \setminus \langle A \rangle.</tex> Возьмем максимальное по мощности множество <tex>B \in I : \ B \subset 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) \ge |B \cup p| = r(A) + 1 = r(\langle A \rangle) + 1,</tex> что невозможно.
}}
== Литература Примечания ==<references/> == Источники информации ==''Асанов М. О., Баранский В. А., Расин В. В.'' {{-- -}} Дискретная математика: Графы, матроиды, алгоритмы. '''ISBN 978-5-8114-1068-2'''<br />
[[Категория:Алгоритмы и структуры данных]]
[[Категория:Матроиды]]
