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

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

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

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 1: Строка 1:
 +
== Замыкание ==
 +
 
{{Определение
 
{{Определение
 
|definition = Пусть <tex>M =\; \langle X,I \rangle</tex> {{---}} [[Определение матроида|матроид]]. Тогда '''замыкание''' (англ. ''closure'') множества <tex>A \subseteq X</tex> {{---}} это множество <tex>\langle A \rangle \subseteq X</tex> такое, что <tex>\langle A \rangle = A \cup \{ x \in X \; |\; \exists H \subseteq A :\ H \in I ,\; H \cup x \notin I \}</tex>
 
|definition = Пусть <tex>M =\; \langle X,I \rangle</tex> {{---}} [[Определение матроида|матроид]]. Тогда '''замыкание''' (англ. ''closure'') множества <tex>A \subseteq X</tex> {{---}} это множество <tex>\langle A \rangle \subseteq X</tex> такое, что <tex>\langle A \rangle = A \cup \{ x \in X \; |\; \exists H \subseteq A :\ H \in I ,\; H \cup x \notin I \}</tex>
Строка 47: Строка 49:
 
# По первому свойству очевидно, что <tex>\langle A \rangle \subseteq \langle A \cup e \rangle</tex>. Докажем обратное: <tex>\langle A  \cup e \rangle \subseteq \langle A \rangle</tex>.<br>Воспользуемся вторым определением оператора замыкания. Рассмотрим <tex>f \in \langle A \cup e \rangle</tex>. По [[Ранговая_функция,_полумодулярность|полумодулярности ранговой функции]] имеем: <br><tex>r(A \cup e) + r(A \cup f) \geqslant r(A \cup e \cup f) + r((A \cup e) \cap (A \cup f)) \geqslant r(A \cup e \cup f) + r(A)</tex>.<br>Но  <tex>r(A \cup e) = r(A)</tex> (так как <tex>e \in \langle A \rangle</tex>), значит, <tex>r(A \cup f) \geqslant r(A \cup e \cup f)</tex>, что в свою очередь влечет <tex>r(A \cup f) = r(A \cup e \cup f)</tex>.<br>Но так как <tex>f \in  \langle A \cup e \rangle</tex> и <tex>e \in \langle A \rangle</tex>, то имеем <tex>r(A) = r(A \cup e) = r(A \cup e \cup f) = r(A \cup f)</tex>.<br>Следовательно, по определению, <tex>f \in \langle A \rangle</tex>. <br>В силу произвольности <tex>f: \langle A \cup e \rangle \subseteq \langle A \rangle</tex>.
 
# По первому свойству очевидно, что <tex>\langle A \rangle \subseteq \langle A \cup e \rangle</tex>. Докажем обратное: <tex>\langle A  \cup e \rangle \subseteq \langle A \rangle</tex>.<br>Воспользуемся вторым определением оператора замыкания. Рассмотрим <tex>f \in \langle A \cup e \rangle</tex>. По [[Ранговая_функция,_полумодулярность|полумодулярности ранговой функции]] имеем: <br><tex>r(A \cup e) + r(A \cup f) \geqslant r(A \cup e \cup f) + r((A \cup e) \cap (A \cup f)) \geqslant r(A \cup e \cup f) + r(A)</tex>.<br>Но  <tex>r(A \cup e) = r(A)</tex> (так как <tex>e \in \langle A \rangle</tex>), значит, <tex>r(A \cup f) \geqslant r(A \cup e \cup f)</tex>, что в свою очередь влечет <tex>r(A \cup f) = r(A \cup e \cup f)</tex>.<br>Но так как <tex>f \in  \langle A \cup e \rangle</tex> и <tex>e \in \langle A \rangle</tex>, то имеем <tex>r(A) = r(A \cup e) = r(A \cup e \cup f) = r(A \cup f)</tex>.<br>Следовательно, по определению, <tex>f \in \langle A \rangle</tex>. <br>В силу произвольности <tex>f: \langle A \cup e \rangle \subseteq \langle A \rangle</tex>.
 
# Следует из третьего свойства: <tex>\forall e \in \langle A \rangle : \langle A \cup e \rangle = \langle A \rangle</tex>, а значит, <tex>\langle \langle A \rangle \rangle = \langle A \cup \langle A \rangle \rangle = \langle A \cup e_1 \cup e_2 \cup e_3 \cup \ldots \rangle = \langle A \rangle</tex> (где <tex>e_1, e_2, \ldots \in \langle A \rangle</tex>)
 
# Следует из третьего свойства: <tex>\forall e \in \langle A \rangle : \langle A \cup e \rangle = \langle A \rangle</tex>, а значит, <tex>\langle \langle A \rangle \rangle = \langle A \cup \langle A \rangle \rangle = \langle A \cup e_1 \cup e_2 \cup e_3 \cup \ldots \rangle = \langle A \rangle</tex> (где <tex>e_1, e_2, \ldots \in \langle A \rangle</tex>)
 +
}}
 +
 +
== Покрытие ==
 +
 +
{{Определение
 +
|definition = Пусть <tex>M =\; \langle X,I \rangle</tex> {{---}} матроид. Тогда '''покрытие''' (англ. ''span'') множества <tex>A \subseteq X</tex> {{---}} это множество <tex> span(A) = \mathcal {f} x \in X \; |\; r(A) = r(A \cup x) \mathcal {g}</tex>
 +
}}
 +
{{Определение
 +
|definition = <tex> span(A) = A \cup \mathcal {f} x \in X \; |\; \forall S \subseteq A \setminus x,\ S \in I,\ |S| = r(A) :\ S \cup x \notin I \mathcal {g} </tex>
 +
}}
 +
 +
{{Утверждение
 +
|statement=Эти определения эквивалентны.
 +
|proof=Понятно, что элементы из <tex> A </tex> подходят под оба определения. Для остальных же <tex> x </tex> равенство <tex> \ r(A) = r(A \cup x) </tex> означает, что не найдётся множеств <tex> S' \subseteq A \cup x :\ S' \in I,\ |S'| > r(A). </tex> Для такого <tex> S' </tex> обязательно будет выполнено <tex> x \in S', </tex> в противном случае <tex> S' \subseteq A, </tex> откуда следует <tex> r(A) \geqslant |S'|. </tex> Следовательно для <tex> S = S' \setminus x </tex> верно <tex> S \subseteq A,\ S \in I. </tex> Из последнего получается, что <tex> r(A) \geqslant |S|, </tex> и учитывая <tex> r(A) < |S'|,\ |S| + 1 = |S'| </tex> имеем <tex> r(A) = |S|. </tex>
 +
 +
Иначе говоря, не должно существовать множеств <tex> S \subseteq A,\ x \notin S,\ S \in I,\ |S| = r(A):\ S' = S \cup x \in I. </tex>
 +
}}
 +
 +
{{Утверждение
 +
|statement=Для множества <tex> A \in X </tex> выполнено <tex> span(A) \subseteq \langle A \rangle. </tex>
 +
|proof=Покажем, что следующее определение замыкания равносильно тому, которое [[Оператор замыкания для матроидов | было дано]] ранее:
 +
: <tex>\langle A \rangle = A \cup \mathcal {f} x \in X \; |\; \exists H \subseteq A \setminus x, \; H \in I , \; |H| = r(A) :\ H \cup x \notin I \mathcal {g}</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> H' \cup x \notin I </tex> также будет выполнено, поскольку в противном случае <tex> H \cup x \notin I </tex> будет неверно (в силу 2-ой аксиомы матроидов).
 +
Второе ограничение {{---}} <tex> H \subseteq A \setminus x </tex> вместо <tex> H \subseteq A </tex> {{---}} подразумевается само собой, поскольку в случае <tex> x \in H </tex> не могут одновременно выполнятся <tex> H \in I </tex> и <tex> H \cup x \notin I. </tex>
 +
}}
 +
 +
 +
{{Теорема
 +
|id = theorem2
 +
|statement = Покрытие обладает следующими свойствами:
 +
# <tex> A, B \in X;\ A \subseteq span(B) \ \Rightarrow \ span(A) \subseteq span(B) </tex>
 +
# <tex> A \in X,\ p \in X \setminus A,\ q \in span(A \cup p) \Rightarrow p \in span(A \cup q) </tex>
 +
|proof =
 +
}}
 +
 +
 +
== Закрытые множества ==
 +
{{Определение
 +
|definition = Множество <tex>A \subseteq X</tex> называется '''закрытым''' (англ. ''closed set'', ''flat''), если <tex> span(A) = A. </tex> Класс закрытых множеств обозначается <tex> \mathcal L. </tex>
 +
}}
 +
 +
{{Теорема
 +
|id = theorem3
 +
|statement = Замкнутые множества обладают следующими свойствами:
 +
# <tex> A, B \in \mathcal L \ \; \Rightarrow \ A \cap B \in \mathcal L </tex>
 +
# Если <tex> F \in \mathcal L,\ p \in X \setminus A </tex> и <tex> F' </tex> {{---}} наименьшее по включению закрытое множество, содержащее <tex> F \cup p, </tex> тогда не существует <tex> F'' \in \mathcal L :\ F \subseteq F'' \subseteq F'. </tex>
 +
|proof =
 
}}
 
}}
  

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

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

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