Пропускные способности - дуга
Cтраница 3
 |
Граф из примера. [31] |
Рассмотрим граф, изображенный на рис. 11.1, и возьмем в качестве источника вершину хг, а в качестве стока - вершину хд. Пропускные способности дуг указаны на рисунке. [32]
На рис. 11.5 показано, как множество источников и стоков может быть сведено к единственному источнику и единственному стоку. Пропускные способности дуг, ведущих от s к источникам, могут быть выбраны равными бесконечности или в случае, когда производительность источника Sh ограничена, пропускная способность соответствующей дуги ( s, sfe) может быть выбрана равной этой границе. [33]
 |
Граф из примера. [34] |
Рассмотрим граф, изображенный на рис. 11.1, и возьмем в качестве источника вершину х, а в качестве стока - вершину хд. Пропускные способности дуг указаны на рисунке. [35]
На рис. 11.5 показано, как множество источников и стоков может быть сведено к единственному источнику и единственному стоку. Пропускные способности дуг, ведущих от в к источникам, могут быть выбраны равными бесконечности или в случае, когда производительность источника ь ограничена, пропускная способность соответствующей дуги ( 5, 5Й) может быть выбрана равной этой границе. [36]
На рис. 4.6 показано, что шаг 2 уже пройден. Все нижние пропускные способности дуг положены равными нулю. [37]
Пусть известно, что суммарные затраты на преобразование сети не должны превышать заданной величины с. Как следует увеличить пропускные способности дуг, чтобы в преобразованной сети получить как можно большую величину потока. [38]
В полученном решении выделяются риски, превысившие допустимые. Далее снимаются ограничения на пропускные способности дуг: их считают ограниченными только снизу и притом нулем. [39]
Заметим, что если пропускные способности симметричных дуг равны между собой, то эти дуги могут быть заменены ребрами. В силу сказанного постановка задачи справедлива для смешанных и неориентированных графов. [40]
Вводится еще дуга ( п - - 1 0), соединяющая сток и источник, с пропускными способностями с 1 0 и / 7i i. В таким образом дополненном графе G все нижние пропускные способности дуг становятся равными нулю, и в нем уже в качестве начального потока можно брать нулевой. [41]
Если вычисления начались с целочисленного потока, то все последующие потоки ( в частности, максимальный), получаемые при работе рассмотренного алгоритма, будут целочисленными. Этот простой, но важный факт известен под названием теоремы о целочисленности: если пропускные способности дуг btj целочисленны, то существует максимальный поток, который целочислен. [42]
В § 8.2 было показано, что всегда существует целочисленное оптимальное решение задачи о максимальном потоке, если пропускные способности дуг целочисленны. [43]
Если такого потока не существует, то, очевидно, задача не имеет решения. Если же, как в нашем случае, хотя бы один такой поток существует, то на следующем шаге мы уменьшаем пропускные способности дуг на величины flll и повторяем весь процесс уже только для второго продукта. [44]
Прежде чем раскрыть суть третьего вопроса, заметим, что нельзя говорить о состоянии системы на таком интервале, на котором решение задачи не существует. Поэтому будем говорить о состоянии, имеющемся при решении на этом интервале такой задачи, у которой ослаблены ограничения на риски срыва узлов или на пропускные способности дуг. [45]
Страницы: 1 2 3 4