Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

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

В сети потока , 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-сложной, и самый известный алгоритм приближения - это приближение, разработанное Аророй, Рао и Вазирани (2009) . [7]

Вырезать пространство [ править ]

Семейство всех разрезов неориентированного графа известно как пространство разрезов графа. Он образует векторное пространство над двухэлементным конечным полем арифметического по модулю два, с симметричной разностью двух множеств разрезанных в качестве операции сложения векторов, и является ортогональным дополнением в пространстве цикла . [8] [9] Если ребрам графа заданы положительные веса, базис минимального веса разреза может быть описан деревом на том же множестве вершин, что и граф, называемым деревом Гомори – Ху . [10]Каждое ребро этого дерева связано со связью в исходном графе, а минимальный разрез между двумя узлами s и t является связью с минимальным весом среди узлов , связанных с путем от s к t в дереве.

См. Также [ править ]

  • Связность (теория графов)
  • Графические сокращения в компьютерном зрении
  • Сплит (теория графов)
  • Разделитель вершин
  • Мост (теория графов)

Ссылки [ править ]

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