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

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 2: Строка 2:
  
 
{{Определение
 
{{Определение
|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>
+
|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>
 
}}
 
}}
 
Далее <tex>span_M </tex> будет указываться, как <tex>span</tex>
 
Далее <tex>span_M </tex> будет указываться, как <tex>span</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>  
+
|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>  
 
}}
 
}}
  
Строка 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 \{ x \in X \setminus A \; |\; \exists H \subseteq A, \; H \in I , \; |H| = r(A) :\ H \cup x \notin I \}</tex>
+
: <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> |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>  
Строка 49: Строка 49:
  
 
'''Достаточное условие'''. Пусть функция <tex>span</tex> удовлетворяет свойствам и определена, как:
 
'''Достаточное условие'''. Пусть функция <tex>span</tex> удовлетворяет свойствам и определена, как:
:<tex> L = \{ I \subseteq S \; |\; \forall s \in I :  s \notin span(I \setminus {s}) \} </tex>
+
:<tex> L = \mathcal {f} I \subseteq S \; |\; \forall s \in I :  s \notin span(I \setminus {s}) \mathcal {g} </tex>
 
Сперва посмотрим на следующее:  
 
Сперва посмотрим на следующее:  
:если <tex> I \in L </tex>, тогда <tex>span(I) = I \cup \{ t \; | \; I \cup {t} \in L \} </tex>. <tex>(1)</tex>
+
:если <tex> I \in L </tex>, тогда <tex>span(I) = I \cup \mathcal {f} t \; | \; I \cup {t} \in L \mathcal {g} </tex>. (1)
  
Действительно, если <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> 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>. Таким образом по 3 свойству доказывается (для <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>.  
 
Теперь покажем, что <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>.
+
Для того чтобы проверить [[Определение матроида | 3-ю аксиому матроидов]], допустим, что <tex> I, J \in L </tex>, <tex> |I \setminus J| = 1 </tex> и <tex> |J \setminus I| = 2</tex>. Пусть <tex>I \setminus J = \mathcal {f} i \mathcal {g}</tex> и <tex>J \setminus I = \mathcal {f} {j_1, j_2} \mathcal {g}</tex>. Предположим, что <tex> I \cup {j_1} \notin L</tex>, т.е. <tex> J \cup {i} \setminus {j_2} \notin 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 \notin span(i) </tex>(как и <tex> J \in L</tex>) и поэтому, (1) применяется к <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 \{ x \; | \; I \cup {x} \notin L \} = span(I) \subseteq(T) </tex>
+
:<tex>span_M(T) = T \cup \mathcal {f} x \; | \; I \cup {x} \notin L \mathcal {g} = span(I) \subseteq(T) </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>.
+
Таким образом, мы показали, что <tex> span(T) \subseteq span(I)</tex> т.е. по 1 свойству <tex> T \subseteq span(I)</tex>. Теперь выберем <tex> t \in T \setminus I</tex>. В силу максимальности <tex> I </tex>, мы знаем, что <tex>I \cup t \notin L</tex>, и, следовательно, по (1) получаем, что <tex> t \in span(I) </tex>.
 
}}
 
}}
  
Строка 73: Строка 73:
 
# <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 ='''Необходимость'''. Пусть <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>.
+
|proof ='''Необходимость'''. Пусть <tex> \mathcal L </tex> семейство закрытых множеств матроида <tex> M = (S, \mathcal I) </tex>. 1 свойство следует из <tex> span(A \cap B) \subseteq span(A) \cap span(B) = A \cap B </tex>, по определению закрытого множества мы получаем, что пересечение закрытых множеств закрыто. Посмотрим на 2 свойства, допустим, что такой <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>. Поэтому, по 2 свойству покрывающего множества для <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>.
+
'''Достаточность'''. Пусть <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> удовлетворяет свойствам покрытого множества. 1 свойство тривиально. Рассмотрим 2 свойство, пусть <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>. Следовательно, по 2 свойству, <tex>span(T \cup s) = span(T \cup t) </tex>, и следовательно, <tex> t \in span(T \cup s)</tex>.
  
 
}}
 
}}

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)