Изменения

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

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

508 байт добавлено, 23:50, 13 декабря 2018
Нет описания правки
== Замыкание ==
 
{{Определение
|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> плюс а также такие <tex> x \in X, </tex> которые при добавлении к некоторым независимым подмножествам <tex> A </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>).
}}
 
{{Определение
|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 = \{ x \in X \; |\; r(A \cup x) = r(A) \}</tex>, где <tex>r: 2^X \to \mathbb{N}</tex> - [[Ранговая_функция,_полумодулярность|ранговая функция]]
}}
 
{{Лемма
|statement = Данное определение эквивалентно предыдущему
|proof =
Пусть <tex>\langle A \rangle_1</tex> {{---}} замыкание <tex>A</tex> в смысле первого определения, <tex>\langle A \rangle_2</tex> {{---}} замыкание <tex>A</tex> в смысле второго определения.<br>
Покажем, что <tex>\langle A \rangle_1 = \langle A \rangle_2</tex>
 
# <tex>\langle A \rangle_1 \subseteq \langle A \rangle_2</tex> <br> По предыдущей лемме, <tex>r(A) = r(\langle A \rangle_1)</tex>, а значит, <tex>\forall a \in \langle A \rangle_1 : r(A \cup a) = r(A)</tex>, а значит, <tex>a \in \langle A \rangle_2</tex>. <br> В силу произвольности <tex>a</tex>, <tex>\langle A \rangle_1 \subseteq \langle A \rangle_2</tex>.
# <tex>\langle A \rangle_2 \subseteq \langle A \rangle_1</tex> <br> Рассмотрим <tex>a \in \langle A \rangle_2 : r(A \cup a) = r(A)</tex>. Возьмем <tex>B \subseteq A, \; B \in I</tex> {{---}} наибольшее независимое подмножество <tex>A</tex>. Тогда <tex>B \cup a \notin I</tex>, так как иначе <tex>r(A \cup e) = |B \cup e| > |B| = r(A)</tex>. <br> Следовательно, <tex>b \in \langle A \rangle_1</tex>, и в силу произвольности <tex>b</tex>, <tex>\langle A \rangle_2 \subseteq \langle A \rangle_1</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>e \in \langle A \rangle \Rightarrow \langle A \cup e \rangle = \langle A \rangle</tex>
# <tex>\langle \langle A \rangle \rangle = \langle A \rangle </tex>
|proof =
# Положим <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>\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> 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> \langle A \rangle \subseteq \langle \langle A \rangle cup e \rangle </tex>. Предположим Докажем обратное: <tex>\exists p \in \langle \langle A \rangle cup e \rangle \setminus subseteq \langle A \rangle.</tex> Возьмем максимальное по мощности множество .<texbr>B \in I :\ B \subseteq AВоспользуемся вторым определением оператора замыкания.Рассмотрим </tex> Так как <tex>p f \notin in \langle A \cup e \rangle,</tex> то по определению замыкания <tex>B \cup p \in I.</tex> Тогда, последовательно применив вышеуказанную лемму, дважды По [[Ранговая функцияРанговая_функция, полумодулярность _полумодулярность| определение рангаполумодулярности ранговой функции]] и снова лемму, получим имеем: <br><tex>r(\langle A \ranglecup e) = + r(\langle \langle A \rangle \ranglecup f) \geqslant |B \cup p| = r(A\cup e \cup f) + 1 = r(\langle (A \rangle) + 1,</tex> что невозможно.}} == Покрытие == {{Определение|definition = Пусть <tex>M =\; \langle X,I \rangle</tex> {{---}} матроид. Тогда '''покрытие''' (англ. ''span''cup e) множества <tex>A \subseteq X</tex> {{---}} это множество <tex> spancap (A) = \mathcal {cup f} x )) \in X \; |\; geqslant r(A\cup e \cup f) = + r(A \cup x) \mathcal {g}</tex>}}{{Определение|definition = .<br>Но <tex> spanr(A) = A \cup \mathcal {f} x \in X \; |\; \forall S \subseteq A,\ S \in I,\ |S| e) = r(A) :\ S \cup x \notin I \mathcal {g} </tex> }} {{Утверждение|statement=Эти определения эквивалентны.|proof=Понятно, что элементы из (так как <tex> e \in \langle A \rangle</tex> подходят под оба определения. Для остальных же <tex> x </tex> равенство ), значит, <tex> \ r(A\cup f) = \geqslant r(A \cup xe \cup f) </tex> означает, что не найдётся множеств в свою очередь влечет <tex> S' \subseteq r(A \cup x :\ S' \in I,\ |S'| > f) = r(A\cup e \cup f). </tex> Для такого .<texbr> S' Но так как </tex> обязательно будет выполнено <tex> x f \in S', </tex> в противном случае <tex> S' \subseteq langle A, </tex> откуда следует <tex> r(A) \geqslant |S'|. cup e \rangle</tex> Следовательно для и <tex> S = S' e \setminus x </tex> верно <tex> S in \subseteq langle A,\ S \in I. rangle</tex> Из последнего получается, что то имеем <tex> r(A) = r(A \geqslant |S|, </tex> и учитывая <tex> cup e) = r(A\cup e \cup f) < |S'|,\ |S| + 1 = |S'| </tex> имеем <tex> r(A\cup f) = |S|. </tex>  Иначе говоря.<br>Следовательно, по определению, не должно существовать множеств <tex> S \subseteq A,\ S f \in I,\ |S| = r(langle A):\ S' = S \cup x \in I. rangle</tex> }} {{Теорема|id = theorem2|statement = Покрытие обладает следующими свойствами:# . <br>В силу произвольности <tex> f: \langle A, B \in X;cup e \ A rangle \subseteq span(B) \ \Rightarrow \ span(langle A) \subseteq span(B) rangle</tex>.# Следует из третьего свойства: <tex> A \in X,\ p forall e \in X \setminus langle A,\ q rangle : \in span(langle A \cup p) e \Rightarrow p rangle = \in span(langle A \cup q) </tex>|proof =}} == Закрытые множества =={{Определение|definition = Множество <tex>A \subseteq Xrangle</tex> называется '''закрытым''' (''closed set'', ''flat'')а значит, если <tex> span(\langle \langle A) \rangle \rangle = A. </tex> Класс закрытых множеств обозначается <tex> \mathcal L </tex>}} {{Теорема|id = theorem3|statement = Замкнутые множества обладают следующими свойствами:# <tex> langle A, B \in cup \mathcal L langle A \ rangle \; \Rightarrow rangle = \ langle A \cap B cup e_1 \in cup e_2 \mathcal L </tex># Если <tex> F cup e_3 \in cup \mathcal L,ldots \ p rangle = \in X langle A \setminus A rangle</tex> и (где <tex> F' </tex> {{---}} наименьшее по включению закрытое множествоe_1, e_2, содержащее <tex> F \cup p, </tex> тогда не существует <tex> F'' ldots \in \mathcal L :langle A \ F \subseteq F'' \subseteq F'. rangle</tex> |proof =)
}}
== Примечания Смотри также ==<references/>* [[Покрытия, закрытые множества]]* [[Двойственный матроид]]
== Источники информации ==
* [[wikipedia:ru:Матроид#Определение в терминах правильного замыкания | Википедия {{---}} Матроид]]
* [http://dictionary.sensagent.com/Matroid/en-en/ sensagent.com {{---}} Matroid]
* [http://math.mit.edu/~goemans/18438F09/lec11.pdf Michel X. Goemans: Advanced Combinatorial Optimization, Lecture 11: Matroid Intersection]
[[Категория:Алгоритмы и структуры данных]]
[[Категория:Матроиды]]
[[Категория:Основные факты теории матроидов]]
Анонимный участник

Навигация