Покрытия, закрытые множества — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Покрытие)
(См. также)
 
(не показано 9 промежуточных версий 2 участников)
Строка 2: Строка 2:
  
 
{{Определение
 
{{Определение
|definition = Пусть <tex>M =\; \langle X,I \rangle</tex> {{---}} матроид. Тогда '''покрытие''' (англ. ''span'') множества <tex>A \subseteq X</tex> {{---}} это множество <tex> span_M(A) = \mathcal {f} x \in X \; |\; r(A) = r(A \cup x) \mathcal {g}</tex>
+
|definition = Пусть <tex>M =\; \langle X,I \rangle</tex> {{---}} матроид. Тогда '''покрытие''' (англ. ''span'') множества <tex>A \subseteq X</tex> {{---}} это множество <tex> span_M(A) = \{ x \in X \; |\; r(A) = r(A \cup x) \}</tex>
 
}}
 
}}
 
Далее <tex>span_M </tex> будет указываться, как <tex>span</tex>
 
Далее <tex>span_M </tex> будет указываться, как <tex>span</tex>
  
 
{{Определение
 
{{Определение
|definition = <tex> 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} </tex>  
+
|definition = <tex> span(A) = A \cup \{ x \in X \setminus A \; |\; \forall S \subseteq A,\ S \in I,\ |S| = r(A) :\ S \cup x \notin I \} </tex>  
 
}}
 
}}
  
Строка 21: Строка 21:
 
|statement=Для множества <tex> A \subseteq X </tex> выполнено <tex> span(A) \subseteq \langle A \rangle. </tex>  
 
|statement=Для множества <tex> A \subseteq X </tex> выполнено <tex> span(A) \subseteq \langle A \rangle. </tex>  
 
|proof=Покажем, что следующее определение замыкания равносильно тому, которое [[Оператор замыкания для матроидов | было дано]] ранее:
 
|proof=Покажем, что следующее определение замыкания равносильно тому, которое [[Оператор замыкания для матроидов | было дано]] ранее:
: <tex>\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}</tex>
+
: <tex>\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 \}</tex>
 
По сравнению со старым определением появилось два ограничения, нужно убедится в том, что они не существены. Сначала рассмотрим <tex> |H| = r(A). </tex>  
 
По сравнению со старым определением появилось два ограничения, нужно убедится в том, что они не существены. Сначала рассмотрим <tex> |H| = r(A). </tex>  
 
: Пусть <tex> \exists H \subseteq A :\ H \in I ,\; H \cup x \notin I, </tex> но <tex> |H| < r(A). </tex>  По [[Ранговая функция, полумодулярность | определению ранга]] <tex> \exists D \subseteq A ,\; D \in I :\ |D| = r(A). </tex> Поскольку <tex> |H| < |D| </tex>, можно применить [[Определение матроида | 3-ю аксиому матроидов]] несколько раз и получить <tex> H' \subseteq A :\ H \subseteq H' ,\; H' \in I ,\; |H'| = r(A). </tex>  
 
