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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Отмена правки 8944 участника 192.168.0.2 (обсуждение))
Строка 1: Строка 1:
 
{{Лемма
 
{{Лемма
 
|statement =
 
|statement =
Пусть <tex>G</tex> — граф замен, тогда в его подграфе, индуцированном кратчайшим путем <tex>s \rightsquigarrow t</tex>, существует единственное полное бракосочетание.
+
Пусть <tex>G</tex> — граф замен, тогда в его подграфе, индуцированном кратчайшим путем <tex>s \rightsquigarrow t</tex>, существует единственное полное паросочетание.
 
|proof =
 
|proof =
  
 
}}
 
}}

Версия 04:00, 27 июня 2011

Лемма:
Пусть [math]G[/math] — граф замен, тогда в его подграфе, индуцированном кратчайшим путем [math]s \rightsquigarrow t[/math], существует единственное полное паросочетание.