170
правок
Изменения
м
Нет описания правки
Пусть множество <tex>J \in (\mathcal{I}_1 \cap \mathcal{I}_2)</tex>.
<br>Определим [[Граф замен для двух матроидов|граф замен]] <tex>D_{M_1, M_2}(J) = \langle S, A(J) \rangle</tex>, где
<tex>A(J) = \{(y, z) | \mid y \in J, z \in S\setminus J, J - y + z \in \mathcal{I}_1 \} </tex> <tex>\cup \{ (z', y') | \mid z' \in S \setminus J, y' \in J, J - y' + z' \in \mathcal{I}_2 \}</tex>.
Пусть <tex>X_1 = \{ z \in S \setminus J | \mid J + z \in \mathcal{I}_1 \}</tex>, <tex>X_2 = \{ z \in S \setminus J | \mid J + z \in \mathcal{I}_2 \}</tex>, <tex>P</tex> {{---}} кратчайший путь из <tex>X_1</tex> в <tex>X_2</tex> в графе <tex>D_{M_1, M_2}(J)</tex>. <tex>P</tex> может и не существовать.
{{Лемма
|statement =
'''while''' '''not''' isMaximal
построить [[Граф замен для двух матроидов|граф замен]] <tex>D_{M_1, M_2}(J)</tex>
<tex>X_1 \leftarrow \{ z \in S \setminus J | \mid J + z \in \mathcal{I}_1 \}</tex> <tex>X_2 \leftarrow \{ z \in S \setminus J | \mid J + z \in \mathcal{I}_2 \}</tex>
<tex>P</tex> <tex>\leftarrow</tex> кратчайший путь из <tex>X_1</tex> в <tex>X_2</tex>
'''if''' <tex>P \ne \emptyset</tex>
Конструктивно построим <tex>\forall M_1, M_2</tex> такие <tex>I \in \mathcal{I}_1 \cap \mathcal{I}_2</tex> и <tex>A \subseteq X</tex>, что <tex>|I| = r_1(A) + r_2(X \setminus A)</tex>.
Обозначим <tex>S = \left\{x|\mid I \cup \{x\} \in \mathcal{I}_1\right\}</tex>, <tex>T = \left\{x|\mid I \cup \{x\} \in \mathcal{I}_2\right\}</tex>. Если <tex>S \cap T \ne \varnothing</tex>, добавим их пересечение в <tex>I</tex>.
Построим [[Граф замен для двух матроидов|граф замен]] <tex>G_I</tex>. Добавим вершину <tex>z</tex>, не влияющую на независимость в первом матроиде {{---}} из неё будут вести рёбра во все вершины множества <tex>S</tex>. Пусть <tex>p</tex> {{---}} кратчайший путь из <tex>S</tex> в <tex>T</tex>, <tex>p_1</tex> {{---}} путь <tex>p</tex> с добавленным в начало ребром из <tex>z</tex>. По [[Лемма о единственном паросочетании в графе замен|лемме о единственном паросочетании]] и [[Лемма о единственном паросочетании в подграфе замен, индуцированном кратчайшим путем|лемме о единственном паросочетании, индуцированном кратчайшем путём]] <tex>I \bigtriangleup p_1 \in \mathcal{I}_2</tex>. Теперь добавим вершину <tex>u</tex>, не влияющую на независимость во втором матроиде {{---}} в неё будут вести рёбра из всех вершин множества <tex>T</tex>. Тогда <tex>p_2</tex> (путь <tex>p</tex> с добавленным ребром в <tex>u</tex>) — кратчайший путь из <tex>S</tex> в <tex>u</tex>. Аналогично, <tex>I \bigtriangleup p_2 \in \mathcal{I}_1</tex>. Отсюда следует, что <tex>I \bigtriangleup p \in \mathcal{I}_1 \cap \mathcal{I}_2</tex>, причём <tex>|I \bigtriangleup p| = |I| + 1</tex>.</div>
Будем таким образом увеличивать <tex>I</tex>, пока существует путь <tex>p</tex>. Рассмотрим момент, когда такого пути не нашлось.
Введём обозначение: <tex>A = \{u|\mid u \rightsquigarrow T\}</tex>.
Докажем, что <tex>r_1(A) = |I \cap A|</tex> от противного.