: Пусть <tex> \exists H \subseteq A :\ H \in I ,\; H \cup x \notin I, </tex> но <tex> |H| < r(A). </tex>  По [[Ранговая функция, полумодулярность | определению ранга]] <tex> \exists D \subseteq A ,\; D \in I :\ |D| = r(A). </tex> Поскольку <tex> |H| < |D| </tex>, можно применить [[Определение матроида | 3-ю аксиому матроидов]] несколько раз и получить <tex> H' \subseteq A :\ H \subseteq H' ,\; H' \in I ,\; |H'| = r(A). </tex>  
Строка 37: Строка 37:
  
 
{{Теорема
 
{{Теорема
|statement = Покрытие обладает следующими свойствами:
+
|statement = Пусть S {{---}} конечное множество. Функция <tex> span : \mathcal P (S) \rightarrow \mathcal P (S) </tex> является покрытием матроида тогда и только тогда, когда удовлетворяет следующим свойствам:
 
# <tex> T, U \subseteq S;\ U \subseteq span(T) \ \Rightarrow \ span(U) \subseteq span(T) </tex>
 
# <tex> T, U \subseteq S;\ U \subseteq span(T) \ \Rightarrow \ span(U) \subseteq span(T) </tex>
 
# <tex> T \subseteq S,\ t \in S \setminus T,\ s \in span(T \cup t) \setminus span(T) \ \Rightarrow \ t \in span(T \cup s) </tex>
 
# <tex> T \subseteq S,\ t \in S \setminus T,\ s \in span(T \cup t) \setminus span(T) \ \Rightarrow \ t \in span(T \cup s) </tex>
 
|proof ='''Необходимое условие'''. Пусть <tex> span </tex> будет функцией покрытия матроида <tex> M = (S, L) </tex> с ранговой функцией <tex> r </tex>. Покажем, что <tex> s \in span(T)</tex>. Пусть <tex>U \subseteq span(T)</tex> и <tex>s \in span(U)</tex>. Предположим, что <tex> s </tex> не принадлежит <tex>T</tex>. Тогда по [[ Ранговая_функция, полумодулярность | полумодулярность ранговой функции]] мы имеем:
 
|proof ='''Необходимое условие'''. Пусть <tex> span </tex> будет функцией покрытия матроида <tex> M = (S, L) </tex> с ранговой функцией <tex> r </tex>. Покажем, что <tex> s \in span(T)</tex>. Пусть <tex>U \subseteq span(T)</tex> и <tex>s \in span(U)</tex>. Предположим, что <tex> s </tex> не принадлежит <tex>T</tex>. Тогда по [[ Ранговая_функция, полумодулярность | полумодулярность ранговой функции]] мы имеем:
: <tex> r(T \cup {s}) <= r(T \cup U \cup {s}) <= r(T \cup U) + r(U \cup {s}) - r(U) = r(T \cup U) = r(T)</tex>
+
: <tex> 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)</tex>
 
Это показывает, что <tex> s \in span(T) </tex>.
 
Это показывает, что <tex> s \in span(T) </tex>.
  
Строка 49: Строка 49:
  
 
'''Достаточное условие'''. Пусть функция <tex>span</tex> удовлетворяет свойствам и определена, как:
 
'''Достаточное условие'''. Пусть функция <tex>span</tex> удовлетворяет свойствам и определена, как:
:<tex> L = \mathcal {f} I \subseteq S \; |\; \forall s \in I :  s \notin span(I \setminus {s}) \mathcal {g} </tex>
+
:<tex> L = \{ I \subseteq S \; |\; \forall s \in I :  s \notin span(I \setminus {s}) \} </tex>
 
Сперва посмотрим на следующее:  
 
Сперва посмотрим на следующее:  
:если <tex> I \in L </tex>, тогда <tex>span(I) = I \cup \mathcal {f} t \; | \; I \cup {t} \in L \mathcal {g} </tex>. (1)
+
:если <tex> I \in L </tex>, тогда <tex>span(I) = I \cup \{ t \; | \; I \cup {t} \in L \} </tex>. <tex>(1)</tex>
  
Действительно, если <tex> t \in span(I) \setminus I </tex>, тогда <tex> I \cup {t} \notin L </tex>, по определению независимого множества. С другой стороны, <tex> I \subseteq span(I)</tex>. Кроме того, если <tex> I \cup {t} \notin L </tex>, тогда по определению независимого множества получаем, что <tex> \exists s \in I \cup t : s \in span(I \cup {t} \setminus {s}) </tex>. Если <tex> s = t </tex>, тогда <tex> t \in span(I) </tex>. Предположим, что <tex> s \neq t </tex>, т.е. <tex> s \in I </tex>. Мы знаем, что <tex> s \in span(I \setminus {s}) </tex>, так как <tex> I \in L </tex>. Таким образом по 3 свойству доказывается (для <tex> T \in I \setminus {s} </tex>), <tex> t \in span(I) </tex>.
+
Действительно, если <tex> t \in span(I) \setminus I </tex>, тогда <tex> I \cup {t} \notin L </tex>, по определению независимого множества. С другой стороны, <tex> I \subseteq span(I)</tex>. Кроме того, если <tex> I \cup {t} \notin L </tex>, тогда по определению независимого множества получаем, что <tex> \exists s \in I \cup t : s \in span(I \cup {t} \setminus {s}) </tex>. Если <tex> s = t </tex>, тогда <tex> t \in span(I) </tex>. Предположим, что <tex> s \neq t </tex>, т.е. <tex> s \in I </tex>. Мы знаем, что <tex> s \notin span(I \setminus {s}) </tex>, так как <tex> I \in L </tex>. Таким образом по <tex>3</tex> свойству доказывается (для <tex> T \in I \setminus {s} </tex>), <tex> t \in span(I) </tex>.
  
Теперь покажем, что <tex> M = (S, L) </tex> {---} матроид. Очевидно, <tex> \emptyset \in L </tex>. Для начала покажем, что  <tex> I </tex> закрытое множество под полученным подмножеством, Пусть <tex> I \in L </tex> и <tex> J \subseteq I </tex>. Мы видим, что <tex> J \in I </tex>. Предположим наоборот, что <tex>\exists s \in J : s \in span(J \setminus {s}) </tex>. Тогда по второму свойству <tex> span(J \setminus {s}) \subseteq span(I \setminus {s})</tex>. Следовательно, <tex> s \in span( I \setminus {s})</tex>, что противоречит условию, что <tex> I \in L </tex>. Для того чтобы проверить [[Определение матроида | 3-ю аксиому матроидов]], допустим, что <tex> I, J \in L </tex>, <tex> |I \setminus J| = 1 </tex> и <tex> |J \setminus I| = 2</tex>. Пусть <tex>I \setminus J = {i}</tex> и <tex>J \setminus I = {j_1, j_2}</tex>. Предположим, что <tex> I \cup {j_1} \in L</tex>, т.е. <tex> J \cup {i} \setminus {j_2} \in L</tex>, и так по (1) применяется к <tex>J \setminus {j_2} </tex>, <tex> i \in span(J \setminus {j_2}) </tex>. Поэтому, <tex> I \subseteq span(J \setminus {j_2})</tex> и <tex> span(I) \subseteq span(J \setminus {j_2}) </tex>. Таким образом <tex> j_2 \in span(i) </tex>(как и <tex> J \in L</tex>) и поэтому, (1) применяется к <tex> I </tex> и к <tex> I \cup {j_2} \in L </tex>.
+
Теперь покажем, что <tex> M = (S, L) </tex> {{---}} матроид. Очевидно, <tex> \emptyset \in L </tex>. Для начала покажем, что  <tex> I </tex> закрытое множество под полученным подмножеством, Пусть <tex> I \in L </tex> и <tex> J \subseteq I </tex>. Мы видим, что <tex> J \in I </tex>. Предположим наоборот, что <tex>\exists s \in J : s \in span(J \setminus {s}) </tex>. Тогда по второму свойству <tex> span(J \setminus {s}) \subseteq span(I \setminus {s})</tex>. Следовательно, <tex> s \in span( I \setminus {s})</tex>, что противоречит условию, что <tex> I \in L </tex>.  
 +
 
 +
Для того чтобы проверить [[Определение матроида | 3-ю аксиому матроидов]], допустим, что <tex> I, J \in L </tex>, <tex> |I \setminus J| = 1 </tex> и <tex> |J \setminus I| = 2</tex>. Пусть <tex>I \setminus J = \{ i \}</tex> и <tex>J \setminus I = \{ {j_1, j_2} \}</tex>. Предположим, что <tex> I \cup {j_1} \notin L</tex>, т.е. <tex> J \cup {i} \setminus {j_2} \notin L</tex>, и так по <tex>(1)</tex> применяется к <tex>J \setminus {j_2} </tex>, <tex> i \in span(J \setminus {j_2}) </tex>. Поэтому, <tex> I \subseteq span(J \setminus {j_2})</tex> и <tex> span(I) \subseteq span(J \setminus {j_2}) </tex>. Таким образом <tex> j_2 \notin span(i) </tex>(как и <tex> J \in L</tex>) и поэтому, <tex>(1)</tex> применяется к <tex> I </tex> и к <tex> I \cup {j_2} \in L </tex>.
  
 
Таким образом <tex> M </tex> является матроидом. Теперь покажем, что <tex>span = span_M</tex>. Выберем такое множество <tex> T \subseteq S </tex>, чтобы увидеть, что <tex> span(T) = span_M(T) </tex>, пусть <tex> I </tex> будет базой <tex> T </tex> (в <tex> M </tex>). Тогда используя (1), мы получаем:
 
Таким образом <tex> M </tex> является матроидом. Теперь покажем, что <tex>span = span_M</tex>. Выберем такое множество <tex> T \subseteq S </tex>, чтобы увидеть, что <tex> span(T) = span_M(T) </tex>, пусть <tex> I </tex> будет базой <tex> T </tex> (в <tex> M </tex>). Тогда используя (1), мы получаем:
:<tex>span_M(T) = T \cup \mathcal {f} x \; | \; I \cup {x} \in L \mathcal {g} = span(I) \subseteq(T) </tex>
+
:<tex>span_M(T) = T \cup \{ x \; | \; I \cup {x} \notin L \} = span(I) \subseteq(T) </tex>
Таким образом, мы показали, что <tex> span(T) \subseteq span(I)</tex> т.е. по 1 свойству <tex> T \subseteq span(I)</tex>. Теперь выберем <tex> t \in T \setminus I</tex>. Мы знаем <tex>I \cup t \notin L</tex>, т.к. <tex> I </tex> максимально по включению, и, следовательно, по (1) получаем, что <tex> t \in span(I) </tex>.
+
Таким образом, мы показали, что <tex> span(T) \subseteq span(I)</tex> т.е. по <tex>1</tex> свойству <tex> T \subseteq span(I)</tex>. Теперь выберем <tex> t \in T \setminus I</tex>. В силу максимальности <tex> I </tex>, мы знаем, что <tex>I \cup t \notin L</tex>, и, следовательно, по <tex>(1)</tex> получаем, что <tex> t \in span(I) </tex>.
 
}}
 
}}
  
