WikiDer > Минимальный разрез

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

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

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

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

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

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

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

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

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

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

Обобщением задачи минимального разреза с терминалами является k-терминальный разрез или многотерминальный разрез. Эта проблема NP-жесткий, даже для .[3]

Приложения

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

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

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

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

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

Рекомендации

  1. ^ «4 алгоритма Min-Cut».
  2. ^ «Полиномиальный алгоритм для задачи k-разреза при фиксированном k». Цитировать журнал требует | журнал = (помощь)
  3. ^ «Сложность многотерминальных разрезов» (PDF). Цитировать журнал требует | журнал = (помощь)