Изменения

Перейти к: навигация, поиск

Оператор замыкания для матроидов

917 байт добавлено, 17:19, 16 июня 2015
Дополнительное свойство замыкания
# <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>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>
|proof =
# Положим <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>\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> 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> \langle A \rangle \subseteq \langle \langle A \rangle cup e \rangle </tex>. Предположим Докажем обратное: <tex>\exists p langle A \cup e \in rangle \langle subseteq \langle A \rangle </tex>.<br>Воспользуемся вторым определением оператора замыкания. Рассмотрим <tex>f \rangle \setminus in \langle A \cup e \rangle.</tex> Возьмем максимальное по мощности множество . По [[Ранговая_функция,_полумодулярность|полумодулярности ранговой функции]] имеем: <br><tex>B r(A \cup e) + r(A \cup f) \geqslant r(A \cup e \cup f) + r((A \cup e) \cap (A \cup f)) \in I :geqslant r(A \ B cup e \subseteq cup f) + r(A)</tex>.<br>Но <tex>r(A \cup e) = r(A)</tex> Так (так как <tex>p e \notin in \langle A \rangle,</tex> то по определению замыкания ), значит, <tex>B r(A \cup p f) \geqslant r(A \in I.cup e \cup f)</tex> Тогда, последовательно применив вышеуказанную лемму, дважды [[Ранговая функция, полумодулярность | определение ранга]] и снова лемму, получим что в свою очередь влечет <tex>r(\langle A \ranglecup f) = r(A \langle 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) \geqslant |B = r(A \cup p| e) = r(A\cup e \cup f) + 1 = 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) + 1= \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 ... \rangle = \langle A \rangle</tex> что невозможно(где <tex>e_1, e_2, ...\in \langle A \rangle</tex>)
}}
116
правок

Навигация