Введение

Разделение графа путем удаления минимального количества ребер

В теории графов минимальный разрез (или мини-разрез) графа — это разрез (разделение вершин графа на два непересекающихся подмножества), который минимален по некоторой метрике. Вариации задачи о минимальном разрезе рассматривают взвешенные графы, ориентированные графы, терминалы и разделение вершин на более чем два множества. Взвешенную задачу о минимальном разрезе, допускающую как положительные, так и отрицательные веса, можно тривиально преобразовать в задачу о взвешенном максимальном разрезе, изменив знак всех весов. TOC

Без конечных узлов

Проблема минимального разреза в ненаправленных взвешенных графах с неотрицательными весами может быть решена за полиномиальное время алгоритмом Стоера — Вагнера. В частном случае, когда граф невзвешенный, алгоритм Каргера предоставляет эффективный рандомизированный метод для нахождения разреза. В этом случае минимальный разрез равен краевой связности графа. Обобщением задачи минимального разреза без выделенных вершин является задача о минимальном k-разрезе, в которой цель состоит в том, чтобы разделить граф на как минимум k связных компонент, удалив минимальное количество ребер. Для фиксированного значения k эта задача может быть решена за полиномиальное время, однако алгоритм неэффективен при больших значениях k.

С конечными узлами

Когда заданы два терминальных узла, их обычно называют источником и стоком. В сети потоков минимальный разрез отделяет вершины источника и стока и минимизирует общую сумму пропускных способностей рёбер, направленных от стороны источника разреза к стороне стока разреза. Как показано в теореме о максимальном потоке и минимальном разрезе, вес этого разреза равен максимальному объёму потока, который может быть отправлен от источника к стоку в данной сети. В взвешенной, неориентированной сети можно вычислить разрез, который отделяет заданную пару вершин друг от друга и имеет минимально возможный вес. Система разрезов, решающая эту задачу для каждой возможной пары вершин, может быть собрана в структуру, известную как дерево Гомори-Ху графа. Обобщением задачи о минимальном разрезе с терминалами является k-терминальный разрез или мультитерминальный разрез. Эта задача является NP-трудной, даже для .

Приложения

Проблемы разбиения графов — это семейство комбинаторных задач оптимизации, в которых граф необходимо разделить на две или более частей с дополнительными ограничениями, такими как балансировка размеров двух сторон разреза. Категоризация объектов на основе сегментации можно рассматривать как частный случай нормализованной спектральной кластеризации с минимальным разрезом, применяемой к сегментации изображений. Её также можно использовать как универсальный метод кластеризации, где узлы представляют собой образцы данных, предположительно взятые из метрического пространства, а веса ребер — их расстояния. Однако это часто непрактично из-за высокой вычислительной сложности. В силу теоремы о максимальном потоке и минимальном разрезе, минимальное значение разреза между двумя узлами равно их максимальному значению потока. В этом случае некоторые алгоритмы, используемые для решения задачи о максимальном потоке, также могут быть применены для решения данной задачи.

Количество минимальных разрезов

Граф с *n* вершинами может иметь не более *n* различных минимальных разрезов. Эта граница является точной, поскольку (простой) цикл на *n* вершинах имеет ровно *n* минимальных разрезов.