137
правок
Изменения
м
→Трансверсальный матроид
{{Определение
|definition=
Пусть <tex>G = \langle X, Y, E \rangle</tex> — двудольный граф. Тогда <tex>M = \langle X, I = \mathcal{f} A \subset X \mid \exists </tex> паросочетание <tex> M: X \cap ends(M) = P</tex>, покрывающее <tex>A \mathcal {g} </tex>. Тогда <tex>M = \langle X, I \rangle </tex> называют '''трансверсальным матроидом (transversal matroid).'''
}}
2) <tex>A \subset B, B \in I \Rightarrow A \in I</tex>
Подмножество паросочетания также является паросочетанием. Удалим из исходного паросочетания <tex>MP</tex> ребра, концами которых являются вершины из множества <tex>B \setminus A</tex>. Оставшееся множество ребер будет являться паросочетанием, которое обозначим за покрывающим <tex>M'A</tex>. И будет выполняться условие <tex> X \cap ends(M') = A </tex> , что значит, Значит <tex> A \in I </tex>.
3) <tex>\left\vert A \right\vert < \left\vert B \right\vert \Rightarrow \mathcal {9} x \in B \setminus A, A \cup \mathcal{f} x \mathcal {g} \in I</tex>
