В теории графов , А минимальный разрез или мин-срез из графика является срез (а разбиение вершин графа на два непересекающихся подмножество) , что является минимальным в некоторой метрике.
Варианты задачи минимального разреза рассматривают взвешенные графы, ориентированные графы, терминалы и разбивают вершины на более чем два множества.
Задача взвешенного минимального разреза, допускающая как положительные, так и отрицательные веса, может быть тривиально преобразована в задачу взвешенного максимального разреза путем изменения знака во всех весах.
Без оконечных узлов
Задача минимального разреза в неориентированных взвешенных графах может быть решена за полиномиальное время с помощью алгоритма Стоера-Вагнера . В особом случае, когда граф не взвешен, алгоритм Каргера обеспечивает эффективный рандомизированный метод нахождения разреза. В этом случае минимальный разрез равен связности ребер графа.
Обобщением задачи о минимальном разрезе без терминалов является минимальный k- разрез , цель которого состоит в том, чтобы разбить граф не менее чем на k связных компонентов, удалив как можно меньше ребер. При фиксированном значении k эта проблема может быть решена за полиномиальное время, хотя алгоритм непрактичен для больших k . [2]
С конечными узлами
Когда даны два оконечных узла, их обычно называют источником и приемником . В направленной, взвешенной потоковой сети минимальный разрез разделяет вершины источника и приемника и сводит к минимуму общий вес на ребрах, которые направлены от исходной стороны разреза к входной стороне разреза. Как показано в теореме о максимальном потоке и минимальном отсечении , вес этого отсечения равен максимальному количеству потока, который может быть отправлен от источника к потребителю в данной сети.
В взвешенной неориентированной сети можно вычислить разрез, который отделяет конкретную пару вершин друг от друга и имеет минимально возможный вес. Система разрезов, которая решает эту проблему для каждой возможной пары вершин, может быть собрана в структуру, известную как дерево Гомори – Ху графа.
Обобщением задачи минимального разреза с терминалами является разрезание k -терминала или многополюсное разрезание. Эта проблема NP-сложна даже для. [3]
Приложения
Задачи разбиения графа - это семейство задач комбинаторной оптимизации, в которых граф должен быть разбит на две или более частей с дополнительными ограничениями, такими как уравновешивание размеров двух сторон разреза. Категоризацию объектов на основе сегментации можно рассматривать как частный случай нормализованной минимальной спектральной кластеризации, применяемой к сегментации изображения .
В соответствии с теоремой о максимальном расходе и минимальном отсечении минимальное значение отсечения 2 узлов равно их значению максимального расхода . В этом случае некоторые алгоритмы, используемые в задаче maxflow, также могут быть использованы для решения этого вопроса.
Количество минимальных разрезов
График с вершины могут иметь самое большее отчетливые минимальные разрезы. Эта оценка точна в том смысле, что (простой) цикл на вершин ровно минимальные разрезы.
Смотрите также
- Максимальный разрез
- Разделитель вершин , аналогичная концепция минимальных разрезов для вершин вместо ребер
Рекомендации
- ^ «4 алгоритма Min-Cut» .
- ^ «Полиномиальный алгоритм для задачи k-разреза при фиксированном k» . Цитировать журнал требует
|journal=
( помощь ) - ^ «Сложность многотерминальных сокращений» (PDF) . Архивировано из оригинального (PDF) 25 декабря 2018 года. Цитировать журнал требует
|journal=
( помощь )