Cтраница 1
Метод расстановки пометок для сети с пропускными способностями узлов позволяет найти множество узлов, образующих минимальный разрез. Если этот минимальный разрез удалить из сети, то сеть будет разбита на две части. В силу минимальности разреза никакое его собственное подмножество не обладает этим свойством. [1]
Можно разработать метод расстановки пометок, аналогичный методу, приведенному в гл. Однако правило 3 требует, чтобы просматривались не только все узлы Nh, соседние с каждым узлом, но также и все соседние для каждого узла Nh. Это резко увеличивает объем вычислений. [2]
При описании метода расстановки пометок мы до сих пор не указывали, в каком порядке следует просматривать помеченные узлы. Будем теперь придерживаться правила первым помечен - первым просмотрен. [3]
Перейдем к рассмотрению такой модификации метода расстановки пометок, которая применима для любых неориентированных сетей с действительными пропускными способностями. [4]
При получении максимального потока с помощью метода расстановки пометок все пометки стираются после нахождения некоторого пути, увеличивающего поток. В модификации этого метода, предложенной Скоинсом [177] и Джонсоном [119], каждый узел получает 3 пометки. После нахождения некоторого пути, увеличивающего поток, стирается только одна ветвь некоторого дерева, содержащего найденный путь, увеличивающий поток. В работе Джонсона проводится также обсуждение свойств базисных решений в сетевых терминах. [5]
Используя любые оставшиеся в сети дуги, находим с помощью метода расстановки пометок произвольный путь, увеличивающий поток; посылаем по нему максимально возможный поток. [6]
Эта задача, конечно, может быть решена посредством нахождения максимального потока с помощью метода расстановки пометок. [7]
Эта цепь называется прямым путем из Nz в AV - Прямой и обратный пути могут быть найдены с помощью метода расстановки пометок. [8]
Если пропускные способности btj не являются все целыми числами, то алгоритм может не быть конечным и может даже сходиться не к максимальному потоку. Это показывает, что метод расстановки пометок не эквивалентен симплекс-методу для задач линейного программирования. Так как задача о потоке в сети является частным случаем задачи линейного программирования, а симплекс-метод работает при любых действительных числах, то должен существовать алгоритм решения потоковой задачи, в которой пропускные способности дуг являются любыми действительными числами. [9]
Матрица А обладает свойством абсолютной унимодулярности, и следовательно, базисное оптимальное решение всегда целочис-ленно. Это, вообще говоря, уже неверно в задачах о многопродуктовом потоке. Большинство многопродуктовых задач не может быть решено методом расстановки пометок или его вариациями. [10]
В функциональном анализе имеется понятие локального минимума. В теории сетевых потоков ищутся минимальные разрезы, отделяющие источник от стока. Метод расстановки пометок для нахождения максимального потока ( а следовательно, и минимального разреза) позволяет находить абсолютный минимум, не используя понятия локального минимума. В последующих параграфах этот факт будет изучаться более подробно. [11]
Как уже отмечалось в § 8.1, задача о максимальном потоке в сети может быть сформулирована как задача линейного программирования. Однако метод расстановки пометок не является частным случаем симплекс-метода. В симплекс-методе происходит движение от одной вершины многогранника к другой, пока не будет достигнута оптимальная. Как станет ясно в дальнейшем, в методе расстановки пометок дело обстоит не так. [12]