Алгоритмы: проблема максимального расхода и минимального разреза

Question

Пусть G - входной граф для задачи о максимальном расходе.Пусть A - минимальный срез st в графе.Предположим, мы добавляем 1 к емкости каждого ребра графа.Обязательно ли верно, что A все еще является минимальным разрезом?Если да, то докажите это, если не предоставите контрпример

[Примечание: я думаю, что ответ отрицательный, не обязательно, но я не могу придумать контрпример] Обратите внимание, что это домашнее задание, яищу подсказку или любую помощь, которую я могу получить:)

Answer 1

С примечанием user57368 легко построить простые контрпримеры.

например. V = {A, B, C, D}, E = {(A, B, 2.5), (B, D, 1), (C, D, 1)}. Минимальный срез {{B, D), (C, D)} с весом 2.

Если вы добавите вес 1 к каждому ребру, вы получите E2 = {(A, B, 3.5), (B, D, 2), (C, D, 2)}. Здесь минимальный разрез {(A, B)} с весом 3,5.