Оператор замыкания для матроидов

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

Пусть [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 \mathcal {f} x\; |\; \exists B \subseteq A :\ B \in I ,\; B \cup x \notin I \mathcal {g}[/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, C \in I:\ B \subseteq A, C \subseteq \langle A \rangle, |B| = r(A) \lt r(\langle A \rangle) = |C|.[/math] Тогда по аксиоме замен [math]\exists p \in C \setminus B :\ B \cup p \in I.[/math] Так как [math]B[/math] — максимально, то [math]p \in \langle A \rangle \setminus A.[/math] По определению замыкания существует множество [math]D \subseteq A:\ D \in I,\ D\cup p \notin I.[/math] В силу аксиомы наследования можно считать, что [math]|D| = |B|.[/math] Тогда [math]r(A) = |D| \lt |B \cup p|.[/math] По аксиоме замены существует [math]q \in (B \cup p)\setminus D :\ D \cup q \in I.[/math] Если [math]q \in B,[/math] то [math](D \cup q) \subseteq A[/math] (противоречит максимальности множества [math]D[/math]). Если [math]q = p,[/math] то [math](D \cup p) \in I[/math] (противоречит выбору множества [math]D[/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]\langle \langle A \rangle \rangle = \langle A \rangle [/math]

Доказательство:

[math]\triangleright[/math]

[math]x \in \langle A \rangle.[/math] Тогда по определению оператора замыкания [math]\exists C \in I, C \subseteq A :\ C \cup x \notin I.[/math] Но [math]C \subseteq B,[/math] поэтому [math]x \in \langle B \rangle.[/math] Так как [math]q \in \langle A \cup p \rangle [/math] и [math]q \notin \langle A \rangle,[/math] то существует независимое множество [math]B :\ B \subseteq A \cup p, B \cup q \notin I.[/math] Так как [math]q \notin \langle A \rangle,[/math] то [math]p \in B, (B \setminus p)\cup q \in I.[/math] Тогда [math]((B \setminus p)\cup q) \cup p \notin I,[/math] то есть [math]p \in \langle A \cup q \rangle.[/math] Из определения понятно, что [math] \langle A \rangle \subseteq \langle \langle A \rangle \rangle [/math]. Предположим [math]\exists p \in \langle \langle A \rangle \rangle \setminus \langle A \rangle.[/math] Возьмем максимальное по мощности множество [math]B \in I :\ B \subseteq A.[/math] Так как [math]p \notin \langle A \rangle,[/math] то по определению замыкания [math]B \cup p \in I.[/math] Тогда, последовательно применив вышеуказанную лемму, дважды определение ранга и снова лемму, получим [math]r(\langle A \rangle) = r(\langle \langle A \rangle \rangle) \geqslant |B \cup p| = r(A) + 1 = r(\langle A \rangle) + 1,[/math] что невозможно.

[math]\triangleleft[/math]

Источники информации

Асанов М. О., Баранский В. А., Расин В. В. — Дискретная математика: Графы, матроиды, алгоритмы. ISBN 978-5-8114-1068-2