В теории графов минимальный разрез или мин-разрез графа — это разрез ( разбиение вершин графа на два непересекающихся подмножества), который минимален по некоторой метрике.
Вариации задачи минимального разреза рассматривают взвешенные графы, ориентированные графы, терминалы и разбиение вершин на более чем два множества.
Задача взвешенного минимального разреза, допускающая как положительные, так и отрицательные веса, может быть тривиально преобразована в задачу взвешенного максимального разреза, путем изменения знака во всех весах.
Задача минимального разреза в неориентированных взвешенных графах, ограниченных неотрицательными весами, может быть решена за полиномиальное время с помощью алгоритма Стоера-Вагнера . В особом случае, когда граф не взвешен, алгоритм Каргера обеспечивает эффективный рандомизированный метод поиска разреза. В этом случае минимальный разрез равен связности ребер графа.
Обобщением задачи минимального разреза без терминалов является минимальный k -разрез , в котором цель состоит в том, чтобы разбить граф на по крайней мере k связных компонентов, удалив как можно меньше ребер. Для фиксированного значения k эта задача может быть решена за полиномиальное время, хотя алгоритм непрактичен для больших k . [2]
Когда даны два конечных узла, их обычно называют источником и стоком . В сети потоков минимальный разрез разделяет вершины источника и стока и минимизирует общую сумму пропускных способностей ребер, которые направлены от стороны источника разреза к стороне стока разреза. Как показано в теореме о максимальном потоке и минимальном разрезе , вес этого разреза равен максимальному объему потока, который может быть отправлен от источника к стоку в данной сети.
В взвешенной ненаправленной сети можно вычислить разрез, который отделяет определенную пару вершин друг от друга и имеет минимально возможный вес. Система разрезов, которая решает эту задачу для каждой возможной пары вершин, может быть собрана в структуру, известную как дерево Гомори–Ху графа.
Обобщением задачи минимального разреза с терминалами является k -терминальный разрез, или многотерминальный разрез. В плоском графе эта задача может быть решена за полиномиальное время. Однако в общем случае эта задача является NP-трудной , даже для . [3]
Задачи разбиения графа представляют собой семейство задач комбинаторной оптимизации, в которых граф должен быть разделен на две или более частей с дополнительными ограничениями, такими как балансировка размеров двух сторон разреза. Категоризация объектов на основе сегментации может рассматриваться как частный случай нормализованной спектральной кластеризации минимального разреза, применяемой к сегментации изображений . Ее также можно использовать как общий метод кластеризации , где узлы представляют собой выборки данных, предположительно взятые из метрического пространства , а веса ребер — их расстояния. Однако это часто непрактично из-за высокой вычислительной сложности для .
Из-за теоремы о максимальном потоке и минимальном разрезе , минимальное значение разреза для 2 узлов равно их максимальному потоку . В этом случае некоторые алгоритмы, используемые в задаче о максимальном потоке, также могут быть использованы для решения этого вопроса.
Граф с вершинами может иметь максимум различные минимальные разрезы. Эта граница узкая в том смысле, что (простой) цикл на вершинах имеет ровно минимальные разрезы.
