Оператор замыкания для матроидов — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м
м (rollbackEdits.php mass rollback)
 
(не показано 14 промежуточных версий 6 участников)
Строка 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 \mathcal {f} x \in X \; |\; \exists H \subseteq A :\ H \in I ,\; H \cup x \notin I \mathcal {g}</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>
}}
+
}} <!---ну хз кто догадался так записать, я исправляю такое без разрешения.)))--->
Другими словами, замыкание множества <tex> A </tex> {{---}} это все элементы из <tex> A </tex> плюс такие <tex> x \in X, </tex> которые при добавлении к некоторым независимым подмножествам <tex> A </tex> не оставляют их независимыми.
+
Другими словами, замыкание множества <tex> A </tex> {{---}} это все элементы из <tex> A, </tex> а также такие <tex> x \in X, </tex> которые при добавлении к некоторым независимым подмножествам <tex> A </tex> не оставляют их независимыми.
  
  
Строка 10: Строка 8:
 
|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> Тогда по аксиоме замен<ref>[[Определение матроида | Определение матроида]], 3-я аксиома</ref> <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>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>
 
}}
 
}}
  
Строка 20: Строка 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>  
Строка 32: Строка 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 \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> что невозможно.
+
# По первому свойству очевидно, что <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>)
 
 
== Покрытие ==
 
 
 
