динамические потоки на графах

я попробовал google:dynamic cut definition

нашлось такое (там какие-то формулы есть): http://gpd.sip.ucm.es/fraguas/papers/FLOPS02b.pdf

да я уже сам таки по конспекту разобрался. А твоя ссылка кстати представляет интерес хотя бы потому, что там на Прологе иллюстрации есть. Я думал, что Пролог уже давно рипнулся.

Что ты понимаешь под динамическим случаем, и почему оптимальный разрез с постоянными весами должен отличаться от разреза с переменными весами? Обычна под dynamic cuts имеют в виду нахождение оптимального разреза, зная разрез похожего графа(например, мы знаем сегментацию прошлого кадра в видео).

Что ты понимаешь под динамическим случаем, и почему оптимальный разрез с постоянными весами должен отличаться от разреза с переменными весами?

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

веса не меняются кстати, а на ребрах заданы два параметра - время «проезда» и вместимость.

А разрез dynamic в данном случае потому, что в разные моменты времени в разрезе присутствуют разные ребра.

Я все не могу понять, зачем в разрезе присутствовать разным ребрам, и что меняется со временем? Я работал вот с этим:

http://research.microsoft.com/en-us/um/people/pkohli/papers/pami07.pdf http://research.microsoft.com/en-us/um/people/pkohli/papers/kt_bc2010.pdf

И здесь просто алгоритмы перерасчета разреза графа, когда структура немного меняется(веса ну или, суть то же, максимальный поток на ребро).

Можешь дать ссылку на свою тему? А то я начинаю чувствовать себя ущербным)

Я все не могу понять, зачем в разрезе присутствовать разным ребрам, и что меняется со временем?

дан граф, на у каждого ребра есть два параметра - пропускная способность и время, которое нужно «частице» потока, чтобы преодолеть данное ребро.

Закон «Кирхгофа» потока должен выполняться всегда для всех узлов (ну кроме старта и финиша). Кроме того, после времени T не должно остаться ни одной частицы на ребрах графа.

Я б еще dynamic cut сформулировал, но мне надо убегать.

О, наконец, понял, спасибо!) Да, коллизия понятий произошла, то что я скидывал, не по той совсем теме. Буду рад, если кинешь какую-нибудь ссылку на краткое описание теории(2 минуты в гугле дают результаты по динамическам катам, того что я скидывал — подстроенный под меня поиск, фиг ли).

Буду рад, если кинешь какую-нибудь ссылку на краткое описание теории(2 минуты в гугле дают результаты по динамическам катам, того что я скидывал — подстроенный под меня поиск, фиг ли).

я в гугле и за пол-часа не нашел. Поэтому пришлось осиливать то, что я нацарапал в конспекте. Оказалось совсем не так трудно.

в нете особо нет нифига. Более-менее вменяемо написано у собсно авторов теоремы Ford Fulkerson - Flows in Networks. Прыгай сразу в параграф Dynamic Flows.

Вся суть теоремы в том, что максимальный temporar repeated flow является так же максимальным динамическим потоком. А temporar repeated flow - это такой, что его можно пересылать через сеть бесконечно. То есть, если поток определяется функцией f(e)->R, то эта функция должна быть такой, что не надо ее менять, если мы хотим пересылать этот поток бесконечно долго.

так что осиль сначала что такое temporar repeated flow, а потом все будет уже яснее.