Cтраница 1
Минимальный разрез, определенный в гл. Например, ясно, что ATS - минимальный разрез, разделяющий Ns и Nt, а разрез ( Z, Z) - локально минимальный разрез, но не минимальный. [1]
Минимальный разрез ( Хт - - Хт) - это разрез с наименьшим таким значением. [2]
Бели же минимальный разрез в GO содержит такие дуги, то соответствующие вершины в G насыщены полученным максимальным потоком. [3]
Тогда каждый минимальный разрез по ребрам есть кограница некоторой вершины. [4]
Каждая дуга минимального разреза оказывается насыщенной, поэтому для нее с / оо. Следовательно, ни одна дуга минимального разреза не может войти в отрицательный цикл. Следовательно, сеть можно разбить на две части и искать отрицательные циклы отдельно в каждой из них. [5]
Задача определения минимального разреза на бисвязных орграфах вызывает все возрастающий интерес [1-4] благодаря большому числу задач, сводимых к ней. Рассмотрим некоторые из них. [6]
Число М возможных минимальных разрезов может быть несколько уменьшено путем исключения разрезов, содержащих дуги бесконечных пропускных способностей. Помимо этого, число дуг в приведенной сети можно дополнительно уменьшить, основываясь на пересечении множеств дуг, входящих в разные разрезы. [7]
Предположим, что минимальный разрез А С V ( G) индуцирует полный граф. Если z e А, то, в силу минимальности А, вершина х имеет две смежные вершины у я уз, разделяемые разрезом А. Рассмотрим цикл С без хорд, проходящий через ребра ху и ху2 - ( Такой цикл существует, согласно теореме 12.1.6, хотя четность этого цикла здесь не по существу. E ( G), поскольку А индуцирует полный граф, и это противоречит тому факту, что у цикла С нет хорд. [8]
А, определяющее минимальный разрез. [9]
Формулируется задача определения минимального разреза на бисвязных орграфах. Лредлагается процедура, позволяющая получить верхнюю и нижнюю границы величины минимального разреза на пленарных бисвязных орграфах. [10]
Так как существует много минимальных разрезов, возникает естественный вопрос: какой из минимальных разрезов получается в конструктивном доказательстве теоремы о максимальном потоке и минимальном разрезе. [11]
Во-вторых, здесь получается минимальный разрез ( X, X), где X - это единственный узел Ns, a X - три узла Nit N2, Nt. Как уже отмечалось выше, алгоритм расстановки пометок всегда дает такой минимальный разрез ( X, X), что X - наименьшее среди упорядоченных по включению подмножеств узлов. [12]
Но если множество узлов минимального разреза лежит целиком на линии с углом наклона 45, то общий вес этого множества узлов не будет равен весу полосы ширины h с углом наклона 45 ( см. риа. [13]
Естественно выбрать тот из минимальных разрезов, на котором достигается минимум затрат на единицу уменьшения времени. [14]
Тогда двухпродуктовый аналог теоремы о минимальном разрезе и максимальном потоке формулируется следующим образом. [15]