{{Определение
 
|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> x \in A </tex> подходят под оба определения. Для остальных же <tex> x \ r(A) = r(A \cup x) </tex> означает, что нету множеств <tex> S' \in I,\ S' \subseteq A \cup x,\ |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/>
+
* [[Покрытия, закрытые множества]]
 +
* [[Двойственный матроид]]
  
 
== Источники информации ==
 
== Источники информации ==
Строка 80: Строка 58:
 
* [[wikipedia:ru:Матроид#Определение в терминах правильного замыкания | Википедия {{---}} Матроид]]
 
* [[wikipedia:ru:Матроид#Определение в терминах правильного замыкания | Википедия {{---}} Матроид]]
 
* [http://dictionary.sensagent.com/Matroid/en-en/ sensagent.com {{---}} Matroid]
 
* [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

Определение:
Пусть [math]M =\; \langle X,I \rangle[/math]матроид. Тогда замыкание (англ. closure) множества [math]A \subseteq X[/math] — это множество [math]\langle A \rangle \subseteq X[/math] такое, что [math]\langle A \rangle = A \cup \{ x \in X \; |\; \exists H \subseteq A :\ H \in I ,\; H \cup x \notin I \}[/math]

Другими словами, замыкание множества [math] A [/math] — это все элементы из [math] A, [/math] а также такие [math] x \in X, [/math] которые при добавлении к некоторым независимым подмножествам [math] A [/math] не оставляют их независимыми.


Лемма:
Пусть [math]M =\; \langle X,I \rangle[/math] — матроид, [math]A \subseteq X[/math]. Тогда [math]r(A) = r(\langle A \rangle),[/math] где [math]r[/math]ранг.
Доказательство:
[math]\triangleright[/math]

Пусть существуют множества [math]B, D \in I:\ B \subseteq A,\ D \subseteq \langle A \rangle,\ |B| = r(A) \lt r(\langle A \rangle) = |D|.[/math] Тогда по 3-ей аксиоме [math]\exists p \in D \setminus B :\ B \cup p \in I.[/math] Так как [math]B[/math] — максимальное независимое множество из [math] A [/math], то [math]p \notin A,[/math] то есть [math] p \in \langle A \rangle \setminus A. [/math] Согласно определению замыкания возьмём максимальное по мощности множество [math]H \subseteq A:\ H \in I,\ H\cup p \notin I.[/math] Поскольку [math] |H| \leqslant |B| \lt |B \cup p|,[/math] то по аксиоме замены существует [math]q \in (B \cup p)\setminus H :\ H \cup q \in I.[/math]

Если [math]q \in B,[/math] то [math](H \cup q) \subseteq A,\ [/math] но [math] (H \cup q) \cup p \notin I [/math] в силу [math] H \cup p \notin I [/math] (противоречие с максимальностью множества [math]H[/math]). Если [math]q = p,[/math] то [math](H \cup p) \in I[/math] (противоречит выбору множества [math]H[/math]).
[math]\triangleleft[/math]


Определение:
Пусть [math]M =\; \langle X,I \rangle[/math]матроид. Тогда замыкание (англ. closure) множества [math]A \subseteq X[/math] — это множество [math]\langle A \rangle \subseteq X[/math] такое, что [math]\langle A \rangle = \{ x \in X \; |\; r(A \cup x) = r(A) \}[/math], где [math]r: 2^X \to \mathbb{N}[/math] - ранговая функция


Лемма:
Данное определение эквивалентно предыдущему
Доказательство:
[math]\triangleright[/math]

Пусть [math]\langle A \rangle_1[/math] — замыкание [math]A[/math] в смысле первого определения, [math]\langle A \rangle_2[/math] — замыкание [math]A[/math] в смысле второго определения.
Покажем, что [math]\langle A \rangle_1 = \langle A \rangle_2[/math]

  1. [math]\langle A \rangle_1 \subseteq \langle A \rangle_2[/math]
    По предыдущей лемме, [math]r(A) = r(\langle A \rangle_1)[/math], а значит, [math]\forall a \in \langle A \rangle_1 : r(A \cup a) = r(A)[/math], а значит, [math]a \in \langle A \rangle_2[/math].
    В силу произвольности [math]a[/math], [math]\langle A \rangle_1 \subseteq \langle A \rangle_2[/math].
  2. [math]\langle A \rangle_2 \subseteq \langle A \rangle_1[/math]
    Рассмотрим [math]a \in \langle A \rangle_2 : r(A \cup a) = r(A)[/math]. Возьмем [math]B \subseteq A, \; B \in I[/math] — наибольшее независимое подмножество [math]A[/math]. Тогда [math]B \cup a \notin I[/math], так как иначе [math]r(A \cup e) = |B \cup e| \gt |B| = r(A)[/math].
    Следовательно, [math]b \in \langle A \rangle_1[/math], и в силу произвольности [math]b[/math], [math]\langle A \rangle_2 \subseteq \langle A \rangle_1[/math]
[math]\triangleleft[/math]
Теорема:
Оператор замыкания для матроидов обладает следующими свойствами:
  1. [math]A \subseteq B \Rightarrow \langle A \rangle \subseteq \langle B \rangle[/math]
  2. [math]q \notin \langle A \rangle,\; q \in \langle A \cup p \rangle \Rightarrow p \in \langle A \cup q \rangle[/math]
  3. [math]e \in \langle A \rangle \Rightarrow \langle A \cup e \rangle = \langle A \rangle[/math]
  4. [math]\langle \langle A \rangle \rangle = \langle A \rangle [/math]
Доказательство:
[math]\triangleright[/math]
  1. Положим [math]x \in \langle A \rangle.[/math] В соответствии с первым определением оператора замыкания есть 2 случая:
    • [math] x \in A. [/math] Тогда [math] x \in B [/math], и следовательно [math] x \in \langle B \rangle. [/math]
    • [math]\exists H \subseteq A :\ H \in I,\ H \cup x \notin I.[/math] Для такого [math] H [/math] также верно [math]H \subseteq B,[/math] потому [math]x \in \langle B \rangle.[/math]
  2. Опять два случая:
    • [math] q \in A \cup p. [/math] Зная, что [math] q \notin \langle A \rangle, [/math] приходим к [math] q = p, [/math] чего нам более чем достаточно.
    • [math] \exists H \subseteq A \cup p :\ H \in I,\ H \cup q \notin I. [/math]
      Заметим, что [math] p \in H [/math], иначе бы [math] H [/math] подходило для [math] q \in \langle A \rangle, [/math] поэтому запишем имеющееся у нас иначе, положив [math] H' = H \setminus p: [/math]
      [math] \exists H' \subseteq A:\ H' \cup p \in I,\ H' \cup p \cup q \notin I. [/math]
      [math] H' \cup q \in I [/math], в противном случае в силу [math] H' \in I [/math] было бы [math] q \in \langle A \rangle. [/math]
      Как видим, множество [math] H' \cup q [/math] подходит под определение [math] p \in \langle A \cup q \rangle. [/math]
  3. По первому свойству очевидно, что [math]\langle A \rangle \subseteq \langle A \cup e \rangle[/math]. Докажем обратное: [math]\langle A \cup e \rangle \subseteq \langle A \rangle[/math].
    Воспользуемся вторым определением оператора замыкания. Рассмотрим [math]f \in \langle A \cup e \rangle[/math]. По полумодулярности ранговой функции имеем:
    [math]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)[/math].
    Но [math]r(A \cup e) = r(A)[/math] (так как [math]e \in \langle A \rangle[/math]), значит, [math]r(A \cup f) \geqslant r(A \cup e \cup f)[/math], что в свою очередь влечет [math]r(A \cup f) = r(A \cup e \cup f)[/math].
    Но так как [math]f \in \langle A \cup e \rangle[/math] и [math]e \in \langle A \rangle[/math], то имеем [math]r(A) = r(A \cup e) = r(A \cup e \cup f) = r(A \cup f)[/math].
    Следовательно, по определению, [math]f \in \langle A \rangle[/math].
    В силу произвольности [math]f: \langle A \cup e \rangle \subseteq \langle A \rangle[/math].
  4. Следует из третьего свойства: [math]\forall e \in \langle A \rangle : \langle A \cup e \rangle = \langle A \rangle[/math], а значит, [math]\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[/math] (где [math]e_1, e_2, \ldots \in \langle A \rangle[/math])
[math]\triangleleft[/math]

Смотри также

Источники информации