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

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

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

Определение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

См. также

Ссылки

^ «Документация NetworkX 2.6.2» . networkx.algorithms.cuts.cut_size . Архивировано из оригинала 18 ноября 2021 г. Проверено 10 декабря 2021 г. Разрез — это разбиение узлов графа на два множества. Размер разреза представляет собой сумму весов ребер «между» двумя наборами узлов.
^ Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Стейн, Клиффорд (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), «Сводимость комбинаторных задач», в Миллер, Р.Э.; Тэчер, Дж. В. (ред.), Сложность компьютерных вычислений , Нью-Йорк: Plenum Press, стр. 85–103 .
^ Хот, С. ; Киндлер, Г.; Моссель, Э.; О'Доннелл, Р. (2004), «Оптимальные результаты неаппроксимируемости для MAX-CUT и других CSP с двумя переменными?» (PDF) , Труды 45-го симпозиума IEEE по основам информатики , стр. 146–154, заархивировано (PDF) из оригинала 15 июля 2019 г. , получено 29 августа 2019 г.
^ Гоеманс, MX ; Уильямсон, Д. П. (1995), «Улучшенные алгоритмы аппроксимации для задач максимального разреза и выполнимости с использованием полуопределенного программирования», Journal of the ACM , 42 (6): 1115–1145, doi : 10.1145/227683.227684 .
^ Vazirani, Vijay V. (2004), Approximation Algorithms , Springer, pp. 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 Некоторые линейные алгебры», Теория графов , Тексты для выпускников по математике, том. 173, Спрингер, стр. 23–28 .
^ Корте, Британская Колумбия ; Виген, Йенс (2008), «8.6 Деревья Гомори – Ху», Комбинаторная оптимизация: теория и алгоритмы , Алгоритмы и комбинаторика, том. 21, Спрингер, стр. 180–186, ISBN. 978-3-540-71844-4 .

[networkx.algorithms.cuts.cut_size-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] Vazirani, Vijay V. (2004), Approximation Algorithms , Springer, pp. 97–98, ISBN 3-540-65367-8 .

[8] Арора, Санджив ; Рао, Сатиш; Вазирани, Умеш (2009), «Расширяющие потоки, геометрические вложения и разделение графов», J. ACM , 56 (2), ACM: 1–37, doi : 10.1145/1502793.1502794 , S2CID 263871111 .

[gy-9] Гросс, Джонатан Л.; Йеллен, Джей (2005), «4.6 Графы и векторные пространства», Теория графов и ее приложения (2-е изд.), CRC Press, стр. 197–207, ISBN 9781584885054 .

[diestel-10] Дистель, Рейнхард (2012), «1.9 Некоторые линейные алгебры», Теория графов , Тексты для выпускников по математике, том. 173, Спрингер, стр. 23–28 .

[11] Корте, Британская Колумбия ; Виген, Йенс (2008), «8.6 Деревья Гомори – Ху», Комбинаторная оптимизация: теория и алгоритмы , Алгоритмы и комбинаторика, том. 21, Спрингер, стр. 180–186, ISBN. 978-3-540-71844-4 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]