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