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

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

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

Определение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ссылки

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