394
правки
Изменения
→Пояснения к доказательству
Во множество H вошли вершины с номерами 1,3,4,5,7,8.
Ненасыщенная вершина из правой доли всегда найдется(в примере вершина с номером 8), т.к иначе получается что в Hr входят только насыщенные вершины, и Hl получается равным Hr + 1(соседи по паросочетанию и вершина, которую пытаемся добавить)
Цепь {4,7,3,8} является удлиняющей для текущего паросочетания.