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

Материал из Викиконспекты
Перейти к: навигация, поиск
м
(Покрытие)
Строка 36: Строка 36:
  
 
{{Определение
 
{{Определение
|definition = Пусть <tex>M =\; \langle X,I \rangle</tex> {{---}} матроид. Тогда '''покрытие''' (''span'') множества <tex>A \subseteq X</tex> {{---}} это множество <tex> span(A) \subseteq X </tex> такое, что <tex> span(A) = \mathcal {f} x \in X \; |\; r(A) = r(A \cup x) \mathcal {g}</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 \cup x \notin I \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=Эти определения эквивалентны.
 
|statement=Эти определения эквивалентны.
|proof=
+
|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>
 
}}
 
}}
  
Строка 54: Строка 56:
 
|proof =
 
|proof =
 
# Выпишем несколько полезных нам фактов.
 
# Выпишем несколько полезных нам фактов.
#* <tex> r(A) \leqslant r(span(B)) </tex> (так как <tex> A \subseteq span(B) </tex><ref>Свойство ранга</ref>)
+
#* <tex> r(A) \leqslant r(span(B)) </tex> (так как <tex> A \subseteq span(B) </tex>)<ref>Свойство ранга</ref>
 
#* <tex> r(A) = r(span(A)) </tex>
 
#* <tex> r(A) = r(span(A)) </tex>
#*: Предположим <tex> r(A) < r(span(A)) </tex>, тогда по определению ранга имеем <tex> \exists D \in I,\ D \subseteq span(A),\ |D| = r(span(A)) </tex>. Учитывая <tex> |D| > r(A) </tex>, будет <tex> D \nsubseteq A. </tex>
+
#*: Предположим <tex> r(A) < r(span(A)) </tex>. Тогда по определению ранга <tex> \exists D \subseteq span(A), D \in I, |D| = r(span(A)) </tex>.
#*: Возьмём <tex> S, p:\ S \subseteq A \cap D,\ p \in D \setminus A </tex>.
+
#*: Положим <tex> S = D \cap A, p \in D \setminus A. </tex> 
 +
 
 +
}}
 +
 
 +
== Замкнутые множества ==
 +
{{Определение
 +
|definition = Множество <tex>A \subseteq X</tex> называется '''замкнутым''' (''closed'', ''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 =
 +
}}
  
 
== Примечания ==
 
== Примечания ==

Версия 11:50, 13 июня 2014

Замыкание

Определение:
Пусть [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 \mathcal {f} x \in X \; |\; \exists H \subseteq A :\ H \in I ,\; H \cup x \notin I \mathcal {g}[/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] Тогда по аксиоме замен[1] [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]
Теорема:
Оператор замыкания для матроидов обладает следующими свойствами:
  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]\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 \langle A \rangle \rangle [/math]. Предположим [math]\exists p \in \langle \langle A \rangle \rangle \setminus \langle A \rangle.[/math] Возьмем максимальное по мощности множество [math]B \in I :\ B \subseteq A.[/math] Так как [math]p \notin \langle A \rangle,[/math] то по определению замыкания [math]B \cup p \in I.[/math] Тогда, последовательно применив вышеуказанную лемму, дважды определение ранга и снова лемму, получим [math]r(\langle A \rangle) = r(\langle \langle A \rangle \rangle) \geqslant |B \cup p| = r(A) + 1 = r(\langle A \rangle) + 1,[/math] что невозможно.
[math]\triangleleft[/math]

Покрытие

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


Определение:
[math] 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} [/math]


Утверждение:
Эти определения эквивалентны.
[math]\triangleright[/math]

Понятно, что [math] x \in A [/math] подходят под оба определения. Для остальных же [math] x \ r(A) = r(A \cup x) [/math] означает, что нету множеств [math] S' \in I,\ S' \subseteq A \cup x,\ |S'| \gt r(A). [/math] Для такого [math] S' [/math] обязательно будет выполнено [math] x \in S', [/math] в противном случае [math] S' \subseteq A, [/math] и тогда [math] r(A) \geqslant |S'|ю [/math] Тогда для [math] S = S' \setminus x [/math] верно [math] S \subseteq A,\ S \in I. [/math] Из последнего получается, что [math] r(A) \geqslant |S|, [/math] и учитывая [math] r(A) \lt |S'|,\ |S| + 1 = |S'| [/math] имеем [math] r(A) = |S|. [/math]

Другими словами, не должно существовать множеств [math] S \subseteq A,\ S \in I,\ |S| = r(A):\ S' = S \cup x \in I. [/math]
[math]\triangleleft[/math]
Теорема:
Покрытие обладает следующими свойствами:
  1. [math] A, B \in X;\ A \subseteq span(B) \ \Rightarrow \ span(A) \subseteq span(B) [/math]
  2. [math] A \in X,\ p \in X \setminus A,\ q \in span(A \cup p) \Rightarrow p \in span(A \cup q) [/math]
Доказательство:
[math]\triangleright[/math]
  1. Выпишем несколько полезных нам фактов.
    • [math] r(A) \leqslant r(span(B)) [/math] (так как [math] A \subseteq span(B) [/math])[2]
    • [math] r(A) = r(span(A)) [/math]
      Предположим [math] r(A) \lt r(span(A)) [/math]. Тогда по определению ранга [math] \exists D \subseteq span(A), D \in I, |D| = r(span(A)) [/math].
      Положим [math] S = D \cap A, p \in D \setminus A. [/math]
[math]\triangleleft[/math]

Замкнутые множества

Определение:
Множество [math]A \subseteq X[/math] называется замкнутым (closed, flat), если [math] span(A) = A. [/math] Множество замкнутых множеств обозначается [math] \mathcal L [/math]


Теорема:
Замкнутые множества обладают следующими свойствами:
  1. [math] A, B \in \mathcal L \ \Rightarrow \ A \cap B \in \mathcal L [/math]
  2. Если [math] F \in \mathcal L,\ p \in X \setminus A [/math] и [math] F' [/math] — наименьшее по включению замкнутое множество, содержащее [math] F \cup p, [/math] тогда не существует [math] F'' \in \mathcal L :\ F \subseteq F'' \subseteq F'. [/math]

Примечания

  1. Определение матроида, 3-я аксиома
  2. Свойство ранга

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