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

Материал из Викиконспекты
Перейти к: навигация, поиск
м
м
Строка 1: Строка 1:
 
{{Определение
 
{{Определение
|definition = <tex>M =\; \langle X,I \rangle</tex> - матроид. Тогда '''замыкание (closure)''' множества <tex>A \subset X</tex> - это множество <tex>\langle A \rangle \subset X</tex> такое, что <tex>\langle A \rangle = A \cup \mathcal {f} x\; |\; \exists B \subset A : B \in I ,\; B \cup x \notin I \mathcal {g}</tex>
+
|definition = <tex>M =\; \langle X,I \rangle</tex> - [[Определение матроида|матроид]]. Тогда '''замыкание (closure)''' множества <tex>A \subset X</tex> - это множество <tex>\langle A \rangle \subset X</tex> такое, что <tex>\langle A \rangle = A \cup \mathcal {f} x\; |\; \exists B \subset A : B \in I ,\; B \cup x \notin I \mathcal {g}</tex>
 
}}
 
}}
  
 
{{Лемма
 
{{Лемма
|statement = <tex>M =\; \langle X,I \rangle</tex> - матроид, <tex>A \subset X</tex>. Тогда <tex>r(A) = r(\langle A \rangle),</tex> где <tex>r</tex> - ранг множества <tex>A.</tex>
+
|statement = <tex>M =\; \langle X,I \rangle</tex> - матроид, <tex>A \subset X</tex>. Тогда <tex>r(A) = r(\langle A \rangle),</tex> где <tex>r</tex> - [[Ранговая функция, полумодулярность|ранг]] множества <tex>A.</tex>
 
|proof =
 
|proof =
 
Пусть существуют такие множества <tex>B, C \in I: B \subset A, C \subset \langle A \rangle, |B| = r(A) < r(\langle A \rangle) = |C|.</tex> Тогда по аксиоме замен <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 \subset A: D \in I, D\cup p \notin I.</tex> В силу аксиомы наследования можно считать, что <tex>|D| = |B|.</tex> Тогда <tex>r(A) = |D| < |B \cup p|.</tex> По аксиоме замены существует <tex>q \in (A \cup p)\setminus D : D \cup q \notin I.</tex>  
 
Пусть существуют такие множества <tex>B, C \in I: B \subset A, C \subset \langle A \rangle, |B| = r(A) < r(\langle A \rangle) = |C|.</tex> Тогда по аксиоме замен <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 \subset A: D \in I, D\cup p \notin I.</tex> В силу аксиомы наследования можно считать, что <tex>|D| = |B|.</tex> Тогда <tex>r(A) = |D| < |B \cup p|.</tex> По аксиоме замены существует <tex>q \in (A \cup p)\setminus D : D \cup q \notin I.</tex>  

Версия 01:19, 3 июня 2011

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


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

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

Если [math]q \in B,[/math] то [math](D \cup q) \subset A[/math](противоречит максимальности множества [math]D[/math]). Если [math]q = p,[/math] то [math](D \cup p) \in I[/math](противоречит выбору множества [math]D[/math]).
[math]\triangleleft[/math]
Теорема:
Оператор замыкания для матроидов обладает следующими свойствами:
  1. [math]A \subset B \Rightarrow \langle A \rangle \subset \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]\langle A \rangle \not\subset \langle B \rangle,[/math] тогда [math]\exists x \notin \langle B \rangle, x \in \langle A \rangle.[/math] Следовательно, [math]\exists C \in I, C \subset A : C \cup x \notin I.[/math] Но так как [math]C \subset B,[/math] то [math]x \in \langle B \rangle.[/math] Получили противоречие.
  2. Так как [math]q \in \langle A \cup p \rangle [/math] и [math]q \notin \langle A \rangle,[/math] то существует независимое множество [math]B : B \subset A \cup p, B \cup q \notin I.[/math] Так как [math]q \notin \langle A \rangle,[/math] то [math]p \in B, (B \setminus p)\cup q \in I.[/math] Тогда [math]((B \setminus p)\cup q) \cup p \notin I,[/math] то есть [math]p \in \langle A \cup q \rangle.[/math]
[math]\triangleleft[/math]