Изменения
Нет описания правки
|proof=
Конструктивно построим <tex>\forall M_1, M_2</tex> такие <tex>I \in I_1 \cap I_2</tex> и <tex>A \subseteq X</tex>, что <tex>|I| = r_1(A) + r_2(X \setminus A)</tex>. Этого будет достаточно для доказательства теоремы.
Обозначим <tex>S = \left\{x|I \cup \{x\} \in I_1\right\}</tex>, <tex>T = \left\{x|I \cup \{x\} \in 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>. По лемме 1 и [[Лемма о единственном паросочетании в подграфе замен, индуцированном кратчайшим путем|лемме о единственном паросочетании]] <tex>I \oplus p_1 \in 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 \oplus p_2 \in I_1</tex>. Отсюда следует, что <tex>I \oplus p \in I_1 \cap I_2</tex>, причём <tex>|I \oplus p| = |I| + 1</tex>.
Будем таким образом увеличивать <tex>I</tex>, пока существует путь <tex>p</tex>. Рассмотрим момент, когда такого пути не нашлось.Введём обозначение: <tex>A = \{u|u \rightsquigarrow T\}</tex>. Докажем, что <tex>r_1(A) = |I \cap A|</tex> от противного.Пусть <tex>r_1(A) > |I \cap A|</tex>. Обозначим <tex>(I \cap A) \cup \{u\}</tex> как <tex>A'</tex>. Заметим, что <tex>A' \in I_1</tex>.Возможны 2 случая:# <tex>\overline{A} \cap I = \varnothing</tex>, тогда <tex>u \in S</tex>, что приводит к противоречию.# Можно добавлять из <tex>I \setminus A'</tex> в <tex>A'</tex>, пока <tex>|I| > |A'|</tex> (по аксиоме замены в <tex>M_1</tex>). Теперь <tex>A' = I \setminus \{z\}</tex>. <tex>I \setminus \{z\} \cup \{u\} \in I_1</tex>, следовательно, ребро <tex>zu \in G_I</tex>, что приводит к противоречию.Следовательно, <tex>r_1(A) = |I \cap A|</tex>. Аналогично, <tex>r_2(\overline A) = |I \cap \overline A|</tex>. Отсюда <tex>r_1(A) + r_2(\overline A) = |I|</tex>, то есть при найденных <tex>I</tex> и <tex>A</tex> достигается равенство. Построен пример равенства, значит, теорема доказана.
}}
