Оператор замыкания для матроидов — различия между версиями
Martoon (обсуждение | вклад) м |
м (rollbackEdits.php mass rollback) |
||
(не показана 21 промежуточная версия 6 участников) | |||
Строка 1: | Строка 1: | ||
{{Определение | {{Определение | ||
− | |definition = Пусть <tex>M =\; \langle X,I \rangle</tex> {{---}} [[Определение матроида|матроид]]. Тогда '''замыкание (closure | + | |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> |
− | }} | + | }} <!---ну хз кто догадался так записать, я исправляю такое без разрешения.)))---> |
+ | Другими словами, замыкание множества <tex> A </tex> {{---}} это все элементы из <tex> A, </tex> а также такие <tex> x \in X, </tex> которые при добавлении к некоторым независимым подмножествам <tex> A </tex> не оставляют их независимыми. | ||
+ | |||
{{Лемма | {{Лемма | ||
|statement = Пусть <tex>M =\; \langle X,I \rangle</tex> {{---}} матроид, <tex>A \subseteq X</tex>. Тогда <tex>r(A) = r(\langle A \rangle),</tex> где <tex>r</tex> {{---}} [[Ранговая функция, полумодулярность|ранг]]. | |statement = Пусть <tex>M =\; \langle X,I \rangle</tex> {{---}} матроид, <tex>A \subseteq X</tex>. Тогда <tex>r(A) = r(\langle A \rangle),</tex> где <tex>r</tex> {{---}} [[Ранговая функция, полумодулярность|ранг]]. | ||
|proof = | |proof = | ||
− | Пусть существуют множества <tex>B, D \in I:\ B \subseteq A,\ D \subseteq \langle A \rangle,\ |B| = r(A) < r(\langle A \rangle) = |D|.</tex> Тогда по | + | Пусть существуют множества <tex>B, D \in I:\ B \subseteq A,\ D \subseteq \langle A \rangle,\ |B| = r(A) < r(\langle A \rangle) = |D|.</tex> Тогда по [[Определение матроида | 3-ей аксиоме]] <tex>\exists p \in D \setminus B :\ B \cup p \in I.</tex> Так как <tex>B</tex> {{---}} максимальное независимое множество из <tex> A </tex>, то <tex>p \notin A,</tex> то есть <tex> p \in \langle A \rangle \setminus A. </tex> Согласно определению замыкания возьмём максимальное по мощности множество <tex>H \subseteq A:\ H \in I,\ H\cup p \notin I.</tex> Поскольку <tex> |H| \leqslant |B| < |B \cup p|,</tex> то по аксиоме замены существует <tex>q \in (B \cup p)\setminus H :\ H \cup q \in I.</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>). | Если <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> | ||
}} | }} | ||
Строка 16: | Строка 32: | ||
# <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>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> | # <tex>\langle \langle A \rangle \rangle = \langle A \rangle </tex> | ||
|proof = | |proof = | ||
− | # Положим <tex>x \in \langle A \rangle.</tex> В соответствии с определением оператора замыкания есть 2 случая: | + | # Положим <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> | ||
# Опять два случая: | # Опять два случая: | ||
− | #* <tex> q \in A \cup p. </tex> Зная, что <tex> | + | #* <tex> q \in A \cup p. </tex> Зная, что <tex> q \notin \langle A \rangle, </tex> приходим к <tex> q = p, </tex> чего нам более чем достаточно. |
#* <tex> \exists H \subseteq A \cup p :\ H \in I,\ H \cup q \notin I. </tex> | #* <tex> \exists H \subseteq A \cup p :\ H \in I,\ H \cup q \notin I. </tex> | ||
#*: Заметим, что <tex> p \in H </tex>, иначе бы <tex> H </tex> подходило для <tex> q \in \langle A \rangle, </tex> поэтому запишем имеющееся у нас иначе, положив <tex> H' = H \setminus p: </tex> | #*: Заметим, что <tex> p \in H </tex>, иначе бы <tex> H </tex> подходило для <tex> q \in \langle A \rangle, </tex> поэтому запишем имеющееся у нас иначе, положив <tex> H' = H \setminus p: </tex> | ||
Строка 28: | Строка 45: | ||
#*: <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 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>) | ||
}} | }} | ||
− | == | + | == Смотри также == |
− | + | * [[Покрытия, закрытые множества]] | |
+ | * [[Двойственный матроид]] | ||
== Источники информации == | == Источники информации == | ||
− | ''Асанов М. О., Баранский В. А., Расин В. В.'' {{---}} Дискретная математика: Графы, матроиды, алгоритмы. '''ISBN 978-5-8114-1068-2''' | + | *''Асанов М. О., Баранский В. А., Расин В. В.'' {{---}} Дискретная математика: Графы, матроиды, алгоритмы. '''ISBN 978-5-8114-1068-2''' |
+ | * [[wikipedia:en:Matroid#Closure operators | Wikipedia {{---}} Matroid]] | ||
+ | * [[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] | ||
[[Категория:Алгоритмы и структуры данных]] | [[Категория:Алгоритмы и структуры данных]] | ||
[[Категория:Матроиды]] | [[Категория:Матроиды]] | ||
+ | [[Категория:Основные факты теории матроидов]] |
Текущая версия на 19:12, 4 сентября 2022
Определение: |
Пусть матроид. Тогда замыкание (англ. closure) множества — это множество такое, что | —
Другими словами, замыкание множества
— это все элементы из а также такие которые при добавлении к некоторым независимым подмножествам не оставляют их независимыми.
Лемма: |
Пусть ранг. — матроид, . Тогда где — |
Доказательство: |
Пусть существуют множества 3-ей аксиоме Так как — максимальное независимое множество из , то то есть Согласно определению замыкания возьмём максимальное по мощности множество Поскольку то по аксиоме замены существует Если Тогда по то но в силу (противоречие с максимальностью множества ). Если то (противоречит выбору множества ). |
Определение: |
Пусть матроид. Тогда замыкание (англ. closure) множества — это множество такое, что , где - ранговая функция | —
Лемма: |
Данное определение эквивалентно предыдущему |
Доказательство: |
Пусть
|
Теорема: |
Оператор замыкания для матроидов обладает следующими свойствами:
|
Доказательство: |
|
Смотри также
Источники информации
- Асанов М. О., Баранский В. А., Расин В. В. — Дискретная математика: Графы, матроиды, алгоритмы. ISBN 978-5-8114-1068-2
- Wikipedia — Matroid
- Википедия — Матроид
- sensagent.com — Matroid
- Michel X. Goemans: Advanced Combinatorial Optimization, Lecture 11: Matroid Intersection