А. шень Издание шестое, дополненное Москва
 Скачать 1.62 Mb.
|
|
9.3.2. Как в этих обозначениях записать сеть и поток из нашего примера? Решение. Обозначим верхнюю и нижнюю вершины через 𝐶 и 𝐷 (мы используем буквы вместо номеров, но понятно, что имеется в виду). 𝑐 𝐴 𝐵 𝐶 𝐷 𝐴 0 0 6 4 𝐵 0 0 4 6 𝐶 6 4 0 1 𝐷 4 6 1 0 𝑓 𝐴 𝐵 𝐶 𝐷 𝐴 0 0 5 4 𝐵 0 0 − 4 −5 𝐶 − 5 4 0 1 𝐷 −4 5 − 1 0 Обратите внимание, что матрица 𝑓, как говорят, кососимметрич- на (симметричные относительно главной диагонали клетки содержат противоположные числа), а матрица 𝑐 симметрична. Кососимметрич- ность матрицы 𝑓 | это результат нашего соглашения, что поток из 𝑖 в 𝑗 в нашей бухгалтерии учитывается дважды, со знаком плюс в одной клетке и со знаком минус в симметричной. На всякий случай ещё раз подчеркнём, что нет двух отдельных потоков «из 𝑖 в 𝑗» и «из 𝑗 в 𝑖», которые можно менять независимо; есть только один поток, который лишь записывается в двух клетках с противоположными знаками. (По- добно тому, как переток электричества из одной страны в другую одна страна записывает как экспорт, а другая как импорт.) А матрица 𝑐 симметрична из-за того, что мы рассматриваем сим- метричные трубы | и это, в отличие от кососимметричности потока, не обязательно. Вполне можно было бы рассматривать одностороннюю трубу (см. ниже). 9.3.3. Какие условия накладываются на поток из 𝑖 в 𝑗, если 𝑐[𝑖, 𝑗] = 2 и 𝑐[𝑗, 𝑖] = −2? 9.3. Сети, потоки и разрезы 161 Решение. Условия дают 𝑓[𝑖, 𝑗] 6 2 и 𝑓[𝑗, 𝑖] = −𝑓[𝑖, 𝑗] 6 −2, то есть 𝑓[𝑖, 𝑗] > 2. Таким образом, в этой сети требуется 𝑓[𝑖, 𝑗] = 2, не больше и не меньше. (Можно представить себе трубу, в которой по каким-то технологическим причинам нельзя останавливать или даже уменьшать перекачку ниже максимального уровня.) 9.3.4. Как отразить в наших обозначениях одностороннюю трубу, по которой можно перекачивать из 𝑖 в 𝑗 не более 2 единиц, а обратно ничего перекачивать нельзя? Ответ. 𝑐[𝑖, 𝑗] = 2, 𝑐[𝑗, 𝑖] = 0. 9.3.5. Как записать в терминах 𝑐[𝑖, 𝑗] условие «поток из 𝑖 в 𝑗 должен быть не меньше 2 и не больше 3»? Ответ. 𝑐[𝑖, 𝑗] = 3, 𝑐[𝑗, 𝑖] = −2. 9.3.6. Что можно сказать о потоке в сети, если 𝑐[𝑖, 𝑗] = 2, 𝑐[𝑗, 𝑖] = −3? Ответ. Такого потока не существует. Если отрицательные значения 𝑐[𝑖, 𝑗] вас пугают, то можно догово- риться рассматривать только сети, где 𝑐[𝑖, 𝑗] > 0 при всех 𝑖, 𝑗. В такой сети всегда есть поток (нулевой | все требования выполнены). Так мы и считаем в дальнейшем, если обратное не оговорено явно. Заметь- те, что среди 𝑓[𝑖, 𝑗] отрицательные числа всё равно будут (если поток ненулевой) | в силу кососимметричности. В следующей задаче требуется перевести очевидный факт на мате- матический язык и доказать его. 9.3.7. Покажите, что для любого потока выполнено равенство ∑︁ 𝑖 𝑓[𝑠, 𝑖] = ∑︁ 𝑗 𝑓[𝑗, 𝑡]. Что означает это равенство на человеческом языке? Решение. Левая часть | это суммарный поток из истока (в принци- пе туда может что-то и втекать, тогда в этой сумме есть отрицатель- ные члены), а правая часть | суммарный поток в сток. Равенство, та- ким образом, можно назвать «законом сохранения материи»; оно верно, если в сети нет утечек и дополнительных источников (одно из наших условий). Общее значение левой и правой части называют суммарной величи- ной потока 𝑓. Как это (очевидное) утверждение доказать формально? Вот как: рассмотрим сумму ∑︀ 𝑛 𝑖,𝑗=1 𝑓[𝑖, 𝑗]. Эта сумма равна нулю, так как члены 162 9. Разные алгоритмы на графах 𝑓[𝑖, 𝑗] и 𝑓[𝑗, 𝑖] сокращаются, а все 𝑓[𝑖, 𝑖] равны нулю. С другой стороны, её можно переписать как 𝑛 ∑︁ 𝑖=1 𝑛 ∑︁ 𝑗=1 𝑓[𝑖, 𝑗]. По определению потока внутренняя сумма равна нулю, кроме случаев 𝑖 = 𝑠 и 𝑖 = 𝑡, так что от всей суммы (равной нулю, напомним) остаётся 0 = 𝑛 ∑︁ 𝑗=1 𝑓[𝑠, 𝑗] + 𝑛 ∑︁ 𝑗=1 𝑓[𝑡, 𝑗]. Поскольку 𝑓[𝑡, 𝑗] = −𝑓[𝑗, 𝑡], изменяем знаки во втором слагаемом и по- лучаем искомое равенство. Теперь мы должны перевести на тот же математический язык ут- верждение о разрезах. Будем называть разрезом разбиение всех чисел от 1 до 𝑛 (узлов сети) на два непересекающихся класса 𝑆 и 𝑇 , в котором исток 𝑠 попадает в 𝑆, а сток 𝑡 попадает в 𝑇 . Будем обозначать такой разрез (𝑆, 𝑇 ). Пусть, помимо этого, у нас есть поток 𝑓. Тогда можно посчитать поток через разрез, то есть сумму ∑︁ 𝑢∈𝑆,𝑣∈𝑇 𝑓[𝑢, 𝑣], которую мы будем обозначать через 𝑓(𝑆, 𝑇 ). Подсчёт потока через разрез | это именно то, что делает тамо- женная статистика с потоком товаров через границу. И если товары производятся в одной стране, а потребляются в другой (и только), то эта сумма равна производству в истоке и потреблению в стоке. Следу- ющая задача предлагает доказать это формально. 9.3.8. Пусть (𝑆, 𝑇 ) | произвольный разрез сети, а 𝑓 | поток в этой сети. Докажите, что равенство предыдущей задачи можно дополнить: ∑︁ 𝑖 𝑓[𝑠, 𝑖] = 𝑓(𝑆, 𝑇 ) = ∑︁ 𝑗 𝑓[𝑗, 𝑡]. Решение. Будем действовать по аналогии с предыдущей задачей: рассмотрим сумму ∑︁ 𝑖∈𝑆,𝑗∈{1...,𝑛} 𝑓[𝑖, 𝑗], 9.3. Сети, потоки и разрезы 163 но ограничим суммирование только парами (𝑖, 𝑗), для которых 𝑖 ∈ 𝑆. Теперь уже сокращения не получится: хотя рёбра, у которых оба конца в 𝑆, появляются с плюсом и с минусом и по-прежнему сокращаются, останутся рёбра, у которых 𝑖 ∈ 𝑆, а 𝑗 ∈ 𝑇 , им сократиться не с кем, обратного ребра в сумме нет. Так что от всей суммы останется 𝑓(𝑆, 𝑇 ). С другой стороны, если переписать сумму как ∑︁ 𝑖∈𝑆 𝑛 ∑︁ 𝑗=1 𝑓[𝑖, 𝑗], то все внутренние суммы равны нулю при 𝑖 ̸= 𝑠, так что останется как раз поток, выходящий из истока 𝑠. 9.3.9. Повторите рассуждение для потока, входящего в сток. Заметим, что при подсчёте потока через разрез в сумме могут быть слагаемые разных знаков. Даже если какой-то товар производится то- лько в одной стране, и потребляется только в другой, всё равно потоки через границу могут быть в обе стороны (представьте себе нефтепро- вод из трёх частей, который идёт зигзагом, сначала пересекая границу, потом обратно, и потом снова туда). Естественно, что при подсчёте по- тока слагаемые разного знака полностью или частично сокращаются. 9.3.10. Как изменится поток через разрех, если мы поменяем 𝑆 и 𝑇 (а также исток 𝑠 и сток 𝑡) местами, не меняя массива 𝑓? Ответ. Изменит знак. Зная пропускные способности рёбер через разрез, можно ограни- чить суммарный поток через него: 9.3.11. Пусть дана сеть с пропускными способностями 𝑐[𝑖, 𝑗] и не- который поток 𝑓[𝑖, 𝑗] в ней. Пусть, с другой стороны, в этой сети есть некоторый разрез (𝑆, 𝑇 ). Докажите, что суммарная величина потока не превосходит пропускной способности разреза, определяемой как ∑︁ 𝑢∈𝑆,𝑣∈𝑇 𝑐[𝑢, 𝑣]. Решение. Доказательство короче формулировки: мы знаем, что сум- марная величина потока равна потоку через разрез, а он (очевидно) не превосходит пропускной способности этого разреза. Заметим, что в сумме, определяющей пропускную способность раз- реза, все слагаемые неотрицательны (напомним, что мы ограничива- емся случаем неотрицательных чисел 𝑐[𝑖, 𝑗]) | для потоков это было не так. 164 9. Разные алгоритмы на графах 9.3.12. Иногда вместо потоков рассматривают предпотоки, в кото- рых разрешаются потери перекачиваемой жидкости (но она не может взяться из ниоткуда). Как изменится определение? Покажите, что не- смотря на такое пренебрежение экологией, количество жидкости, при- ходящей в сток, всё равно не превосходит пропускной способности лю- бого разреза. Фиксируем некоторую сеть, и будем рассматривать в ней разные потоки (напомним, что мы считаем 𝑐[𝑖, 𝑗] неотрицательными, так что нулевой поток всегда существует) и разные разрезы. У каждого потока есть суммарная величина, а у каждого разреза | пропускная способ- ность. Задача 9.3.11 утверждает, что все первые не превосходят всех вторых | по очевидным причинам. Оказывается | и это утверждение называют теоремой Форда { Фалкерсона, | что это неравенство обра- щается в равенство для некоторого потока (максимального потока) и некоторого разреза (минимального разреза). Другими словами, есть число, которое является одновременно суммарной величиной некоторо- го потока и пропускной способностью некоторого разреза. Это число ограничивает сверху любой поток (потому что любой поток ограни- чен сверху минимальным разрезом) и снизу любой разрез (потому что любой разрез ограничен снизу максимальным потоком). Так что дей- ствительно названия «максимальный» и «минимальный» для потоков и разрезов оправданы. Мы докажем теорему Форда { Фалкерсона, но не сразу. Начнём с более слабого утверждения. 9.3.13. Пусть имеется сеть 𝑐 и некоторый поток 𝑓 в ней. Тогда выполнено одно из двух: либо в сети 𝑐 существует поток большей ве- личины, либо в ней есть разрез, у которого пропускная способность равна величине потока 𝑓. (Как мы видели, эти случаи исключают друг друга: если поток ра- вен некоторому разрезу, то большего потока уже быть не может.) Это утверждение очевидно следует из теоремы Форда { Фалкерсона: сравнивая поток с максимальным (который существует по этой теоре- ме), мы либо можем его увеличить, либо замечаем, что он уже равен минимальному разрезу. Но обратное рассуждение так просто не про- ходит (см. обсуждение после решения задачи). Решение. Основная идея состоит в рассмотрении остаточной сети (residual network). Представим себе, что по трубе с пропускной способ- ностью 3 в каком-то направлении идёт поток величины 2. В этом случае при необходимости можно увеличить этот поток ещё на 1; как говорят, 9.3. Сети, потоки и разрезы 165 остаточная пропускная способность этой трубы (в том же направле- нии) равна 1. Более хитрый пример: пусть есть односторонняя труба пропускной способности 2, и она полностью использована. Тогда воз- никает «виртуальная» труба 1 в обратную сторону с той же пропускной способностью 2: если мы захотим добавить поток в обратном направле- нии, нужно просто уменьшить исходный поток на соответствующую величину. Формально говоря, мы рассматриваем остаточную сеть 𝑐 ′ , положив 𝑐 ′ [𝑖, 𝑗] = 𝑐[𝑖, 𝑗] − 𝑓[𝑖, 𝑗]. Заметим, что по определению потока все значения 𝑐 ′ [𝑖, 𝑗] неотрицательны (и нулевой поток в остаточной се- ти соответствует неизменённому потоку исходной). 9.3.14. Если в двусторонней трубе с пропускной способностью 3 сейчас поток 2 в одну сторону, то каковы пропускные способности остаточной сети в ту и другую сторону? Продолжим решение задачи 9.3.13 . Для данной сети 𝑐 и потока 𝑓 в ней рассмотрим остаточную сеть. Построим ориентированный граф, проведя рёбро из 𝑢 в 𝑣 в тех случаях, когда в остаточной сети ненуле- вая (положительная) пропускная способность 𝑐[𝑢, 𝑣]. Этот остаточный граф отражает возможности дополнительных поставок. (Заметьте, что в нём вполне могут быть одновременно рёбра из 𝑢 в 𝑣 и обратно.) Те- перь есть два случая: ∙ В остаточном графе есть путь из истока 𝑠 в сток 𝑡. Такой путь называют дополняющим путём (augmenting path), посколь- ку вдоль него можно пропустить дополнительный поток из 𝑠 в 𝑡. Почему? Посмотрим на положительные остаточные пропуск- ные способности вдоль этого пути. Возьмём наименьшую из них, пусть это какое-то 𝛿 > 0. Добавим к исходному потоку дополни- тельный поток величины 𝛿, то есть увеличим исходный поток по рёбрам дополняющего пути на 𝛿, а по другим рёбрам оставим как было. (Педантичный читатель или редактор справедливо ука- жет на неточность в последнем предложении: если в дополняющий путь входит ребро из 𝑢 в 𝑣, то мы увеличиваем 𝑓[𝑢, 𝑣] на 𝛿 и умень- шаем 𝑓[𝑣, 𝑢] на 𝛿 в соответствии с нашим соглашением о знаках.) Легко проверить, что это будет потоком (добавка 𝛿 как вошла, так и выйдет), и суммарная величина потока увеличится на 𝛿. ∙ В остаточном графе нет пути из 𝑠 в 𝑡. Другими словами, верши- на 𝑡 не входит в число вершин, доступных в этом графе из 𝑠. Тогда 1 В газотранспортной отрасли это называют «виртуальным реверсом» и много спорят о законности этого. 166 9. Разные алгоритмы на графах понятно, где «узкое место», в котором надо провести разрез: пусть 𝑆 | вершины, доступные из 𝑠 в остаточном графе (включая сам исток 𝑠), а 𝑇 | все остальные (включая сток 𝑡). Из 𝑆 в 𝑇 не ведёт рёбер в остаточном графе (из доступной вершины нельзя попасть в недоступную, иначе она была бы доступной). Значит, для рёбер из 𝑆 в 𝑇 их пропускная способность 𝑐[𝑢, 𝑣] использует- ся потоком 𝑓[𝑢, 𝑣] полностью, и потому пропускная способность разреза равна потоку 𝑓(𝑆, 𝑇 ) через разрез. Эти два случая и соответствуют двум вариантам из условия задачи. 9.3.15. В решении есть небольшая неточность: нужно было брать не просто путь в остаточном графе, а путь, не проходящий дважды по одному ребру (например, кратчайший). Почему это важно? Решение. Если путь дважды проходит по ребру, то поток по этому ребру придётся увеличивать на 2𝛿, а это может превзойти остаточную пропускную способность. 9.3.16. Докажите, что во втором из рассмотренных случаев (когда пропускная способность равна величине потока) поток по всем рёбрам пересекает разрез в одну и ту же сторону, то есть 𝑓[𝑢, 𝑣] > 0 для всех 𝑢 ∈ 𝑆, 𝑣 ∈ 𝑇 . Решение. Неравенство между потоком и пропускной способностью получается сложением неравенств 𝑓[𝑢, 𝑣] 6 𝑐[𝑢, 𝑣]; оно обращается в ра- венство, лишь если все складываемые неравенства обращаются в равен- ства, и в этом случае 𝑓[𝑢, 𝑣] = 𝑐[𝑢, 𝑣] > 0 по предположению. Теперь попробуем доказать теорему Форда { Фалкерсона, то есть построить поток, равный разрезу (точнее: поток, суммарная величина которого равна пропускной способности некоторого разреза). Будем рассуждать так. Начнём с произвольного потока (например, нулевого). Мы только что доказали, что либо его можно увеличить, либо он уже равен некоторому разрезу. Во втором случае всё хорошо. В первом уве- личим поток, и снова применим то же рассуждение. Либо поток можно ещё увеличить, либо есть равный ему разрез | если первое, увеличим ещё и так далее, пока это не станет невозможным. Когда это случится, мы получим максимальный поток, равный минимальному разрезу. 9.3.17. В чём ошибка в этом рассуждении? Решение. Ниоткуда не следует, что этот процесс увеличения когда- то остановится, так что слова «когда это случится» неоправданно опти- мистичны. 9.3. Сети, потоки и разрезы 167 И это не просто теоретическая возможность, такое реально быва- ет, если никак не ограничивать выбор дополняющего пути. Начальный пример Форда { Фалкерсона был довольно сложный, но потом были при- думаны более простые (Цвик в статье 1995 года построил пример с 6 вершинами и 8 рёбрами и показал, что ни один из параметров нельзя уменьшить, Theoretical Computer Science, 148(1), 165{170, 1995). Идею таких примеров понять не так сложно. Представим себе сеть, в кото- рой есть три ребра небольшой пропускной способности, а кроме этого много рёбер большой пропускной способности, которые связывают все остальные пары вершин. 𝑠 𝑡 Конечно, тогда эти рёбра малой пропускной способности не очень-то и нужны, но мы хотим показать лишь, что при некотором способе вы- бирать дополняющий путь процесс продолжается бесконечно. Так что мы имеем право выбирать дополняющий путь как хотим. А именно, рассмотрим путь, в котором два ребра из трёх проходятся в прямом направлении, а третье в обратном. Таких путей возьмём три (в зави- симости от того, какое ребро проходится в обратном направлении), на рисунке показан один из трёх. 𝑠 𝑡 Что происходит при дополнении потока по таким путям? Если до этого рёбра были недогружены на 𝑎, 𝑏, 𝑐, то после этого в двух из них 168 9. Разные алгоритмы на графах недогруз уменьшится, а в одном увеличится: (𝑎, 𝑏, 𝑐) (𝑎−𝛿, 𝑏−𝛿, 𝑐+𝛿) или (𝑎−𝛿, 𝑏+𝛿, 𝑐−𝛿) или (𝑎+𝛿, 𝑏−𝛿, 𝑐−𝛿) При этом 𝛿 выбирается максимально возможным, чтобы при дальней- шем увеличении недогруз уже стал бы отрицательным | то есть од- но из чисел станет равным нулю. Следующий шаг (указанного вида) определяется однозначно: надо уменьшать два положительных числа, увеличивая нулевое, до тех пор, пока наименьшее из двух не обратится в нуль, и так далее. Легко сообразить, что если после первого шага недогруз будет (0, 𝛼, 𝛽), где 𝛼 и 𝛽 несоизмеримы (их отношение ирра- ционально), то процесс будет продолжаться неограниченно. 9.3.18. Покажите, что если 𝛾 обратно золотому сечению, то есть является (положительным) решением уравнения 𝛾 + 𝛾 2 = 1, то начав с тройки (0, 1, 𝛾), мы получим тройки (𝛾, 𝛾 2 , 0), (𝛾 3 , 0, 𝛾 2 ) и так далее | так что процесс будет продолжаться бесконечно. В приведённом выше рассуждении пропущен один момент: почему остальные рёбра (большой пропускной способности, как мы сказали) никогда не насытятся? Но видно (особенно в последнем примере), что увеличение общего потока ограничено, так что если пропускные спо- собности остальных рёбер достаточно велики, то до их насыщения дело никогда не дойдёт. Построенный пример существенным образом использует иррацио- нальные числа. 9.3.19. Покажите, что в сети с целыми (или хотя бы рациональ- ными) пропускными способностями аналогичная ситуация невозмож- на: увеличение потока вдоль дополняющего пути, как его ни выбирать, рано или поздно даст поток, в котором дополняющего пути не будет. Из этого утверждения (и ранее доказанного) следует теорема Фор- да { Фалкерсона для частного случая графов с целыми пропускными способностями. Решение. Если все пропускные способности целые, и мы начинаем с нулевого потока, то дробные числа не могут возникнуть (и остаточ- ные пропускные способности, и минимум их вдоль дополняющего пути будут целыми, и при вычитании тоже будут только целые числа. Зна- чит, каждый раз поток увеличивается по крайней мере на 1, и рано или поздно это кончится (поток ограничен любым разрезом). Для ра- циональных чисел можно перейти к другой единице измерения потока, чтобы все числа стали целыми. 9.3. Сети, потоки и разрезы 169 В этом рассуждении число шагов может быть большим даже для маленького графа. Это видно на совсем простом примере. 𝑠 𝑡 𝑝 𝑞 𝑁 𝑁 𝑁 𝑁 1 9.3.20. Покажите, что на графе на рисунке (где 𝑁 | большое це- лое число) при неудачном выборе дополняющих путей число итераций будет не меньше 𝑁. Решение. Будем поочерёдно использовать 𝑠{𝑝{𝑞{𝑡 и 𝑠{𝑞{𝑝{𝑡 в каче- стве дополняющих путей, начав с нулевого потока. Тогда на первом ша- ге поток увеличится на 1, а на каждом следующем будет увеличиваться на 2. Максимальный поток (который вообще не использует ребро 𝑝{𝑞) равен 2𝑁, так что до него надо сделать как минимум 𝑁 итераций. (Видно, как неудачный выбор дополняющего пути приводит к долгой работе в тривиальном примере.) 9.3.21. Рассмотрим сеть с целыми пропускными способностями. До- кажите, что максимальный поток в ней всегда можно выбрать целочи- сленным (нецелые потоки могут давать тот же результат, но не могут давать большего). Решение. Описанный процесс увеличения даёт целые потоки | и когда он закончится, поток равен разрезу, а этого не может превзойти никакой поток, целый или нет. Как же найти максимальный поток и минимальный разрез для про- извольной сети? Самый простой алгоритм для этого, называемый ал- горитмом Эдмондса { Карпа в честь его изобретателей, следует опи- санной схеме с единственным добавлением: в качестве дополняющего пути всегда берётся кратчайший путь из 𝑠 в 𝑡 в остаточном графе. Мы уже знаем, как быстро искать кратчайший путь, так что это не проблема. Осталось только доказать, что при этом процесс сойдётся, и оценить число итераций. Начнём с первого. Вот простое (но невер- ное!) рассуждение: на каждом шаге одно из рёбер дополняющего пути используется полностью, и тем самым больше по нему ничего пропу- стить нельзя. Значит, количество рёбер в остаточном графе каждый раз уменьшается, и бесконечно так продолжаться не может. 170 9. Разные алгоритмы на графах 9.3.22. Что неверно в этом рассуждении? (Оно не может быть вер- ным, так как мы не используем, что дополняющий путь кратчайший.) Решение. Хотя одно из рёбер дополняющего пути действительно пропадает, но общее число рёбер может не уменьшиться или даже уве- личиться, поскольку возникают реверсные рёбра. (Мы видели на при- мерах, что одно и то же ребро может входить в дополняющий путь то в одну сторону, то в другую.) Но тем не менее что-то в таком роде (что остаточный граф посте- пенно «прореживается») сказать можно. 9.3.23. Выберем какую-то вершину 𝑢 графа и будем следить за рас- стоянием в остаточном графе от 𝑠 до 𝑢. Докажите, что в ходе алго- ритма это расстояние не может уменьшаться (а может оставаться не- изменным или увеличиваться). Аналогичное утверждение верно и для расстояния от 𝑢 до 𝑡 (симме- трия). Решение. Пусть мы сделали несколько шагов алгоритма, и имеется остаточная сеть (и соответствующий остаточный граф). Расклассифи- цируем все вершины по длине кратчайшего пути из 𝑠 в этом графе: в 𝑆 0 входит сама вершина 𝑠, в 𝑆 1 | вершины, куда из 𝑠 ведёт ребро, в 𝑆 2 | вершины на расстоянии 2, и так далее. (Эта классификация не зависит от выбора вершины 𝑢.) Если расстояние от 𝑠 до 𝑢 было равно какому-то 𝑖, то вершина 𝑢 попадёт в класс 𝑆 𝑖 Заметим, что кратчайший путь из 𝑠 в 𝑢 должен проходить по оче- реди через вершины в классах 𝑆 0 , 𝑆 1 , . . . , 𝑆 𝑖 : пропустить класс он не мо- жет, так как на каждом шаге расстояние меняется на 1, а оставаться в том же классе или идти назад нельзя, тогда путь не будет кратчай- шим. После увеличения потока добавятся обратные рёбра этого пути (если их не было) | и все эти рёбра будут идти из класса с большим номером в класс с меньшим номером. И потому их добавление не со- кратит путь: даже если вообще добавить все рёбра, ведущие из класса с большим номером в класс с меньшим номером, путь не сократится | |