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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «{{Лемма |about= о паросочетании в графе замен |statement= Пусть <tex>M = </tex> < <tex> X,I </tex> > — матроид…»)
 
(Перенаправление на Граф замен)
 
(не показано 16 промежуточных версий 2 участников)
Строка 1: Строка 1:
{{Лемма
+
#перенаправление [[Граф замен]]
|about=
 
о паросочетании в графе замен
 
|statement= Пусть <tex>M = </tex> &lt; <tex> X,I </tex> &gt; &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 \ x \cup y \in I</tex>} содержит полное паросочетание на <tex>A \oplus B</tex>.
 
|proof= Индукция по <tex>|A \oplus B|</tex>. База индукции очевидна.
 
}}
 

Текущая версия на 14:13, 24 апреля 2016

Перенаправление на: