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

Покрытие

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

Пусть [math]M =\; \langle X,I \rangle[/math] — матроид. Тогда покрытие (англ. span) множества [math]A \subseteq X[/math] — это множество [math] span_M(A) = \{ x \in X \; |\; r(A) = r(A \cup x) \}[/math]

Далее [math]span_M [/math] будет указываться, как [math]span[/math]

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

[math] span(A) = A \cup \{ x \in X \setminus A \; |\; \forall S \subseteq A,\ S \in I,\ |S| = r(A) :\ S \cup x \notin I \} [/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 \{ x \in X \setminus A \; |\; \exists H \subseteq A, \; H \in I , \; |H| = r(A) :\ H \cup x \notin I \}[/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]

Теорема:

Пусть S — конечное множество. Функция [math] span : \mathcal P (S) \rightarrow \mathcal P (S) [/math] является покрытием матроида тогда и только тогда, когда удовлетворяет следующим свойствам: [math] T, U \subseteq S;\ U \subseteq span(T) \ \Rightarrow \ span(U) \subseteq span(T) [/math] [math] T \subseteq S,\ t \in S \setminus T,\ s \in span(T \cup t) \setminus span(T) \ \Rightarrow \ t \in span(T \cup s) [/math]

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

[math]\triangleright[/math]

Необходимое условие. Пусть [math] span [/math] будет функцией покрытия матроида [math] M = (S, L) [/math] с ранговой функцией [math] r [/math]. Покажем, что [math] s \in span(T)[/math]. Пусть [math]U \subseteq span(T)[/math] и [math]s \in span(U)[/math]. Предположим, что [math] s [/math] не принадлежит [math]T[/math]. Тогда по полумодулярность ранговой функции мы имеем: [math] r(T \cup {s}) \leqslant r(T \cup U \cup {s}) \leqslant r(T \cup U) + r(U \cup {s}) - r(U) = r(T \cup U) = r(T)[/math] Это показывает, что [math] s \in span(T) [/math]. Заметим, что [math] s \in span(T \cup {t}) \Rightarrow span(T) [/math] эквивалентно таким выражениям: [math] r(T \cup {t} \cup {s}) = r(T \cup {t}) [/math] и [math] r(T \cup {s}) \gt r(T)[/math]. Следовательно [math]r(T \cup t \cup {s}) = r(T \cup {t}) \lt = r(T) + 1 \lt = r(T \cup {s}) [/math] то есть, [math] t \in span(T \cup {s}) [/math]. Достаточное условие. Пусть функция [math]span[/math] удовлетворяет свойствам и определена, как: [math] L = \{ I \subseteq S \; |\; \forall s \in I : s \notin span(I \setminus {s}) \} [/math] Сперва посмотрим на следующее: если [math] I \in L [/math], тогда [math]span(I) = I \cup \{ t \; | \; I \cup {t} \in L \} [/math]. [math](1)[/math] Действительно, если [math] t \in span(I) \setminus I [/math], тогда [math] I \cup {t} \notin L [/math], по определению независимого множества. С другой стороны, [math] I \subseteq span(I)[/math]. Кроме того, если [math] I \cup {t} \notin L [/math], тогда по определению независимого множества получаем, что [math] \exists s \in I \cup t : s \in span(I \cup {t} \setminus {s}) [/math]. Если [math] s = t [/math], тогда [math] t \in span(I) [/math]. Предположим, что [math] s \neq t [/math], т.е. [math] s \in I [/math]. Мы знаем, что [math] s \notin span(I \setminus {s}) [/math], так как [math] I \in L [/math]. Таким образом по [math]3[/math] свойству доказывается (для [math] T \in I \setminus {s} [/math]), [math] t \in span(I) [/math]. Теперь покажем, что [math] M = (S, L) [/math] — матроид. Очевидно, [math] \emptyset \in L [/math]. Для начала покажем, что [math] I [/math] закрытое множество под полученным подмножеством, Пусть [math] I \in L [/math] и [math] J \subseteq I [/math]. Мы видим, что [math] J \in I [/math]. Предположим наоборот, что [math]\exists s \in J : s \in span(J \setminus {s}) [/math]. Тогда по второму свойству [math] span(J \setminus {s}) \subseteq span(I \setminus {s})[/math]. Следовательно, [math] s \in span( I \setminus {s})[/math], что противоречит условию, что [math] I \in L [/math]. Для того чтобы проверить 3-ю аксиому матроидов, допустим, что [math] I, J \in L [/math], [math] |I \setminus J| = 1 [/math] и [math] |J \setminus I| = 2[/math]. Пусть [math]I \setminus J = \{ i \}[/math] и [math]J \setminus I = \{ {j_1, j_2} \}[/math]. Предположим, что [math] I \cup {j_1} \notin L[/math], т.е. [math] J \cup {i} \setminus {j_2} \notin L[/math], и так по [math](1)[/math] применяется к [math]J \setminus {j_2} [/math], [math] i \in span(J \setminus {j_2}) [/math]. Поэтому, [math] I \subseteq span(J \setminus {j_2})[/math] и [math] span(I) \subseteq span(J \setminus {j_2}) [/math]. Таким образом [math] j_2 \notin span(i) [/math](как и [math] J \in L[/math]) и поэтому, [math](1)[/math] применяется к [math] I [/math] и к [math] I \cup {j_2} \in L [/math]. Таким образом [math] M [/math] является матроидом. Теперь покажем, что [math]span = span_M[/math]. Выберем такое множество [math] T \subseteq S [/math], чтобы увидеть, что [math] span(T) = span_M(T) [/math], пусть [math] I [/math] будет базой [math] T [/math] (в [math] M [/math]). Тогда используя (1), мы получаем: [math]span_M(T) = T \cup \{ x \; | \; I \cup {x} \notin L \} = span(I) \subseteq(T) [/math] Таким образом, мы показали, что [math] span(T) \subseteq span(I)[/math] т.е. по [math]1[/math] свойству [math] T \subseteq span(I)[/math]. Теперь выберем [math] t \in T \setminus I[/math]. В силу максимальности [math] I [/math], мы знаем, что [math]I \cup t \notin L[/math], и, следовательно, по [math](1)[/math] получаем, что [math] t \in span(I) [/math].

[math]\triangleleft[/math]

Закрытые множества

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

Множество [math]A \subseteq X[/math] называется закрытым (англ. closed set, flat), если [math] span(A) = A. [/math] Класс закрытых множеств обозначается [math] \mathcal L. [/math]

Теорема:

Пусть [math] S [/math] — какое-то множество и [math] \mathcal L \subseteq S [/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]

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

[math]\triangleright[/math]

Необходимость. Пусть [math] \mathcal L [/math] семейство закрытых множеств матроида [math] M = (S, \mathcal I) [/math]. Первое свойство следует из [math] span(A \cap B) \subseteq span(A) \cap span(B) = A \cap B [/math], по определению закрытого множества мы получаем, что пересечение закрытых множеств закрыто. Посмотрим на [math]2[/math] свойства, допустим, что такой [math] F'' [/math] существует, и выберем [math] s \in F'' \setminus F [/math]. Таким образом [math] s \notin span(F)[/math]. Согласно тому, что [math] F' \not\subseteq F'' [/math], мы получаем, что [math] t \notin span(F \cup s)[/math]. Поэтому, по второму свойству покрывающего множества для [math] T := F [/math] получаем противоречие, т.к. [math] s \notin span(F) = F'[/math]. Достаточность. Пусть [math] \mathcal L [/math] удовлетворяет свойствам закрытого множества и [math] span(Y) [/math] будет наименьшем множеством в [math] \mathcal L [/math] содержащий [math] Y [/math], для [math] F \subseteq S [/math]. Поскольку [math] F \in \mathcal L \Longleftrightarrow span(F) = F [/math], этого достаточно, чтобы увидеть, что [math] span [/math] удовлетворяет свойствам покрытого множества. Первое свойство тривиально. Рассмотрим второе свойство, пусть [math]T \subseteq S, t \in S \setminus T, [/math] и [math] s \in span(T \cup t) \setminus span(T) [/math]. Тогда [math] span(T ) \subset span(T \cup s) \subseteq span(T \cup t) [/math]. Следовательно, по второму свойству, [math]span(T \cup s) = span(T \cup t) [/math], и следовательно, [math] t \in span(T \cup s)[/math].

[math]\triangleleft[/math]

См. также

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

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

• Асанов М. О., Баранский В. А., Расин В. В. — Дискретная математика: Графы, матроиды, алгоритмы. ISBN 978-5-8114-1068-2
• courses.engr.illinois.edu — Lecture 14, course CS 598CSC: Combinatorial optimization
• Alexander Schrijver — Combinatorial Optimization. Polyhedra and Efficiency