В теории графов , разрез представляет собой раздел из вершин графа на два непересекающихся подмножества . Любой разрез определяет набор разрезов , набор ребер, у которых есть одна конечная точка в каждом подмножестве раздела. Говорят, что эти края пересекают разрез. В связном графе каждое множество разрезов определяет уникальный разрез, и в некоторых случаях разрезы идентифицируются с их наборами разрезов, а не с их разбиениями вершин.
В сети потока , s-т вырезать является разрезом , который требует источника и мойки быть в разных подмножествах, а его отключение набор состоит только из ребер , выходящих из стороны источника на сторону крана с . Емкость из S-т разреза определяется как сумма мощностей каждого ребра в вырез набора .
Определение
покрой это раздел графа на два подмножества S и Т . Вырез набор разреза это набор ребер, имеющих один конец в S , а другой конец в T . Если ы и т указаны вершины графа G , тогда ы - т разрез является разрезом , в котором ˙s принадлежит множеству S , и т принадлежит множеству Т .
В невзвешенном неориентированном графе размер или вес разреза - это количество ребер, пересекающих разрез. В взвешенном графе , то значение или вес определяются суммой весов ребер , пересекающих разрез.
Связь представляет собой вырез набор , который не имеет никакого другого разрез установить в качестве собственного подмножества.
Минимальный срез
Отрезок считается минимальным, если размер или вес отруба не больше, чем размер любого другого отруба. На рисунке справа показан минимальный разрез: размер этого разреза равен 2, и нет разреза размера 1, потому что на графике нет мостов .
Теорема о максимальном потоке и минимальном разрезе доказывает, что максимальный сетевой поток и сумма весовых коэффициентов любого минимального разреза, разделяющего источник и приемник, равны. Существуют методы полиномиального времени для решения задачи минимального разреза, в частности, алгоритм Эдмондса – Карпа . [1]
Максимальный разрез
Отрез считается максимальным, если размер отруба не меньше размера любого другого отруба. На иллюстрации справа показан максимальный разрез: размер разреза равен 5, и нет разреза размера 6, или | E | (количество ребер), потому что граф не двудольный (есть нечетный цикл ).
В общем, поиск максимального разреза требует больших вычислений. [2] Задача max-cut - одна из 21 NP-полных проблем Карпа . [3] Задача max-cut также является APX-сложной , что означает, что для нее не существует схемы полиномиального приближения, если только P = NP. [4] Однако его можно аппроксимировать с точностью до постоянного отношения приближения с помощью полуопределенного программирования . [5]
Обратите внимание, что min-cut и max-cut не являются двойными проблемами в смысле линейного программирования , даже если переходить от одной проблемы к другой можно, изменяя min на max в целевой функции . Задача о максимальном расходе двойственна проблеме минимального отсечения. [6]
Самый редкий срез
Самая редкая проблема разреза состоит в том, чтобы разделить вершины пополам, чтобы минимизировать отношение количества ребер в разрезе к количеству вершин в меньшей половине раздела. Эта целевая функция отдает предпочтение решениям, которые одновременно являются разреженными (несколько ребер пересекают разрез) и сбалансированными (близкими к пополам). Проблема, как известно, является NP-сложной, и самый известный алгоритм аппроксимации - этоприближение из-за Arora, Rao & Vazirani (2009) . [7]
Вырезать пространство
Семейство всех разрезов неориентированного графа известно как пространство разрезов графа. Он образует векторное пространство над двухэлементным конечным полем арифметического по модулю два, с симметричной разностью двух множеств разрезанных в качестве операции сложения векторов, и является ортогональным дополнением в пространстве цикла . [8] [9] Если ребрам графа присвоены положительные веса, базис минимального веса разреза может быть описан деревом на том же множестве вершин, что и граф, называемым деревом Гомори – Ху . [10] Каждое ребро этого дерева связано со связью в исходном графе, а минимальный разрез между двумя узлами s и t является связью с минимальным весом среди узлов , связанных с путем от s к t в дереве.
Смотрите также
Рекомендации
- ^ Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Стейн, Клиффорд (2001), Введение в алгоритмы (2-е изд.), MIT Press и McGraw-Hill, стр. 563 655 1043, ISBN 0-262-03293-7.
- ^ Гарей, Майкл Р .; Джонсон, Дэвид С. (1979), Компьютеры и несговорчивость: Руководство по теории NP- полноты, WH Freeman, A2.2: ND16, p. 210 , ISBN 0-7167-1045-5.
- ^ Карп, RM (1972), "Сводимость комбинаторных задач", Miller, RE; Thacher, JW (eds.), Complexity of Computer Computing , New York: Plenum Press, pp. 85–103..
- ^ Хот, С .; Киндлер, G .; Mossel, E .; О'Доннелл, Р. (2004), "Оптимальные результаты несовместимости для MAX-CUT и других CSP с двумя переменными?" (PDF) , Материалы 45-го симпозиума IEEE по основам информатики , стр. 146–154.
- ^ Goemans, MX ; Williamson, DP (1995), "Улучшенные алгоритмы аппроксимации для задач максимальной срезанных и выполнимости с использованием полуопределенного программирования", Журнал ACM , 42 (6): 1115-1145, DOI : 10,1145 / 227683,227684.
- ^ Вазирани, Виджай В. (2004), Алгоритмы аппроксимации , Springer, стр. 97–98, ISBN 3-540-65367-8.
- ^ Арора, Санджив ; Рао, Сатиш; Вазирани, Умеш (2009), "экспандер потоки, геометрические вложения и разбиение графов", J. ACM , ACM, 56 (2): 1-37, DOI : 10,1145 / 1502793,1502794.
- ^ Гросс, Джонатан Л .; Йеллен, Джей (2005), «4.6 Графы и векторные пространства», Теория графов и ее приложения (2-е изд.), CRC Press, стр. 197–207, ISBN 9781584885054.
- ^ Дистель, Рейнхард (2012), "1.9 Некоторые линейные алгебры", Теория графов , Тексты для выпускников по математике, 173 , Springer, стр. 23–28..
- ^ Korte, BH ; Выген, Йенс (2008), «8.6 Деревья Гомори – Ху», Комбинаторная оптимизация: теория и алгоритмы , алгоритмы и комбинаторика, 21 , Springer, стр. 180–186, ISBN 978-3-540-71844-4.