137
правок
Изменения
м
→Matching Matroid
==Matching Matroid==
{{Определение
|definition=
Пусть <tex>G = \langle V, E \rangle</tex> — неориентированный граф. <tex>I = \mathcal{f} A \subset V \mid \exists</tex> паросочетание <tex>P</tex>, покрывающее <tex>A \mathcal {g}</tex>. Тогда <tex>M = \langle V, I \rangle </tex> называют '''(matching matroid)'''.
}}
{{Лемма
|statement = Matching матроид является матроидом.
|proof =
Проверим выполнение аксиом независимости:
1) <tex>\varnothing \in I</tex>
Пустое паросочетание удовлетворяет условию.
2) <tex>A \subset B, B \in I \Rightarrow A \in I</tex>
Удалим из исходного паросочетания <tex>P</tex> ребра, концами которых являются вершины из множества <tex>B \setminus A</tex>. Оставшееся множество ребер будет являться паросочетанием, покрывающим <tex>A</tex>. Значит <tex>A \in I</tex>.
3) <tex>A \in I, B \in I, \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>
}}
==См. также==
* [[Определение матроида]]
