22
правки
Изменения
м
Нет описания правки
Для решения этой задачи преобразуем каждый элемент множества <tex>X</tex> в матроиде <tex>M_1</tex> в <tex>(x, 1)</tex>, а каждый элемент множества <tex>X</tex> в матроиде <tex>M_2</tex> в <tex>(x, 2)</tex>. Мы получили два матроида <tex>M'_1 = \langle (X \times \{1\}), \mathcal{I}_1 \rangle </tex> и <tex> M'_2 = \langle (X \times \{2\}), \mathcal{I}_2 \rangle </tex>.
Определим функцию <tex>P_1</tex> : <tex> X \times Y \rightarrow X</tex> : , при этом <tex>P_1((x, y)) = x</tex>, а для множества <tex>B \in X \times Y</tex> выполняется <tex>P_1(B) = \{A \subset X \mid \forall x \in A </tex> <tex> \exists b \in B : P_1(b) = x\}</tex>.
Тогда функция <tex>P_1</tex> на носителях матроидов <tex>M'_1</tex> и <tex>M'_2</tex> будет являться естественным отображением <tex>(x, i) \rightarrow x</tex>, где <tex>i \in \{1, 2\}</tex>.
Множество <tex>U</tex> является независимым, если [[Ранговая функция, полумодулярность|ранговая функция]] <tex> r(U) = |U|</tex>.
Можно заметить, что в матроиде <tex>M</tex> выполняется <tex>r(U) = \max\limits_{A \mid A \in \mathcal{I}_{\oplus}, A \in \mathcal{I}_{P_1}, P_1(A) \subset U} |A|</tex>.
Таким образом, мы свели задачу о проверке множества на независимость в объединении к нахождению мощности максимального независимого множества в пересечении матроидов <tex>M_{\oplus}</tex> и <tex>M_{P_1}</tex>. С помощью [[Алгоритм построения базы в пересечении матроидов|алгоритма построения базы в пересечении матроидов]] найдем размер максимального подсета множества подмножества <tex>U' \mid P_1(U') = U</tex> в пересечении наборов независимых множеств матроидов.
==См. также==
==Источники информации ==
* Емеличев В. А., Мельников О. И., Сарванов В. И., Тышкевич Р. И. {{---}} Лекции по теории графов
* Chandra Chekuri {{---}} [https://courses.engr.illinois.edu/cs598csc/sp2010/Lectures/Lecture19.pdf '''Combinatorial Optimization''']* Michel X. Goemans Chandra Chekuri {{---}} Combinatorial Optimization]* [http://math.mit.edu/~goemans/18438F09/lec13.pdf '''Advanced Combinatorial Optimization''']* Wikipedia Michel X. Goemans {{---}} Advanced Combinatorial Optimization]* [https://en.wikipedia.org/wiki/Matroid '''Wikipedia {{---}} Matroid''']
[[Категория:Алгоритмы и структуры данных]]
[[Категория:Матроиды]]
[[Категория:Объединение матроидов]]