Строка 68: Строка 70:
  
 
{{Теорема
 
{{Теорема
|statement = Закрытые множества обладают следующими свойствами:
+
|statement = Пусть <tex> S </tex> {{---}} какое-то множество и <tex> \mathcal L \subseteq S </tex>. Закрытые множества обладают следующими свойствами:
 
# <tex> A, B \in \mathcal L \ \; \Rightarrow \ A \cap B \in \mathcal L </tex>
 
# <tex> A, B \in \mathcal L \ \; \Rightarrow \ A \cap B \in \mathcal L </tex>
 
# Если <tex> F \in \mathcal L,\ p \in X \setminus F </tex> и <tex> F' </tex> {{---}} наименьшее закрытое множество, содержащее <tex> F \cup p, </tex> тогда не существует <tex> F'' \in \mathcal L :\ F \subseteq F'' \subseteq F'. </tex>  
 
# Если <tex> F \in \mathcal L,\ p \in X \setminus F </tex> и <tex> F' </tex> {{---}} наименьшее закрытое множество, содержащее <tex> F \cup p, </tex> тогда не существует <tex> F'' \in \mathcal L :\ F \subseteq F'' \subseteq F'. </tex>  
|proof =
+
|proof ='''Необходимость'''. Пусть <tex> \mathcal L </tex> семейство закрытых множеств матроида <tex> M = (S, \mathcal I) </tex>. Первое свойство следует из <tex> span(A \cap B) \subseteq span(A) \cap span(B) = A \cap B </tex>, по определению закрытого множества мы получаем, что пересечение закрытых множеств закрыто. Посмотрим на <tex>2</tex> свойства, допустим, что такой <tex> F'' </tex> существует, и выберем <tex> s \in F'' \setminus F </tex>. Таким образом <tex> s \notin span(F)</tex>. Согласно тому, что <tex> F' \not\subseteq F'' </tex>, мы получаем, что <tex> t \notin span(F \cup s)</tex>. Поэтому, по второму свойству покрывающего множества для <tex> T := F </tex> получаем противоречие, т.к. <tex> s \notin span(F) = F'</tex>.
 +
 
 +
'''Достаточность'''. Пусть <tex> \mathcal L </tex> удовлетворяет свойствам закрытого множества и <tex> span(Y) </tex> будет наименьшем множеством в <tex> \mathcal L </tex> содержащий <tex> Y </tex>, для <tex> F \subseteq S </tex>. Поскольку <tex> F \in \mathcal L \Longleftrightarrow span(F) = F </tex>, этого достаточно, чтобы увидеть, что <tex> span </tex> удовлетворяет свойствам покрытого множества. Первое свойство тривиально. Рассмотрим второе свойство, пусть <tex>T \subseteq S, t \in S \setminus T, </tex> и <tex> s \in span(T \cup t) \setminus span(T) </tex>. Тогда <tex> span(T ) \subset span(T \cup s) \subseteq span(T \cup t) </tex>. Следовательно, по второму свойству, <tex>span(T \cup s) = span(T \cup t) </tex>, и следовательно, <tex> t \in span(T \cup s)</tex>.
 +
 
 
}}
 
}}
  
 
== См. также ==
 
