137
правок
Изменения
→Matching Matroid
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>
Пусть паросочетание <tex>P_A</tex> покрывает множество <tex>A</tex>, <tex>P_B</tex> — множество <tex>B</tex>.
Все вершины, принадлежащие <tex>A \cap B</tex> покроем ребрами из паросочетания <tex>P_B</tex>.
Так как <tex>\left\vert A \right\vert < \left\vert B \right\vert \Rightarrow \exists x \in B \setminus A</tex>
Рассмотрим три возможных случая:
* <tex>\exists xy \in P_A, y \in A \Rightarrow P_A</tex> покрывает <tex>A \cup \mathcal{f} x \mathcal {g} \Rightarrow A \cup \mathcal{f} x \mathcal {g} \in I</tex>
* <tex>\exists xy: y \in B \setminus A \Rightarrow xy \notin P_A</tex>. Мы можем добавить в <tex>A</tex> вершину <tex>x</tex> (или <tex>y</tex>), а в <tex>P_A</tex> ребро <tex>xy</tex>. Тогда паросочетание <tex>P_A \cup xy</tex> покрывает <tex>A \cup \mathcal{f} x \mathcal {g} \Rightarrow A \cup \mathcal{f} x \mathcal{g} \in I</tex>
*Если первые два случая не выполнились, значит <tex>\forall x \in B \setminus A</tex> <tex>\exists y \notin A, \notin B: \exists xy \in P_B</tex>. Обозначим множество таких <tex>y</tex> за <tex>C, \left\vert C \right\vert = \left\vert B \setminus A \right\vert > \left\vert A \setminus B \right\vert</tex>. Таким образом в <tex>C</tex> найдется хотя бы одна вершина <tex>y</tex>, не покрытая паросочетанием <tex>P_A</tex>. Тогда паросочетание <tex>P_A \cup xy</tex> покрывает <tex>A \cup \mathcal{f} x \mathcal {g} \Rightarrow A \cup \mathcal{f} x \mathcal{g} \in I</tex>
}}
