stringtranslate.com

Cut (теория графов)

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

В потоковой сети разрез s – t — это разрез, который требует, чтобы источник и сток находились в разных подмножествах, а его набор разрезов состоит только из ребер, идущих от стороны источника к стороне стока. Пропускная способность разреза s–t определяется как сумма пропускных способностей каждого ребра в наборе разрезов .

Определение

Разрез C = ( S , T ) — это разбиение V графа G = ( V , E ) на два подмножества S и T . Множество разрезов C = ( S , T ) — это множество {( u , v ) ∈ E | u ∈ S , v ∈ T } ребер, которые имеют один конец в S , а другой конец в T. Если s и t — заданные вершины графа G , то разрез s–t — это разрез, в котором s принадлежит множеству S , а t принадлежит множеству T.

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

Облигация — это набор разрезов , который не имеет другого набора разрезов в качестве собственного подмножества.

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

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

Отрезок считается минимальным , если размер или вес отруба не превышает размера любого другого отруба. На иллюстрации справа показан минимальный разрез: размер этого разреза равен 2, а разреза размера 1 не существует, поскольку граф не содержит мостов .

Теорема о максимальном потоке и минимальном разрезе доказывает, что максимальный поток сети и сумма весов ребер любого минимального разреза, разделяющего источник и сток, равны. Существуют методы с полиномиальным временем для решения проблемы минимального разреза, в частности алгоритм Эдмондса-Карпа . [2]

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

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

Отрезок является максимальным , если его размер не меньше размера любого другого отреза. На рисунке справа показан максимальный разрез: размер разреза равен 5, а разреза размера 6 нет, или | Е | (количество ребер), поскольку граф не двудольный (есть нечетный цикл ).

В общем, найти максимальный разрез вычислительно сложно. [3] Задача о максимальном разрезе — одна из 21 NP-полной задачи Карпа . [4] Задача максимального разреза также является APX-трудной , а это означает, что для нее не существует схемы аппроксимации с полиномиальным временем, если только P = NP. [5] Однако его можно аппроксимировать с точностью до постоянного коэффициента аппроксимации , используя полуопределенное программирование . [6]

Обратите внимание, что min-cut и max-cut не являются двойными задачами в смысле линейного программирования , хотя можно перейти от одной проблемы к другой, меняя min на max в целевой функции . Проблема максимального потока является двойственной проблеме минимального сокращения. [7]

Самый редкий разрез

Самая разреженная проблема разреза состоит в том, чтобы разбить вершины на две части так, чтобы минимизировать отношение числа ребер в разрезе к числу вершин в меньшей половине разбиения. Эта целевая функция благоприятствует решениям, которые являются одновременно разреженными (несколько ребер пересекают разрез) и сбалансированными (близкими к разделению пополам). Известно, что проблема NP-трудна, и наиболее известным алгоритмом аппроксимации является аппроксимация, предложенная Аророй, Рао и Вазирани (2009). [8]

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

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

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

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

  1. ^ «Документация NetworkX 2.6.2» . networkx.algorithms.cuts.cut_size . Архивировано из оригинала 18 ноября 2021 г. Проверено 10 декабря 2021 г. Разрез — это разбиение узлов графа на два множества. Размер разреза представляет собой сумму весов ребер «между» двумя наборами узлов.
  2. ^ Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Стейн, Клиффорд (2001), Введение в алгоритмы (2-е изд.), MIT Press и McGraw-Hill, стр. 563 655 1043, ISBN 0-262-03293-7.
  3. ^ Гэри, Майкл Р .; Джонсон, Дэвид С. (1979), Компьютеры и трудноразрешимые проблемы: Руководство по теории NP-полноты , WH Freeman, A2.2: ND16, с. 210, ISBN 0-7167-1045-5.
  4. ^ Карп, Р.М. (1972), «Сводимость комбинаторных задач», в Миллер, Р.Э.; Тэчер, Дж.В. (ред.), Сложность компьютерных вычислений , Нью-Йорк: Plenum Press, стр. 85–103..
  5. ^ Хот, С .; Киндлер, Г.; Моссель, Э.; О'Доннелл, Р. (2004), «Оптимальные результаты неаппроксимируемости для MAX-CUT и других CSP с двумя переменными?» (PDF) , Труды 45-го симпозиума IEEE по основам информатики , стр. 146–154, заархивировано (PDF) из оригинала 15 июля 2019 г. , получено 29 августа 2019 г..
  6. ^ Гоеманс, MX ; Уильямсон, Д.П. (1995), «Улучшенные алгоритмы аппроксимации для задач максимального разреза и выполнимости с использованием полуопределенного программирования», Journal of the ACM , 42 (6): 1115–1145, doi : 10.1145/227683.227684.
  7. ^ Вазирани, Виджай В. (2004), Алгоритмы аппроксимации , Springer, стр. 97–98, ISBN 3-540-65367-8.
  8. ^ Арора, Санджив ; Рао, Сатиш; Вазирани, Умеш (2009), «Расширяющие потоки, геометрические вложения и разделение графов», J. ACM , ACM, 56 (2): 1–37, doi : 10.1145/1502793.1502794, S2CID  263871111.
  9. ^ Гросс, Джонатан Л.; Йеллен, Джей (2005), «4.6 Графы и векторные пространства», Теория графов и ее приложения (2-е изд.), CRC Press, стр. 197–207, ISBN 9781584885054.
  10. ^ Дистель, Рейнхард (2012), «1.9 Некоторые линейные алгебры», Теория графов, Тексты для выпускников по математике, том. 173, Спрингер, стр. 23–28..
  11. ^ Корте, BH ; Виген, Йенс (2008), «8.6 Деревья Гомори – Ху», Комбинаторная оптимизация: теория и алгоритмы , Алгоритмы и комбинаторика, том. 21, Спрингер, стр. 180–186, ISBN. 978-3-540-71844-4.