== См. также ==
 +
* [[Определение матроида]]
 
* [[Оператор замыкания для матроидов]]
 
* [[Оператор замыкания для матроидов]]
 +
* [[Теорема о базах]]
  
 
== Источники информации ==
 
== Источники информации ==
 
*''Асанов М. О., Баранский В. А., Расин В. В.'' {{---}} Дискретная математика: Графы, матроиды, алгоритмы. '''ISBN 978-5-8114-1068-2'''
 
*''Асанов М. О., Баранский В. А., Расин В. В.'' {{---}} Дискретная математика: Графы, матроиды, алгоритмы. '''ISBN 978-5-8114-1068-2'''
 
* [http://courses.engr.illinois.edu/cs598csc/sp2010/Lectures/Lecture14.pdf courses.engr.illinois.edu {{---}} Lecture 14, course ''CS 598CSC: Combinatorial optimization'']
 
* [http://courses.engr.illinois.edu/cs598csc/sp2010/Lectures/Lecture14.pdf courses.engr.illinois.edu {{---}} Lecture 14, course ''CS 598CSC: Combinatorial optimization'']
 +
*''Alexander Schrijver'' {{---}} Combinatorial Optimization. Polyhedra and Efficiency
  
 
[[Категория:Алгоритмы и структуры данных]]
 
[[Категория:Алгоритмы и структуры данных]]
 
[[Категория:Матроиды]]
 
[[Категория:Матроиды]]
 
[[Категория:Основные факты теории матроидов]]
 
[[Категория:Основные факты теории матроидов]]

Текущая версия на 17:42, 11 декабря 2018

Покрытие[править]

Определение:
Пусть [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] является покрытием матроида тогда и только тогда, когда удовлетворяет следующим свойствам:
  1. [math] T, U \subseteq S;\ U \subseteq span(T) \ \Rightarrow \ span(U) \subseteq span(T) [/math]
  2. [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]. Закрытые множества обладают следующими свойствами:
  1. [math] A, B \in \mathcal L \ \; \Rightarrow \ A \cap B \in \mathcal L [/math]
  2. Если [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]

См. также[править]

Источники информации[править]