200
правок
Изменения
интервики
{{Задача
|definition=
Даны [[Определение матроида|матроиды ]] <tex>M_1 = \langle S, \mathcal{I}_1 \rangle</tex> и <tex>M_2 = \langle S, \mathcal{I}_2 \rangle</tex>. Необходимо найти максимальное по мощности [[Определение матроида#def_matroid|независимое множество ]] в объединении <tex>M_1</tex> и <tex>M_2</tex>.
}}
== Алгоритм ==
Определим [[Граф замен|граф замен]]: для каждого <tex>M_i</tex> построим [[Основные определения теории графов#defBiparateGraph|двудольный ориентированный граф ]] <tex>D_{M_i}(I_i)</tex>, где <tex>I_i \in \mathcal{I}_i</tex>, такой что в левой доле находятся вершины из <tex>I_i</tex>, а в правой — вершины из <tex>S \setminus I_i</tex>. Построим ориентированные ребра из <tex>y \in I_i</tex> в <tex>x \in S \setminus I_i</tex>, при условии, что <tex>(I_i \setminus y) \cup x \in \mathcal{I}_i</tex>.
Объединим все <tex>D_{M_i}(I_i)</tex> в один граф <tex>D</tex>, который будет суперпозицией ребер из этих графов. Пусть для каждого <tex>i:</tex> <tex>F_i</tex> - множество вершин из <tex>S_i \setminus I_i</tex>, которые могут быть добавлены в <tex>I_i</tex> таким образом, что <tex>I_i + x</tex> независимое множество в <tex>M_i</tex>. Или формально:
Предположим, что это не так. <tex>|I_i \cap T| = r_i(I_i\cap T) \le r_i(T)</tex>, это возможно только если <tex>|I_i \cap T| < r_i(T)</tex>. Значит существует такой <tex>x \in T \cap (S \setminus I_i)</tex>, для которого <tex>(I_i \cap T) + x \in J_i</tex>. Но <tex>x \notin F</tex> (по предположению вначале доказательства), значит <tex>I_i + x \notin J_i</tex>. Из этого следует, что <tex>I_i + x</tex> содержит единственный цикл. Значит существует <tex>y \in I_i - T</tex>, такой что <tex>I_i + x - y \in J_i</tex>. Получается, что <tex>(y, x)</tex> — ребро в <tex>D_{M_i}(I_i)</tex> и оно содержит этот <tex>y \in T</tex>, что противоречит тому как был выбран <tex>y \in I_i \setminus T</tex>. Следовательно для всех <tex>i</tex> нам известно : <tex>|I_i \cap T| = r_i(T)</tex>.
У нас есть <tex>s \in T</tex> и <tex>(I + s) \cap T = (\cup I_i + s)\cap T = \cup(I_i \cap T) + s</tex>. Из определния функции [[Определение матроида#def_rank_of_matroid|ранга ]] объединения матроидов имеем :
<tex>r_M(I + s) \le (|(I + s)\setminus T| + \sum\limits_{k=1}^{n}r_i(T))</tex>
