308
правок
Изменения
м
Нет описания правки
}}
{{Определение
|definition = <tex> span(A) = A \cup \mathcal {f} x \in X \setminus A \; |\; \forall S \subseteq A \setminus x,\ S \in I,\ |S| = r(A) :\ S \cup x \notin I \mathcal {g} </tex>
}}
{{Утверждение
|statement=Эти определения эквивалентны.
|proof=Понятно, что элементы из <tex> A </tex> подходят под оба определения. Для остальных же <tex> x </tex> равенство <tex> \ r(A) = r(A \cup x) </tex> означает, что не найдётся множеств <tex> S' \subseteq A \cup x :\ S' \in I,\ |S'| > r(A). </tex> Для такого <tex> S' </tex> обязательно будет выполнено <tex> x \in S', </tex> в противном случае <tex> S' \subseteq A, </tex> откуда следует что приведёт к <tex> r(A) \geqslant |S'|. </tex> Следовательно Тогда для <tex> S = S' \setminus x </tex> верно <tex> S \subseteq A,\ S \in I. </tex> Из последнего получается, что <tex> r(A) \geqslant |S|, </tex> и учитывая <tex> r(A) < |S'|,\ |S| + 1 = |S'| </tex> имеем <tex> r(A) = |S|. </tex>
Иначе говоря, не должно существовать множеств <tex> S \subseteq A,\ x \notin S,\ S \in I,\ |S| = r(A):\ S' = S \cup x \in I. </tex>
}}
{{Утверждение
|statement=Определения замыкания и покрытия похожи Для множества <tex> A \subseteq X </tex> выполнено <tex> span(???A)\subseteq \langle A \rangle. </tex>
|proof=Покажем, что следующее определение замыкания равносильно тому, которое [[Оператор замыкания для матроидов | было дано]] ранее:
: <tex>\langle A \rangle = A \cup \mathcal {f} x \in X \setminus A \; |\; \exists H \subseteq A \setminus x, \; H \in I , \; |H| = r(A) :\ H \cup x \notin I \mathcal {g}</tex>
По сравнению со старым определением появилось два ограничения, нужно убедится в том, что они не существены. Сначала рассмотрим <tex> |H| = r(A). </tex>
: Пусть <tex> \exists H \subseteq A :\ H \in I ,\; H \cup x \notin I, </tex> но <tex> |H| < r(A). </tex> По [[Ранговая функция, полумодулярность | определению ранга]] <tex> \exists D \subseteq A ,\; D \in I :\ |D| = r(A). </tex> Поскольку <tex> |H| < |D| </tex>, можно применить 3-ю аксиому матроидов несколько раз и получить <tex> H' \subseteq A :\ H \subseteq H' ,\; H' \in I ,\; |H'| = r(A). </tex>
: <tex> H' \cup x \notin I </tex> также будет выполнено, поскольку в противном случае <tex> H \cup x \notin I </tex> будет неверно (в силу 2-ой аксиомы матроидов).
Второе ограничение {{---}} <tex> H x \subseteq A in X \setminus x </tex> вместо <tex> H \subseteq A </tex> {{---}} вытекает само собойможно наложить по той причине, поскольку в случае что элементы <tex> x \in H </tex> не могут одновременно выполнятся <tex> H \in I A </tex> и <tex> H \cup x \notin Iтак входят в замыкание благодаря левой части объединения. </tex>
В соответствии с этим определением, замыкание множества <tex> A </tex> {{---}} это, кроме всех элементов <tex> A </tex>, все такие <tex> x, </tex> что какое-то из максимальных по мощности независимых подмножеств <tex> A </tex> нельзя дополнить <tex> x </tex>-ом, оставив это множество независимым. Определение покрытия отличается только квантором {{---}} вместо "какое-то" нужно поставить "любое".
Учитывая, что <tex> S \subseteq A,\ S \in I,\ |S| = r(A) </tex> описывает непустое множество таких <tex> S </tex> (по определению ранга), будет верным следствие:
: <tex> \forall S \subseteq A,\ S \in I,\ |S| = r(A) :\ S \cup x \notin I \ \Rightarrow </tex>
: <tex> \exists H \subseteq A, \; H \in I , \; |H| = r(A) :\ H \cup x \notin I </tex>
Следовательно <tex> x \in span(A) \ \Rightarrow \ x \in \langle A \rangle. </tex>
}}
{{Теорема
|statement = Покрытие обладает следующими свойствами:
# <tex> A, B \in subseteq X;\ A \subseteq span(B) \ \Rightarrow \ span(A) \subseteq span(B) </tex># <tex> A \in subseteq X,\ p \in X \setminus A,\ q \in span(A \cup p) \setminus span(A) \Rightarrow p \in span(A \cup q) </tex>
|proof =
}}
{{Теорема
|statement = Замкнутые Закрытые множества обладают следующими свойствами:
# <tex> A, B \in \mathcal L \ \; \Rightarrow \ A \cap B \in \mathcal L </tex>
# Если <tex> F \in \mathcal L,\ p \in X \setminus A F </tex> и <tex> F' </tex> {{---}} наименьшее по включению закрытое множество, содержащее <tex> F \cup p, </tex> тогда не существует <tex> F'' \in \mathcal L :\ F \subseteq F'' \subseteq F'. </tex>
|proof =
}}
*''Асанов М. О., Баранский В. А., Расин В. В.'' {{---}} Дискретная математика: Графы, матроиды, алгоритмы. '''ISBN 978-5-8114-1068-2'''
* [http://dictionary.sensagent.com/Matroid/en-en/ sensagent.com {{---}} Matroid]
* [http://courses.engr.illinois.edu/cs598csc/sp2010/Lectures/Lecture14.pdf http://courses.engr.illinois.edu] {{---}} Lecture 14, course ''CS 598CSC: Combinatorial optimization''
[[Категория:Алгоритмы и структуры данных]]
[[Категория:Матроиды]]
