Изменения
Нет описания правки
* '''База
: В случае, когда При <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 \mathcal{I}, A \leqslant k \} \rangle</tex>. Множества <tex>A, B \in \mathcal{I}</tex>, <tex>|A| = |B|</tex> и матроид <tex>M_1</tex> не содержит множеств больших, чем <tex>A</tex>, а значит они являются базами для матроида <tex>M_1</tex>. :По [[Теорема о базах|сильной теореме о базах]] :<tex>\forall x \in A \setminus B: \exists y \in B \setminus A : (A \setminus x) \cup y \in \mathcal{I}</tex> и <tex>(B \setminus y) \cup x \in \mathcal{I}</tex> из :Из этого следует, что множество множества <tex>A' = (A \setminus x) \cup y </tex> и <tex>B' = (B \cup x) \setminus 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
\in \mathcal{I}</tex>, следовательно по определению графа <tex>D_M(A) \Rightarrow (x, y) \in D_M(A)</tex>. Тогда <tex>N \cup {(x, y)}</tex> составляет полное паросочетание на <tex>|A \bigtriangleup B|</tex>, а значит индукционный . Индукционный переход справедливдоказан.
}}
