Минимальный срез - Minimum cut

График и два его разреза. Пунктирная линия красного цвета представляет собой разрез с тремя пересекающимися краями. Пунктирная линия зеленого цвета представляет собой одно из минимальных разрезов этого графа, пересекающее только два ребра.

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

Варианты задачи минимального разреза рассматривают взвешенные графы, ориентированные графы, терминалы и разбивают вершины на более чем два множества.

Задачу взвешенного минимального разреза, допускающую как положительные, так и отрицательные веса, можно тривиально преобразовать в задачу взвешенного максимального разреза , перевернув знак во всех весах.

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

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

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

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

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

В взвешенной неориентированной сети можно вычислить разрез, который отделяет конкретную пару вершин друг от друга и имеет минимально возможный вес. Система разрезов, которая решает эту проблему для каждой возможной пары вершин, может быть собрана в структуру, известную как дерево Гомори – Ху графа.

Обобщением задачи минимального разреза с терминалами является разрез k -терминала или многополюсный разрез. Эта проблема NP-сложна даже для . ${\ displaystyle k = 3}$

Приложения

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

В соответствии с теоремой о максимальном расходе и минимальном отсечении минимальное значение отсечения 2 узлов равно их значению максимального расхода . В этом случае некоторые алгоритмы, используемые в задаче maxflow, также могут быть использованы для решения этого вопроса.

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

Граф с вершинами может иметь самое большее количество различных минимальных разрезов. Эта оценка точна в том смысле, что (простой) цикл на вершинах имеет ровно минимальные разрезы. ${\ displaystyle n}$${\ displaystyle {\ binom {n} {2}} = {\ frac {n (n-1)} {2}}}$${\ displaystyle n}$${\ Displaystyle {\ гидроразрыва {п (п-1)} {2}}}$

Смотрите также

• Максимальный разрез
• Разделитель вершин , аналогичная концепция минимальных разрезов для вершин вместо ребер

использованная литература

Указатель статей, связанных с тем же именем

Эта статья включает список связанных элементов с одинаковыми (или похожими именами).
Если внутренняя ссылка привела вас сюда неправильно, вы можете изменить ссылку, чтобы она указывала прямо на предполагаемую статью.