25
правок
Изменения
→Паросочетание в двудольном графе
|definition= '''Чередующаяся цепь''' — путь в двудольном графе, для любых двух соседних ребер которого верно, что одно из них принадлежит паросочетанию <tex>M</tex>, а другое нет.}}
{{Определение
|definition= '''Дополняющая цепь(или увеличивающая цепь)''' — чередующаяся цепь, у которой оба конца свободны.}}{{Определение|definition= '''Уменьшающая цепь''' — чередующаяся цепь, у которой оба конца покрыты.}}{{Определение|definition= '''Сбалансированная цепь''' — чередующаяся цепь, у которой один конец свободен, а другой покрыт}}
== Теорема о максимальном паросочетании и дополняющих цепях ==
