Лемма о паросочетании в графе замен — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 2: Строка 2:
 
|about=
 
|about=
 
о паросочетании в графе замен
 
о паросочетании в графе замен
|statement= Пусть <tex>M = \langle X,I \rangle </tex> &mdash;  матроид. Множества <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>.
+
|statement= Пусть <tex>M = \langle X,I \rangle </tex> &mdash;  матроид. Множества <tex>A, B \in I</tex>, причем <tex>|A| = |B|</tex>. Тогда двудольный граф <tex>G_M(A) = \{ (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 = \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 </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> есть полное паросочетание, которое вместе с <tex>(x, y)</tex> составляет полное паросочетание на <tex>A \oplus B</tex>, а значит индукционный переход справедлив.
 
|proof= Индукция по <tex>|A \oplus B|</tex>. База индукции очевидна. Покажем, что справедлив и индукционный переход. Рассмотрим матроид <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 </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> есть полное паросочетание, которое вместе с <tex>(x, y)</tex> составляет полное паросочетание на <tex>A \oplus B</tex>, а значит индукционный переход справедлив.
 
}}
 
}}

Версия 00:49, 18 мая 2011

Лемма (о паросочетании в графе замен):
Пусть [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[/math] \ [math]x \cup y \in I \}[/math] содержит полное паросочетание на [math]A \oplus B[/math].
Доказательство:
[math]\triangleright[/math]
Индукция по [math]|A \oplus B|[/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 [/math] \ [math]B: \exists y \in B [/math] \ [math]A : A[/math] \ [math]x \cup y \in I[/math], поэтому [math](x, y) \in G_M(A)[/math]. Множества [math]A [/math] \ [math] x [/math] и [math]B[/math] \ [math]y[/math] являются независимыми как подмножества независимых и их [math]\oplus[/math] имеет меньшую мощность, чем [math]|A \oplus B|[/math]. Тогда по предположению индукции на их [math]\oplus[/math] есть полное паросочетание, которое вместе с [math](x, y)[/math] составляет полное паросочетание на [math]A \oplus B[/math], а значит индукционный переход справедлив.
[math]\triangleleft[/math]