Материал из Викиконспекты
|
|
| Строка 11: |
Строка 11: |
| | |proof = | | |proof = |
| | # Пусть <tex>\langle A \rangle \not\subset \langle B \rangle,</tex> тогда <tex>\exists x \notin \langle B \rangle, x \in \langle A \rangle.</tex> Следовательно, <tex>\exists C \in I, C \subset A : C \cup x \notin I.</tex> Но так как <tex>C \subset B,</tex> то <tex>x \in \langle B \rangle.</tex> Получили противоречие. | | # Пусть <tex>\langle A \rangle \not\subset \langle B \rangle,</tex> тогда <tex>\exists x \notin \langle B \rangle, x \in \langle A \rangle.</tex> Следовательно, <tex>\exists C \in I, C \subset A : C \cup x \notin I.</tex> Но так как <tex>C \subset B,</tex> то <tex>x \in \langle B \rangle.</tex> Получили противоречие. |
| − | # Так как <tex>q \in \langle A \cup p \rangle </tex> и <tex>q \notin \langle A \rangle,</tex> то существует зависимое множество <tex>\mathcal {f} a_1, a_2, ... a_n, p, q \mathcal {g} (a_i \in A).</tex> Заметим, что множество <tex>\mathcal {f} a_1, a_2, ... a_n, q \mathcal {g} \in I.</tex> То есть <tex>\mathcal {f} a_1, a_2, ... a_n, p, q \mathcal {g} - </tex> цикл. Ч.т.д. | + | # Так как <tex>q \in \langle A \cup p \rangle </tex> и <tex>q \notin \langle A \rangle,</tex> то существует независимое множество <tex>B : B \subset A \cup p, B \cup q \notin I.</tex> Так как <tex>q \notin \langle A \rangle,</tex> то <tex>p \in B, (B - p)\cup q \in I.</tex> Тогда <tex>((B - p)\cup q) \cup p \notin I,</tex> то есть <tex>p \in \langle A \cup q \rangle.</tex> |
| | }} | | }} |
Версия 00:42, 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]A \subset B \Rightarrow \langle A \rangle \subset \langle B \rangle[/math]
- [math]q \notin \langle A \rangle,\; q \in \langle A \cup p \rangle \Rightarrow p \in \langle A \cup q \rangle[/math]
- [math]\langle \langle A \rangle \rangle = \langle A \rangle [/math]
|
| Доказательство: |
| [math]\triangleright[/math] |
- Пусть [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] Получили противоречие.
- Так как [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 - p)\cup q \in I.[/math] Тогда [math]((B - p)\cup q) \cup p \notin I,[/math] то есть [math]p \in \langle A \cup q \rangle.[/math]
|
| [math]\triangleleft[/math] |
