Покрытия, закрытые множества

Покрытие

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

Пусть [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 \setminus A \; |\; \forall S \subseteq A,\ 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,\ S \in I,\ |S| = r(A):\ S' = S \cup x \in I. [/math]

[math]\triangleleft[/math]

Утверждение:

Для множества [math] A \subseteq X [/math] выполнено [math] span(A) \subseteq \langle A \rangle. [/math]

[math]\triangleright[/math]

Покажем, что следующее определение замыкания равносильно тому, которое было дано ранее: [math]\langle A \rangle = A \cup \mathcal {f} x \in X \setminus A \; |\; \exists H \subseteq A, \; 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] x \in X \setminus A [/math] можно наложить по той причине, что элементы [math] x \in A [/math] и так входят в замыкание благодаря левой части объединения. В соответствии с этим определением, замыкание множества [math] A [/math] — это, кроме всех элементов [math] A [/math], все такие [math] x, [/math] что какое-то из максимальных по мощности независимых подмножеств [math] A [/math] нельзя дополнить [math] x [/math]-ом, оставив это множество независимым. Определение покрытия отличается только квантором — вместо "какое-то" нужно поставить "любое". Учитывая, что [math] S \subseteq A,\ S \in I,\ |S| = r(A) [/math] описывает непустое множество таких [math] S [/math] (по определению ранга), будет верным следствие: [math] \forall S \subseteq A,\ S \in I,\ |S| = r(A) :\ S \cup x \notin I \ \Rightarrow [/math] [math] \exists H \subseteq A, \; H \in I , \; |H| = r(A) :\ H \cup x \notin I [/math] Поэтому [math] x \in span(A) \Rightarrow x \in \langle A \rangle. [/math]

[math]\triangleleft[/math]

Теорема:

Покрытие обладает следующими свойствами: [math] A, B \subseteq X;\ A \subseteq span(B) \ \Rightarrow \ span(A) \subseteq span(B) [/math] [math] A \subseteq X,\ p \in X \setminus A,\ q \in span(A \cup p) \setminus span(A) \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 F [/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
• courses.engr.illinois.edu — Lecture 14, course CS 598CSC: Combinatorial optimization