Cтраница 2
Теорема о максимальном потоке и минимальном разрезе позволяет проверять, максимален данный поток или нет, но только для достаточно простых сетей. Разумеется, на практике приходится иметь дело е большими и сложными сетями, и в общем случае трудно найти максимальный поток простым подбором. [16]
Модуль анализа узких мест ПРС-Д определяет минимальный разрез и входящие в него магистрали. Если есть возможность увеличить пропускную способность магистралей, составляющих минимальный разрез, за счет перераспределения узловых давлений, то пользователь может откорректировать узловые давления и повторить расчет начиная с модуля ПС. [17]
Пусть ( X, X) является минимальным разрезом, разделяющим некоторые узлы Nt. Величина максимального потока fab равна величине некоторого минимального разреза в исходной сети. [18]
Некоторые приложения теоремы о максимальном потоке и минимальном разрезе мы обсудим в разд. [19]
Теперь применим теорему о максимальном потоке и минимальном разрезе для получения быстрого доказательства минимаксной теоремы Кенига. [20]
Дать доказательства теоремы о максимальном потоке и минимальном разрезе и теоремы о целочисленном потоке, используя рассуждения такого же вида, как приведенные выше. [21]
Пусть ( Yi, Y) - некоторый минимальный разрез, не пересекающийся с ( Л, X), а ( У2, У о) - минимальны. [22]
На шаге 14 описанной процедуры получаем верхнюю оценку минимального разреза, а на шаге 16 последней итерации - нижнюю. Если верхняя оценка не представляет интереса, то шаги 9 - 14 можно опустить. Алгоритм дает точное значение минимального разреза, если на двойственном орграфе существует один источник и один сток. [23]
Находим максимальную величину потока и значение пропускной способности минимального разреза сети, соответствующей значению ту. Полученное значение т обозначаем через TV I и повторяем процедуру. [24]
В этой сети с ограниченными пропускными способностями узлов минимальным разрезом является некоторое множество узлов. Необходимо обратить внимание на следующие три обстоятельства. Во-первых, минимальный разрез в рассматриваемой приближающей сети представляет собой некоторое множество узлов. Во-вторых, исходная прямоугольная область разбивается на элементарные квадраты. Объединение элементарных квадратов, соответствующих узлам минимального разреза, является подобластью. [25]
Величина максимального потока в орграфе G равна пропускной способности минимального разреза. [26]
Ху [9] получил теоретический результат, аналогичный теореме о минимальном разрезе - максимальном потоке, и дал вычислительную процедуру для решения поставленной задачи. [27]
Форд и Фалкерсон доказали теорему о максимальном потоке и минимальном разрезе [55]: для любой сети максимальная величина потока из вершины v в вершину v равна минимальной пропускной способности разрезов, отделяющих if от v; разрез с минимальной пропускной способностью носит название минимального разреза. [28]
Менгера для орграфов влечет теорему о максимальном потоке и минимальном разрезе. [29]
Здесь дано конструктивное доказательство теоремы о максимальном потоке и минимальном разрезе, и используемый метод непосредственно приводит к алгоритму расстановки пометок, излагаемому ниже. [30]