Материал из Викиконспекты
|
|
| (не показано 12 промежуточных версий 2 участников) |
| Строка 1: |
Строка 1: |
| − | {{Лемма
| + | #перенаправление [[Граф замен]] |
| − | |about=
| |
| − | о паросочетании в графе замен
| |
| − | |statement= Пусть <tex>M = </tex> < <tex> X,I </tex> > — матроид. Множества <tex>A, B \in I</tex>, причем <tex>|A| = |B|</tex>. Тогда двудольный граф <tex>G_M(A) = </tex>{ <tex>(x, y) | x \in A, y \notin A, A</tex> \ <tex>x \cup y \in I</tex>} содержит полное паросочетание на <tex>A \oplus B</tex>.
| |
| − | |proof= Индукция по <tex>|A \oplus B|</tex>. База индукции очевидна. Покажем, что справедлив и индукционный переход. Рассмотрим матроид <tex>M_1 = </tex> < <tex> X</tex>, { <tex>K | K \in I, |K| \leq |A|</tex> } >. Множества <tex>A, B \in I</tex>, а значит они являются базами для матроида <tex>M_1</tex>. Тогда по [[Теорема о базах|теореме о базах]] <tex>\forall x \in A </tex> \ <tex>B: \exists y \in B </tex> \ <tex>A : A</tex> \ <tex>x \cup y \in I</tex>, поэтому <tex>(x, y) \in G_M(A)</tex>. Множества <tex>A </tex> \ <tex> x </tex> и <tex>B</tex> \ <tex>y</tex> являются независимыми как подмножества независимых и их <tex>\oplus</tex> имеет меньшую мощность, чем <tex>|A \oplus B|</tex>. Тогда по предположению индукции на их <tex>\oplus</tex> есть полное паросочетание, которое вместе с (x, y) составляет полное паросочетание на <tex>A \oplus B</tex>, а значит индукционный переход справедлив.
| |
| − | }}
| |
Текущая версия на 14:13, 24 апреля 2016
