Введение
Разделение узлов графа на 2 непересекающихся подмножества. В теории графов, разрез — это разделение вершин графа на два непересекающихся подмножества. Любой разрез определяет множество ребер, образующих разрез, то есть множество ребер, имеющих один конец в каждом подмножестве разделения. Такие ребра называются пересекающими разрез. В связном графе каждое множество ребер, образующих разрез, определяет единственный разрез, и в некоторых случаях разрез идентифицируется с его множеством ребер, образующих разрез, а не с разделением вершин. В сети потоков, s–t-разрез — это разрез, требующий, чтобы источник и сток находились в разных подмножествах, а множество ребер, образующих разрез, состояло только из ребер, идущих от стороны источника к стороне стока. Пропускная способность s–t-разреза определяется как сумма пропускной способности каждого ребра в множестве ребер, образующих разрез.
In graph theory, a cut is a partition of the vertices of a graph into two disjoint subsets. Any cut determines a cut set, the set of edges that have one endpoint in each subset of the partition. These edges are said to cross the cut. In a connected graph, each cut set determines a unique cut, and in some cases cuts are identified with their cut sets rather than with their vertex partitions. In a flow network, an s–t cut is a cut that requires the source and the sink to be in different subsets, and its cut set only consists of edges going from the source's side to the sink's side. The capacity of an s–t cut is defined as the sum of the capacity of each edge in the cut set.
Определение
Разрез 1=C = (S,T) – это разбиение множества вершин V графа 1=G = (V,E) на два подмножества S и T.
Разрезное множество разреза 1=C = (S,T) – это множество ребер, имеющих одну конечную вершину в S и другую – в T.
Если s и t – заданные вершины графа G, то s–t-разрез – это разрез, в котором вершина s принадлежит множеству S, а вершина t – множеству T.
The cut set of a cut 1=C = (S,T) is the set of edges that have one endpoint in S and the other endpoint in T.
If s and t are specified vertices of the graph G, then an s–t cut is a cut in which s belongs to the set S and t belongs to the set T.
В невзвешенном неориентированном графе размер или вес разреза – это количество ребер, пересекающих разрез. В взвешенном графе значение или вес определяется суммой весов ребер, пересекающих разрез. Связка – это разрезное множество, не имеющее других разрезных множеств в качестве собственных подмножеств.
Минимальный отрез
Разрез считается минимальным, если его размер или вес не превышает размер или вес любого другого разреза. Иллюстрация справа демонстрирует минимальный разрез: его размер равен 2, и разреза размера 1 не существует, поскольку граф не имеет мостов. Теорема о максимальном потоке и минимальном разрезе доказывает, что максимальный сетевой поток равен сумме весов ребер любого минимального разреза, разделяющего источник и сток. Для решения задачи о минимальном разрезе существуют полиномиальные алгоритмы, в частности, алгоритм Эдмондса — Карпа.
Максимальный отрез
Разрез считается максимальным, если его размер не меньше размера любого другого разреза. Иллюстрация справа показывает максимальный разрез: размер разреза равен 5, и нет разреза размера 6 или |E| (число ребер), поскольку граф не является двудольным (содержит нечетный цикл). В общем случае, нахождение максимального разреза является вычислительно сложной задачей. Задача о максимальном разрезе входит в список из 21 NP-полной задачи Карпа. Задача о максимальном разрезе также является APX-трудной, что означает, что для неё не существует схемы полиномиального времени для приближенного решения, если P = NP. Однако её можно приближенно решить с постоянной точностью, используя полудефинитное программирование. Следует отметить, что задачи о минимальном и максимальном разрезах не являются двойственными в смысле линейного программирования, хотя переход от одной задачи к другой осуществляется заменой min на max в целевой функции. Задача о максимальном потоке является двойственной задачей к задаче о минимальном разрезе.
Наименьший разрез
Задача о разрезе с минимальной плотностью заключается в разбиении вершин на две части таким образом, чтобы минимизировать отношение числа ребер, пересекающих разрез, к числу вершин в меньшей из полученных частей. Эта целевая функция благоприятствует решениям, которые одновременно разрежены (мало ребер пересекает разрез) и сбалансированы (близки к бисекции). Известно, что задача является NP-трудной, а наилучший известный алгоритм аппроксимации – это аппроксимация, разработанная .
Отрежьте пространство
Семейство всех разрезов ненаправленного графа известно как пространство разрезов графа. Оно образует векторное пространство над конечным полем из двух элементов с арифметикой по модулю два, где операцией сложения векторов является симметричная разность двух разрезов, и является ортогональным дополнением к циклическому пространству. Если ребрам графа заданы положительные веса, то минимальный весовой базис пространства разрезов может быть описан деревом на том же множестве вершин, что и граф, называемым деревом Гомори — Хю. Каждому ребру этого дерева соответствует связность в исходном графе, а минимальный разрез между двумя узлами s и t является связностью с минимальным весом среди связностей, соответствующих пути от s к t в дереве.