Лемма о паросочетании в графе замен — различия между версиями
(Новая страница: «{{Лемма |about= о паросочетании в графе замен |statement= Пусть <tex>M = </tex> < <tex> X,I </tex> > — матроид…») |
(нет различий)
|
Версия 03:01, 17 мая 2011
Лемма (о паросочетании в графе замен): |
Пусть < > — матроид. Множества , причем . Тогда двудольный граф { } содержит полное паросочетание на . |
Доказательство: |
Индукция по | . База индукции очевидна.