Нахождение максимального потока в транспортной сети

[Sverest]

$\begin{pmatrix} \infty & 1 & 2 & 4 & \infty & \infty & \infty & \infty & \infty & \\ \infty & \infty & \infty & \infty & 3 & \infty & \infty & 2 & \infty & \\ \infty & \infty & \infty & \infty & 3 & 1 & 2 & \infty & \infty & \\ \infty & \infty & \infty & \infty & \infty & \infty & \infty & \infty & 2 & \\ \infty & \infty & \infty & \infty & \infty & \infty & 3 & \infty & \infty & \\ \infty & \infty & \infty & \infty & \infty & \infty & 1 & \infty & 9 & \\ \infty & \infty & \infty & \infty & \infty & \infty & \infty & \infty & 2 & \\ \infty & \infty & \infty & \infty & \infty & \infty & \infty & \infty & 5 & \\ \infty & \infty & \infty & \infty & \infty & \infty & \infty & \infty & \infty & \\ \end{pmatrix}$

$1(\frac{0}{2})3(\frac{0}{2})7(\frac{0}{2})9\quad \min=2$

$1(\frac{0}{1})2(\frac{0}{2})8(\frac{0}{5})9\quad \min=1$

$1(\frac{0}{4})4(\frac{0}{2})9\quad \min=2$

максимальный поток $=2+1+2=5$

я правильно нашел максимальный поток?

[cyb12]

Ответ правильный, если вы искали поток из 1 в 9.
Только вот решение какое-то странное. Просто перебирать цепи нельзя. Надо доказать, что больше 5 поток быть не может, что для данной сети совсем очевидно.

(правда я не знаю, что значат эти дроби в скобочках...)

[Sverest]

cyb12 в сообщении #457973 писал(а):

Ответ правильный, если вы искали поток из 1 в 9.
Только вот решение какое-то странное. Просто перебирать цепи нельзя. Надо доказать, что больше 5 поток быть не может, что для данной сети совсем очевидно.

(правда я не знаю, что значат эти дроби в скобочках...)

Да из 1 в 9

А как это доказывается?

В знаменателе дроби пропускная способность, в числителе текущий поток

-- Вт июн 14, 2011 17:51:53 --

http://rain.ifmo.ru/cat/view.php/vis/graph-flow-match/ford-fulkerson-2008

я по этой ссылке учился определять, там как то по другому чем в учебнике

[Sverest]

И я его не просто перебирал, а применил метод Форда-Фалкерсона, только думаю надо поподробней записать, а то из моих записей это не столь ясно.

[cyb12]

Здесь можно проще. Ребра из 1 мы задействовали полностью, кроме ребра в 4. Но из него ведет единственное ребро сразу же в 9 веса 2, значит, по ребру 1-4 мы больше 2 не проведем.

Если вы применяли метод Форда-Фалкерсона с построением остаточных сетей и проч., то доказывать не надо.

[Sverest]

странно, про остаточные сети ничего не знаю, может на том сайте метод какой-то урезанный или там не объясняется это просто

-- Ср июн 15, 2011 10:10:56 --

рассчитывал так: на ребрах писал пропускную способность в знаменател и ноль в числителе, составлятл маршрут от начала до конца, потом самое наименьшее из пропускных способностей маршрута ставил вместо нуля на данном маршруте, и так делал пока числитель не стал равен или больше пропускной способности

[Sverest]

как найти здесь минимальный разрез, я знаю что он равен максимальному потоку, но надо, как я понимаю, найти дуги