Лемма о паросочетании в графе замен — различия между версиями
| Строка 2: | Строка 2: | ||
|about= | |about= | ||
о паросочетании в графе замен | о паросочетании в графе замен | ||
| − | |statement= Пусть <tex>M = \langle X,I \rangle </tex> — матроид. Множества <tex>A, B \in I</tex>, причем <tex>|A| = |B|</tex>. Тогда двудольный граф <tex>G_M(A) = \{ (x, y) | x \in A, y \notin A, A \setminus x \cup y \in I \}</tex> содержит полное паросочетание на <tex>A \ | + | |statement= Пусть <tex>M = \langle X,I \rangle </tex> — матроид. Множества <tex>A, B \in I</tex>, причем <tex>|A| = |B|</tex>. Тогда двудольный граф <tex>G_M(A) = \{ (x, y) | x \in A, y \notin A, A \setminus x \cup y \in I \}</tex> содержит полное паросочетание на <tex>A \bigtriangleup B</tex>. |
|proof= Индукция по <tex>|A \oplus B|</tex>.<br> 1)База индукции очевидна. В случае, когда <tex>A \oplus B = \emptyset </tex>, есть пустое паросочетание. <br> 2)Покажем, что справедлив и индукционный переход. Рассмотрим матроид <tex>M_1 = \langle X, \{ K | K \in I, |K| \leq |A| \} \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>(x, y) \in G_M(A)</tex>. Множества <tex>A \setminus x </tex> и <tex>B \setminus y</tex> являются независимыми как подмножества независимых и их <tex>\oplus</tex> имеет меньшую мощность, чем <tex>|A \oplus B|</tex>. Тогда по предположению индукции на их <tex>\oplus</tex> есть полное паросочетание, которое вместе с <tex>(x, y)</tex> составляет полное паросочетание на <tex>A \oplus B</tex>, а значит индукционный переход справедлив. | |proof= Индукция по <tex>|A \oplus B|</tex>.<br> 1)База индукции очевидна. В случае, когда <tex>A \oplus B = \emptyset </tex>, есть пустое паросочетание. <br> 2)Покажем, что справедлив и индукционный переход. Рассмотрим матроид <tex>M_1 = \langle X, \{ K | K \in I, |K| \leq |A| \} \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>(x, y) \in G_M(A)</tex>. Множества <tex>A \setminus x </tex> и <tex>B \setminus y</tex> являются независимыми как подмножества независимых и их <tex>\oplus</tex> имеет меньшую мощность, чем <tex>|A \oplus B|</tex>. Тогда по предположению индукции на их <tex>\oplus</tex> есть полное паросочетание, которое вместе с <tex>(x, y)</tex> составляет полное паросочетание на <tex>A \oplus B</tex>, а значит индукционный переход справедлив. | ||
}} | }} | ||
| Строка 8: | Строка 8: | ||
[[Категория:Алгоритмы и структуры данных]] | [[Категория:Алгоритмы и структуры данных]] | ||
[[Категория:Матроиды]] | [[Категория:Матроиды]] | ||
| + | [[Категория:Пересечение матроидов]] | ||
Версия 09:20, 4 апреля 2016
| Лемма (о паросочетании в графе замен): |
Пусть — матроид. Множества , причем . Тогда двудольный граф содержит полное паросочетание на . |
| Доказательство: |
|
Индукция по . 1)База индукции очевидна. В случае, когда , есть пустое паросочетание. 2)Покажем, что справедлив и индукционный переход. Рассмотрим матроид . Множества и , а значит они являются базами для матроида . Тогда по теореме о базах , поэтому . Множества и являются независимыми как подмножества независимых и их имеет меньшую мощность, чем . Тогда по предположению индукции на их есть полное паросочетание, которое вместе с составляет полное паросочетание на , а значит индукционный переход справедлив. |
