Материал из Викиконспекты
|
|
| Строка 1: |
Строка 1: |
| − | {{Лемма
| + | #перенаправление [[Граф замен]] |
| − | |about=
| |
| − | о паросочетании в графе замен
| |
| − | |statement= Пусть <tex>M = \langle X,I \rangle </tex> — матроид. Множества <tex>A, B \in I</tex> {{---}} независимы, причем <tex>|A| = |B|</tex>. Тогда двудольный граф <tex>D_{M}(I)</tex> содержит полное паросочетание на <tex>A \bigtriangleup B</tex>.
| |
| − | |proof=
| |
| − | <tex>D_{M}(I)</tex> {{---}} это двудольный граф с долями <tex>I</tex> и <tex>S \setminus I</tex> с рёбрами между <tex>y \in I</tex> и <tex>x \in S \setminus I</tex> если <tex> (I \setminus y) \cup x \in \mathcal{I} </tex>
| |
| − | Индукция по <tex>|A \bigtriangleup B|</tex>.
| |
| − |
| |
| − | * База
| |
| − | *: В случае, когда <tex>|A \bigtriangleup B| = 0 </tex>, есть пустое паросочетание.
| |
| − | * Переход
| |
| − | *:
| |
| − | Пусть <tex>k = |A| = |B|</tex>.
| |
| − |
| |
| − | Рассмотрим <tex>|A \bigtriangleup B| \geq 1</tex>.
| |
| − |
| |
| − | Рассмотрим матроид <tex>M_1 = \langle X, \{ A | 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>(x, y) \in G_M(A)</tex>. Множества <tex>A' = A - x + y </tex> и <tex>B' = B + x - y</tex> являются независимыми как подмножества независимых и их <tex>|A' \bigtriangleup B'| \leq |A \bigtriangleup B|</tex> Тогда по предположению индукции на их <tex>| A' \bigtriangleup B'|</tex> есть полное паросочетание <tex>N</tex>. Тогда <tex>N \cup {(x, y)}</tex> составляет полное паросочетание на <tex>|A \bigtriangleup B|</tex>, а значит индукционный переход справедлив.
| |
| − | | |
| − | Утверждение доказано.
| |
| − | }}
| |
| − | | |
| − | [[Категория:Алгоритмы и структуры данных]]
| |
| − | [[Категория:Матроиды]]
| |
| − | [[Категория:Пересечение матроидов]]
| |
Текущая версия на 14:13, 24 апреля 2016
