Изменения

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

Покрытия, закрытые множества

69 байт добавлено, 17:45, 15 июня 2015
м
Покрытие
:если <tex> I \in L </tex>, тогда <tex>span(I) = I \cup \mathcal {f} t \; | \; I \cup {t} \in L \mathcal {g} </tex>. (1)
Действительно, если <tex> t \in span(I) \setminus I </tex>, тогда <tex> I \cup {t} \notin L </tex>, по определению независимого множества. С другой стороны, <tex> I \subseteq span(I)</tex>. Кроме того, если <tex> I \cup {t} \notin L </tex>, тогда по определению независимого множества получаем, что <tex> \exists s \in I \cup t : s \in span(I \cup {t} \setminus {s}) </tex>. Если <tex> s = t </tex>, тогда <tex> t \in span(I) </tex>. Предположим, что <tex> s \neq t </tex>, т.е. <tex> s \in I </tex>. Мы знаем, что <tex> s \in notin span(I \setminus {s}) </tex>, так как <tex> I \in L </tex>. Таким образом по 3 свойству доказывается (для <tex> T \in I \setminus {s} </tex>), <tex> t \in span(I) </tex>.
Теперь покажем, что <tex> M = (S, L) </tex> {{---}} матроид. Очевидно, <tex> \emptyset \in L </tex>. Для начала покажем, что <tex> I </tex> закрытое множество под полученным подмножеством, Пусть <tex> I \in L </tex> и <tex> J \subseteq I </tex>. Мы видим, что <tex> J \in I </tex>. Предположим наоборот, что <tex>\exists s \in J : s \in span(J \setminus {s}) </tex>. Тогда по второму свойству <tex> span(J \setminus {s}) \subseteq span(I \setminus {s})</tex>. Следовательно, <tex> s \in span( I \setminus {s})</tex>, что противоречит условию, что <tex> I \in L </tex>.  Для того чтобы проверить [[Определение матроида | 3-ю аксиому матроидов]], допустим, что <tex> I, J \in L </tex>, <tex> |I \setminus J| = 1 </tex> и <tex> |J \setminus I| = 2</tex>. Пусть <tex>I \setminus J = \mathcal {f} i\mathcal {g}</tex> и <tex>J \setminus I = \mathcal {f} {j_1, j_2} \mathcal {g}</tex>. Предположим, что <tex> I \cup {j_1} \in notin L</tex>, т.е. <tex> J \cup {i} \setminus {j_2} \in notin L</tex>, и так по (1) применяется к <tex>J \setminus {j_2} </tex>, <tex> i \in span(J \setminus {j_2}) </tex>. Поэтому, <tex> I \subseteq span(J \setminus {j_2})</tex> и <tex> span(I) \subseteq span(J \setminus {j_2}) </tex>. Таким образом <tex> j_2 \in notin span(i) </tex>(как и <tex> J \in L</tex>) и поэтому, (1) применяется к <tex> I </tex> и к <tex> I \cup {j_2} \in L </tex>.
Таким образом <tex> M </tex> является матроидом. Теперь покажем, что <tex>span = span_M</tex>. Выберем такое множество <tex> T \subseteq S </tex>, чтобы увидеть, что <tex> span(T) = span_M(T) </tex>, пусть <tex> I </tex> будет базой <tex> T </tex> (в <tex> M </tex>). Тогда используя (1), мы получаем:
:<tex>span_M(T) = T \cup \mathcal {f} x \; | \; I \cup {x} \in notin L \mathcal {g} = span(I) \subseteq(T) </tex>
Таким образом, мы показали, что <tex> span(T) \subseteq span(I)</tex> т.е. по 1 свойству <tex> T \subseteq span(I)</tex>. Теперь выберем <tex> t \in T \setminus I</tex>. В силу максимальности <tex> I </tex>, мы знаем, что <tex>I \cup t \notin L</tex>, и, следовательно, по (1) получаем, что <tex> t \in span(I) </tex>.
}}
25
правок

Навигация