Изменения
Нет описания правки
Допустим в <tex>B</tex> не существует ребра, соединяющего две различные компоненты связанности из <tex>G_A</tex>, значит любая компонента связанности из <tex>G_B</tex> целиком вершинно-входит в какую-либо компоненту из <tex>G_A</tex>. Рассмотрим любую компоненту связанности Q из <tex>G_A</tex>, у неё <tex>k</tex> вершин и <tex>k - 1</tex> рёбер. Теперь рассмотрим все компоненты связанности <tex>P_i</tex> из <tex>G_B</tex> вершинно-входящие в <tex>Q</tex>, пусть их <tex>m</tex> штук, тогда суммарное кол-во рёбер из равно <tex>k - m</tex> что не превосходит <tex>k - 1</tex> (кол-во рёбер в <tex>Q</tex>). Просуммируем неравенство по всем компонентам связанности из <tex>G_A</tex> и получим <tex>\mid A \mid > \mid B \mid</tex> что протеворечит условию. Значит предположение не верно и в <tex>B</tex> существует искомое ребро <tex>x</tex> из разных компонент связанности <tex>G_B</tex>.
}}
==Трансверсальный матроид==
{{Определение
|definition=
Пусть <tex>G = \langle X, Y, E \rangle</tex> - двудольный граф. Тогда <tex>M = \langle X, I = \mathcal{f} A \subset X \mid \exists парасочетание M: X \cap ends(M) = A \mathcal {g} \rangle </tex> называют '''трансверсальным матроидом.'''
}}
{{Лемма
|statement = Трансверсальный матроид является матроидом.
|proof =
Проверим выполнение аксиом независимости:
1) <tex>\varnothing \in I</tex>
Пустое парасочетание удовлетворяет условию.
2) <tex>A \subset B, B \in I \Rightarrow A \in I</tex>
Подмножество парасочетания также является парасочетанием. Удалим из исходного парасочетания <tex>M</tex> ребра, концами которых являются вершины из множества <tex>A \setminus B</tex>. Оставшееся множество ребер будет являться парасочетанием, которое обозначим за <tex>M'</tex>. И будет выполняться условие <tex> X \cap ends(M') = B </tex> , что значит, <tex> B \subset I </tex>.
3) <tex>\mid A \mid < \mid B \mid \Rightarrow \mathcal {9} x \in B \setminus A, A \cup \mathcal{f} x \mathcal {g} \in I</tex>
}}
