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

Материал из Викиконспекты
Перейти к: навигация, поиск
м
м
Строка 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\; |\; \exists B \subseteq A :\ B \in I ,\; B \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 \mathcal {f} x \in X \; |\; \exists H \subseteq A :\ H \in I ,\; H \cup x \notin I \mathcal {g}</tex>
 
}}
 
}}
  
Строка 6: Строка 6:
 
|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, C \in I:\ B \subseteq A, C \subseteq \langle A \rangle, |B| = r(A) < r(\langle A \rangle) = |C|.</tex> Тогда по аксиоме замен<ref>[[Определение матроида | Определение матроида]], 3-я аксиома</ref> <tex>\exists p \in C \setminus B :\ B \cup p \in I.</tex> Так как <tex>B</tex> {{---}} максимально, то <tex>p \in \langle A \rangle \setminus A.</tex> По определению замыкания существует множество <tex>D \subseteq A:\ D \in I,\ D\cup p \notin I.</tex> В силу аксиомы наследования<ref>[[Определение матроида | Определение матроида]], 2-я аксиома</ref> можно считать, что <tex>|D| = |B|.</tex> Тогда <tex>r(A) = |D| < |B \cup p|.</tex> По аксиоме замены существует <tex>q \in (B \cup p)\setminus D :\ D \cup q \in I.</tex>  
+
Пусть существуют множества <tex>B, C \in I:\ B \subseteq A, C \subseteq \langle A \rangle, |B| = r(A) < r(\langle A \rangle) = |C|.</tex> Тогда по аксиоме замен<ref>[[Определение матроида | Определение матроида]], 3-я аксиома</ref> <tex>\exists p \in C \setminus B :\ B \cup p \in I.</tex> Так как <tex>B</tex> {{---}} максимально, то <tex>p \in \langle A \rangle \setminus A.</tex> По определению замыкания существует множество <tex>H \subseteq A:\ H \in I,\ H\cup p \notin I.</tex> В силу аксиомы наследования<ref>[[Определение матроида | Определение матроида]], 2-я аксиома</ref> можно считать, что <tex>|H| = |B|.</tex> Тогда <tex>r(A) = |H| < |B \cup p|.</tex> По аксиоме замены существует <tex>q \in (B \cup p)\setminus H :\ H \cup q \in I.</tex>  
  
Если <tex>q \in B,</tex> то <tex>(D \cup q) \subseteq A</tex> (противоречит максимальности множества <tex>D</tex>). Если <tex>q = p,</tex> то <tex>(D \cup p) \in I</tex> (противоречит выбору множества <tex>D</tex>).
+
Если <tex>q \in B,</tex> то <tex>(H \cup q) \subseteq A</tex> (противоречит максимальности множества <tex>H</tex>). Если <tex>q = p,</tex> то <tex>(H \cup p) \in I</tex> (противоречит выбору множества <tex>H</tex>).
 
}}
 
}}
  
Строка 18: Строка 18:
 
# <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>\exists C \in I, C \subseteq A :\ C \cup x \notin I.</tex> Но <tex>C \subseteq B,</tex> поэтому <tex>x \in \langle B \rangle.</tex>  
+
# Положим <tex>x \in \langle A \rangle.</tex> В соответствии с определением оператора замыкания есть 2 случая:
# Так как <tex>q \in \langle A \cup p \rangle </tex> и <tex>q \notin \langle A \rangle,</tex> то существует независимое множество <tex>B :\ B \subseteq A \cup p, B \cup q \notin I.</tex> Так как <tex>q \notin \langle A \rangle,</tex> то <tex>p \in B, (B \setminus p)\cup q \in I.</tex> Тогда  <tex>((B \setminus p)\cup q) \cup p \notin I,</tex> то есть <tex>p \in \langle A \cup q \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> q \in A \cup p. </tex> Зная, что <tex> p \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> p \in H </tex>, иначе бы <tex> H </tex> подходило для <tex> q \in \langle A \rangle, </tex> поэтому запишем данное нам иначе:
 +
#*:: <tex> \exists H' \subseteq A:\ H' \cup p \in I,\ (H' \cup p) \cup q \notin I. </tex>  
 +
#*: <tex> H' \cup q \in I </tex>, в противном случае в силу <tex> H' \in I </tex> было бы <tex> q \in \langle A \rangle. </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 \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> что невозможно.
 
}}
 
}}

Версия 19:53, 7 июня 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, C \in I:\ B \subseteq A, C \subseteq \langle A \rangle, |B| = r(A) \lt r(\langle A \rangle) = |C|.[/math] Тогда по аксиоме замен[1] [math]\exists p \in C \setminus B :\ B \cup p \in I.[/math] Так как [math]B[/math] — максимально, то [math]p \in \langle A \rangle \setminus A.[/math] По определению замыкания существует множество [math]H \subseteq A:\ H \in I,\ H\cup p \notin I.[/math] В силу аксиомы наследования[2] можно считать, что [math]|H| = |B|.[/math] Тогда [math]r(A) = |H| \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[/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] p \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] \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] 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]

Примечания

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

Асанов М. О., Баранский В. А., Расин В. В. — Дискретная математика: Графы, матроиды, алгоритмы. ISBN 978-5-8114-1068-2