Cтраница 3
Отсюда следует, что ( X, X) - минимальный разрез, поток через который равен его пропускной способности. Таким образом, получен максимальный поток. [31]
Чтобы использовать эту идею более полно, изучим некоторые свойства минимальных разрезов в сети. Будем говорить, что два разреза ( X, X) и ( У, Y) пересекаются, если каждое из четырех множеств узлов Xf Y, X ] Y, X [) Y1X Y непусто. [32]
Во всякой сети величина любого максимального потока равна пропускной способности любого минимального разреза. [33]
Покажем, что q - максимальный поток, а А определяет минимальный разрез. [34]
Величина максимальг ного потока из источника в сток равна, величине минимального разреза. [35]
Величина каждого потока из s в t не превосходит пропускной способности минимального разреза, разделяющего s и t, причем существует поток, достигающий этого значения. [36]
Дерево разрезов, содержащее п узлов, изображает п - 1 минимальных разрезов исходной сети, которые не пересекаются друг с другом. На рис. 9.19 эти разрезы изображены пунктирными линиями. [37]
Хо), который, следовательно, должен тогда быть равным минимальному разрезу. [38]
Конструктивный метод, использованный при доказательстве теоремы о максимальном потоке и минимальном разрезе, позволяет сразу же получить алгоритм вычисления максимального потока из данной вершины в данную вершину I в графе с известными пропускными способностями. Такой алгоритм будет сейчас описан. [39]
Конструктивный метод, использованный при доказательстве теоремы о максимальном потоке и минимальном разрезе, позволяет сразу же получить алгоритм вычисления максимального потока из данной вершины s в данную вершину t в графе с известными пропускными способностями. Такой алгоритм будет сейчас описан. [40]
Стержни для отверстия должны всегда иметь хотя бы незначительные / клоны, минимальный разрез которых в каждом отдельном случае зависит, с одной стороны, от степени усадки литейного сплава, с другой - от диаметра стержня, толщины стенок окружающего его литейного металла и от зажима последнего в период удаления стержня. [41]
Заметим, что все дуги, связывающие вершины дерева Т, изображают минимальные разрезы, отделяющие некоторые пары полюсов сети N. [42]
В сети с пропускными способностями узлов справедлива теорема о максимальном потоке и минимальном разрезе, аналогичная соответствующей теореме из гл. Но, поскольку при этом резко возрастает число дуг 1), будем рассматривать непосредственно сеть с пропускными способностями узлов. [43]
Сущность алгоритма основана на теореме Форда - Фалкерсона о максимальном потоке и минимальном разрезе. [44]
Тогда требуемый результат немедленно вытекает из теоремы 2.1.4 о максимальном потоке и минимальном разрезе и теоремы 2.2.1 о целочисленности потока. [45]