Редактирование: Оператор замыкания для матроидов
Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.
Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия | Ваш текст | ||
Строка 1: | Строка 1: | ||
+ | == Замыкание == | ||
+ | |||
{{Определение | {{Определение | ||
− | |definition = Пусть <tex>M =\; \langle X,I \rangle</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 \mathcal {f} x \in X \; |\; \exists H \subseteq A :\ H \in I ,\; H \cup x \notin I \mathcal {g}</tex> |
− | }} | + | }} |
− | Другими словами, замыкание множества <tex> A </tex> {{---}} это все элементы из <tex> A | + | Другими словами, замыкание множества <tex> A </tex> {{---}} это все элементы из <tex> A </tex> плюс такие <tex> x \in X, </tex> которые при добавлении к некоторым независимым подмножествам <tex> A </tex> не оставляют их независимыми. |
Строка 11: | Строка 13: | ||
Если <tex>q \in B,</tex> то <tex>(H \cup q) \subseteq A,\ </tex> но <tex> (H \cup q) \cup p \notin I </tex> в силу <tex> H \cup p \notin I </tex> (противоречие с максимальностью множества <tex>H</tex>). Если <tex>q = p,</tex> то <tex>(H \cup p) \in I</tex> (противоречит выбору множества <tex>H</tex>). | Если <tex>q \in B,</tex> то <tex>(H \cup q) \subseteq A,\ </tex> но <tex> (H \cup q) \cup p \notin I </tex> в силу <tex> H \cup p \notin I </tex> (противоречие с максимальностью множества <tex>H</tex>). Если <tex>q = p,</tex> то <tex>(H \cup p) \in I</tex> (противоречит выбору множества <tex>H</tex>). | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
}} | }} | ||
Строка 32: | Строка 20: | ||
# <tex>A \subseteq B \Rightarrow \langle A \rangle \subseteq \langle B \rangle</tex> | # <tex>A \subseteq B \Rightarrow \langle A \rangle \subseteq \langle B \rangle</tex> | ||
# <tex>q \notin \langle A \rangle,\; q \in \langle A \cup p \rangle \Rightarrow p \in \langle A \cup q \rangle</tex> | # <tex>q \notin \langle A \rangle,\; q \in \langle A \cup p \rangle \Rightarrow p \in \langle A \cup q \rangle</tex> | ||
− | |||
# <tex>\langle \langle A \rangle \rangle = \langle A \rangle </tex> | # <tex>\langle \langle A \rangle \rangle = \langle A \rangle </tex> | ||
|proof = | |proof = | ||
− | # Положим <tex>x \in \langle A \rangle.</tex> В соответствии с | + | # Положим <tex>x \in \langle A \rangle.</tex> В соответствии с определением оператора замыкания есть 2 случая: |
#* <tex> x \in A. </tex> Тогда <tex> x \in B </tex>, и следовательно <tex> x \in \langle B \rangle. </tex> | #* <tex> x \in A. </tex> Тогда <tex> x \in B </tex>, и следовательно <tex> x \in \langle B \rangle. </tex> | ||
#* <tex>\exists H \subseteq A :\ H \in I,\ H \cup x \notin I.</tex> Для такого <tex> H </tex> также верно <tex>H \subseteq B,</tex> потому <tex>x \in \langle B \rangle.</tex> | #* <tex>\exists H \subseteq A :\ H \in I,\ H \cup x \notin I.</tex> Для такого <tex> H </tex> также верно <tex>H \subseteq B,</tex> потому <tex>x \in \langle B \rangle.</tex> | ||
Строка 45: | Строка 32: | ||
#*: <tex> H' \cup q \in I </tex>, в противном случае в силу <tex> H' \in I </tex> было бы <tex> q \in \langle A \rangle. </tex> | #*: <tex> H' \cup q \in I </tex>, в противном случае в силу <tex> H' \in I </tex> было бы <tex> q \in \langle A \rangle. </tex> | ||
#*: Как видим, множество <tex> H' \cup q </tex> подходит под определение <tex> p \in \langle A \cup q \rangle. </tex> | #*: Как видим, множество <tex> H' \cup q </tex> подходит под определение <tex> p \in \langle A \cup q \rangle. </tex> | ||
− | # | + | # Из определения понятно, что <tex> \langle A \rangle \subseteq \langle \langle A \rangle \rangle </tex>. Предположим <tex>\exists p \in \langle \langle A \rangle \rangle \setminus \langle A \rangle.</tex> Возьмем максимальное по мощности множество <tex>B \in I :\ B \subseteq A.</tex> Так как <tex>p \notin \langle A \rangle,</tex> то по определению замыкания <tex>B \cup p \in I.</tex> Тогда, последовательно применив вышеуказанную лемму, дважды [[Ранговая функция, полумодулярность | определение ранга]] и снова лемму, получим <tex>r(\langle A \rangle) = r(\langle \langle A \rangle \rangle) \geqslant |B \cup p| = r(A) + 1 = r(\langle A \rangle) + 1,</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,\ 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,\ S \in I,\ |S| = r(A):\ S' = S \cup x \in 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 = | ||
}} | }} | ||
− | == | + | == Примечания == |
− | + | <references/> | |
− | |||
== Источники информации == | == Источники информации == | ||
Строка 58: | Строка 80: | ||
* [[wikipedia:ru:Матроид#Определение в терминах правильного замыкания | Википедия {{---}} Матроид]] | * [[wikipedia:ru:Матроид#Определение в терминах правильного замыкания | Википедия {{---}} Матроид]] | ||
* [http://dictionary.sensagent.com/Matroid/en-en/ sensagent.com {{---}} Matroid] | * [http://dictionary.sensagent.com/Matroid/en-en/ sensagent.com {{---}} Matroid] | ||
− | |||
[[Категория:Алгоритмы и структуры данных]] | [[Категория:Алгоритмы и структуры данных]] | ||
[[Категория:Матроиды]] | [[Категория:Матроиды]] | ||
− |