Экземпляр Ford Fulkerson нарушает собственность

Question

Каким-то образом я создал этот график, который, кажется, нарушает одно из свойств, заключающееся в том, что значение потока ограничено верхним пределом пропускной способности min cut.
Вот график:

Максимальный поток, который находит алгоритм, равен 7. (отправка 3 на святых, 3 на сбт и 1 на сб)
В то время как минимальное сокращение в графе является {s,b}, {a,c,t} с емкостью 5.
Я не уверен, где я иду не так в этом. Может кто-нибудь исправить это?

Answer 1

Значение среза - это сумма мощностей кромок, которые "обрезаются".

В случае с разрезанием графика в {s,b} а также {a,c,t}края s-a, b-t, (и вы можете рассчитывать a-b если хотите), что означает значение 8 (11 если считать a-b), а не 5.

Насколько я могу судить, минимальный разрез будет включать в себя края a-t, b-t, а также c-t, который имеет значение 7, что соответствует Ford-Fulkerson.