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

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

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

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

Без терминальных узлов

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

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

С терминальными узлами

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

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

Обобщением проблемы минимального разреза с терминалами является $k$ -терминальный разрез или многотерминальный разрез. В плоском графе эту задачу можно решить за полиномиальное время. Однако в целом эта задача NP-трудна даже для $k=3$ . ^[3]

Приложения

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

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

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

График с $n$ вершины могут иметь максимум ${\binom {n}{2}}={\frac {n(n-1)}{2}}$ четкие минимальные сокращения.Эта оценка точна в том смысле, что (простой) цикл на $n$ вершин имеет ровно ${\frac {n(n-1)}{2}}$ минимальные сокращения.

См. также

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

Ссылки

^ «4 алгоритма минимального сокращения» . Архивировано из оригинала 5 августа 2016 г.
^ Гольдшмидт, Оливье; Хохбаум, Дорит С. (1994). «Полиномиальный алгоритм решения задачи k-разреза при фиксированном k» . Математика исследования операций . 19 : 24–37. дои : 10.1287/moor.19.1.24 .
^ Дальхаус, Э.; Джонсон, Д.С.; Пападимитриу, Швейцария; Сеймур, PD; Яннакакис, М. (1994). «Сложность многоконцевых разрезов» (PDF) . SIAM Journal по вычислительной технике . 23 (4): 864–894. дои : 10.1137/S0097539792225297 . S2CID 1123876 . Архивировано из оригинала (PDF) 2 декабря 2018 г.

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

[1] «4 алгоритма минимального сокращения» . Архивировано из оригинала 5 августа 2016 г.

[2] Гольдшмидт, Оливье; Хохбаум, Дорит С. (1994). «Полиномиальный алгоритм решения задачи k-разреза при фиксированном k» . Математика исследования операций . 19 : 24–37. дои : 10.1287/moor.19.1.24 .

[3] Дальхаус, Э.; Джонсон, Д.С.; Пападимитриу, Швейцария; Сеймур, PD; Яннакакис, М. (1994). «Сложность многоконцевых разрезов» (PDF) . SIAM Journal по вычислительной технике . 23 (4): 864–894. дои : 10.1137/S0097539792225297 . S2CID 1123876 . Архивировано из оригинала (PDF) 2 декабря 2018 г.

[1]

[2]

[3]