Модификация метода Форда-Фалкерсона

Я хочу найти среди всех минимальных разрезов в сети потоков G с целыми пропускными способностями тот, который содержит наименьшее количество ребер. Как мы можем изменить пропускную способность G, чтобы создать новую сеть потоков G', в которой любой минимальный разрез в G' является минимальным разрезом с наименьшим количеством ребер в G. Источник - Кормен


algorithm graph-algorithm ford-fulkerson
person Dhruv Singh    schedule 13.06.2017    source источник

Ответы (1)


arrow_upward
2
arrow_downward

Допустим, граф G имеет n вершин.

Определим пропускную способность дуги e' в G', которая соответствует дуге e в G, как c(e') = c(e) * n + 1.

Следовательно, значение разреза в G' ровно в n раз превышает значение разреза в G + количество ребер в разрезе.

Допустим, теперь у нас есть минимальное сокращение G' со значением n * x + a. Это означает, что значение разреза в G равно x. Если бы существовал разрез в G с меньшим значением y < x, этот разрез имел бы значение n * y + b <= n * (y+1) <= n * x < n * x + a, что противоречит тому факту, что разрез со значением n * x + a был минимальным в G'. Мы только что доказали, что каждый минимальный разрез в G' также является минимальным разрезом в G. Но тогда следует, что минимальный разрез в G' является минимальным разрезом в G и имеет минимальное количество ребер из всех минимальных разрезов в G.

person blacktemplar    schedule 13.06.2017