Почему поток от начала до некоторой точки равен от некоторой точки до конца? - PullRequest
0 голосов
/ 18 февраля 2019

На странице 3 слайда второй пункт утверждает, что | f |= сумма f (s, v), где s принадлежит V = сумма f (v, t), где v принадлежит V. (извините, я не знаю, как набрать это в уценке.)

Я не понимаю, почему выполняется уравнение.

1 Ответ

0 голосов
/ 18 февраля 2019

Из названия звучит так, будто вы прочитали уравнение неправильно.Вершины v в первой сумме - это вершины, смежные с s .Они не совпадают с вершинами v во второй сумме.Это те, которые примыкают к t .

Уравнение говорит о суммарном потоке из с (сумма потоков на ребрах от с ) равняется общему потоку в t .

Это должно быть истиной, поскольку общий поток в каждую другую вершину должен равняться общему потоку (это ограничение сохранения потока).Таким образом, если на ребре есть поток из s , то, если он идет к вершине, которая не является t , то он должен снова вытекать из этой вершины и т. Д., Покаоно достигает т .

Все потока из с должны в конечном итоге достичь т , потому что t - единственная вершина, которая может ее потреблять.

...