Изменения
Нет описания правки
{{Определение
|definition=
Объединение матроидов <tex>M</tex> = <tex>\langle S,J \rangle</tex> = <tex>\cup _{k=1}^{n}</tex> <tex>M_i</tex>, где <tex>M_i</tex> = <tex>\langle S_iS,J_i \rangle</tex>
}}
Для любого <tex>s \in S \setminus I</tex> имеем <tex>I + x \in J_i \Leftrightarrow </tex> существует ориентированный путь из <tex>F</tex> в <tex>s</tex> по ребрам <tex>D</tex>.
|proof=
<tex>\Leftarrow</tex> Пусть существует путь из <tex>F</tex> в <tex>s</tex> и <tex>P</tex> - самый короткий такой путь. Запишем его вершины как {<tex>s_0, s_1, ... s_p</tex>}. <tex>s_0 \in F</tex>, так что не умаляя общности можно сказать, что <tex>s_0 \in F_1</tex>. Для каждого <tex>j = 1...k</tex> определим множество вершин <tex>S_j =</tex> {<tex>s_i, s_{i+1}:(s_i, s_{i+1}) \in D_{M_j}(I_j)</tex>}, где <tex>i</tex> пробегает от <tex>0</tex> до <tex>p - 1</tex>.
Положим, что <tex>I'_1 = (I_1 \oplus S_1) \cup \{s_0\}</tex>, для всех <tex>j > 1</tex> положим <tex>I'_j = (I_j \oplus S_j)</tex>. Ясно, что <tex>\cup _j I'_j = I + s</tex>. Для того, чтобы показать независимость <tex>I + s</tex> в объединении матроидов нужно показать, что <tex>I'_j \in J_j</tex> для всех <tex>j</tex>. Заметим, что так как мы выбирали путь <tex>P</tex> таким, что он будет наименьшим, для каждого <tex>j > 1</tex> существует уникальное паросочетание между элементами, которые мы добавляли и удаляли, чтобы сконструировать <tex>I'_j = I_j \oplus S_j</tex>. Так как паросочетание уникально, <tex>I'_j \in J_j</tex>. Аналогично <tex>s_0 \in F_1</tex>, значит <tex>I'_1 \in J_1</tex>. Следовательно увидим, что <tex>I + s</tex> независимо в объединении матроидов.
<tex>\Rightarrow</tex>
}}
