17
правок
Изменения
Нет описания правки
|proof=
* '''База *: В случае, когда <tex>|A \bigtriangleup B| = 0 </tex>, это тривиальный случай, имеем пустое паросочетание. * '''Переход*:Считаем, что <tex>|A \bigtriangleup B| = N</tex> — утверждение верно.*: Пусть <tex>k = |A| = |B|</tex>.*:Рассмотрим и <tex>|A \bigtriangleup B| \geqslant 1</tex>.
*:Рассмотрим матроид <tex>M_1 = \langle X, \{ A \mid A \in I, A \leq k \} \rangle</tex>. Множества <tex>A, B \in I</tex> и <tex>|A| = |B|</tex>, а значит они являются базами для матроида <tex>M_1</tex>. По [[Теорема о базах|сильной теореме о базах]] <tex>\forall x \in A \setminus B: \exists y \in B \setminus A : (A \setminus x) \cup y \in I</tex> и <tex>(B \setminus y) \cup x \in I</tex> из этого следует, что множество <tex>A' = A - x + y </tex> и <tex>B' = B + x - y</tex> являются независимыми, а также базами <tex>M_1</tex>. И их <tex>|A' \bigtriangleup B'| < |A \bigtriangleup B|</tex>. Значит мы умеем переходить от <tex>|A' \bigtriangleup B'| = N</tex> к <tex>|A \bigtriangleup B| = N+1</tex>. По предположению индукции у <tex> |A' \bigtriangleup B'|</tex> есть полное паросочетание.
*:По [[Теорема о базах|теореме о базах]] <tex>\forall x \in A \setminus B: \exists y \in B \setminus A : (A \setminus x) \cup y
