Материал из Викиконспекты
| Лемма (о паросочетании в графе замен): |
Пусть [math]M = \langle X,I \rangle [/math] — матроид. Множества [math]A, B \in I[/math], причем [math]|A| = |B|[/math]. Тогда двудольный граф [math]G_M(A) = \{ (x, y) | x \in A, y \notin A, A \setminus x \cup y \in I \}[/math] содержит полное паросочетание на [math]A \bigtriangleup B[/math]. |
| Доказательство: |
| [math]\triangleright[/math] |
|
Индукция по [math]|A \bigtriangleup B|[/math].
- База
- В случае, когда [math]A \bigtriangleup B = \emptyset [/math], есть пустое паросочетание.
- Переход
- Рассмотрим матроид [math]M_1 = \langle X, \{ K | K \in I, |K| \leq |A| \} \rangle[/math]. Множества [math]A, B \in I[/math] и [math]|A| = |B|[/math], а значит они являются базами для матроида [math]M_1[/math]. Тогда по теореме о базах [math]\forall x \in A \setminus B: \exists y \in B \setminus A : A \setminus x \cup y \in I[/math], поэтому [math](x, y) \in G_M(A)[/math]. Множества [math]A \setminus x [/math] и [math]B \setminus y[/math] являются независимыми как подмножества независимых и их [math]\bigtriangleup[/math] имеет меньшую мощность, чем [math]|A \bigtriangleup B|[/math]. Тогда по предположению индукции на их [math]\bigtriangleup[/math] есть полное паросочетание, которое вместе с [math](x, y)[/math] составляет полное паросочетание на [math]A \bigtriangleup B[/math], а значит индукционный переход справедлив.
Утверждение доказано. |
| [math]\triangleleft[/math] |
