308
правок
Изменения
м
Следовательно Поэтому <tex> x \in span(A) \ \Rightarrow \ x \in \langle A \rangle. </tex>
* [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'']
Нет описания правки
: <tex>\langle A \rangle = A \cup \mathcal {f} x \in X \setminus A \; |\; \exists H \subseteq A, \; 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> x \in X \setminus A </tex> можно наложить по той причине, что элементы <tex> x \in A </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>
}}
== Смотри также ==
* [[Оператор замыкания для матроидов]]
== Источники информации ==
*''Асанов М. О., Баранский В. А., Расин В. В.'' {{---}} Дискретная математика: Графы, матроиды, алгоритмы. '''ISBN 978-5-8114-1068-2'''
[[Категория:Алгоритмы и структуры данных]]
[[Категория:Матроиды]]
