Я читаю алгоритм push-flow в разделе «Введение в алгоритмы» Кормена и т. Д.
Мне трудно понять лемму 26.20, которая упоминается ниже:
Пусть G = (V, E) — поточная сеть с источником s и стоком t, и пусть f — предпоток в G. Тогда для любой переполняющей вершины u существует простой путь из u в s в остаточной сети Gf .
Посмотреть контекст этой лимы можно по следующей ссылке.
http://integrator-crimea.com/ddu0164.html
Просим вашей помощи в понимании этого.
Спасибо за ваше время и помощь.
Прошло много времени с тех пор, как я смотрел на все эти вещи с максимальным потоком, но если я правильно об этом думаю, вот что говорит лемма 26.20.
Очевидно, существует путь из s -> u, потому что в u есть избыток. Важная часть леммы, о которой следует подумать, заключается в том, что она утверждает, что существует простой путь от u -> s, который является направлением, противоположным исходному потоку, вызывающему переполнение в u (поскольку поток начинается в s и движется к u). Поскольку в u есть переполнение, существует простой путь из s -> u с не менее чем 1 единицей потока на всем пути. Даже если c(a,b) = 1 и f(a,b) = 1, что делает c(a,b) = 0, где a и b — все пары вершин этого простого пути, тогда c(b,a) = c(b,a) - f(b,a) = 1 - (-1) = 2, поскольку f(a,b) = -f(b,a). Таким образом, вы можете протолкнуть 2 единицы обратно через это ребро, прежде чем достигнете емкости в этом направлении (1, чтобы противостоять уже протекающей 1, создающей поток через это ребро 0, и еще один, чтобы создать поток через это ребро 1).
Причина, по которой вы знаете, что это простой путь, заключается в том, что если бы не было простого пути из s -> u, то вообще не было бы потока через u. Это связано с тем, что, несмотря на то, что существуют непростые способы добраться до u из s, должен быть хотя бы один простой путь, иначе весь поток будет захвачен непростым путем, что означает, что ни один из них не будет проходить через u.
Представьте это. Нарисуйте потоковую диаграмму, в которой источник полностью циклически проходит через пару узлов. Можно ли попасть в u (выбрать узел) без создания простого остаточного пути обратно в s? Теперь попробуйте сделать такой, в котором поток максимален в нескольких ребрах, все они направлены в u. Теперь попробуйте найти простой путь обратно к s. Это может продемонстрировать, о чем говорит лемма 26.20. Некоторые из этих лемм довольно сложны для понимания, но как только вы хорошенько об этом подумаете, они обычно обретают смысл. Они просто проводят доказательство от противного, чтобы доказать это, что является лучшим способом формально доказать то, что они говорят. Кроме того, загляните на вики-страницу, там, как всегда, есть хорошая идея! http://en.wikipedia.org/wiki/Push-relabel_maximum_flow_algorithm
Надеюсь, что это имеет какой-то смысл, и я готов работать с вами, если это не просто дайте мне знать!
