Ширина резьбы

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

Определение и примеры

Ширина вырезания определяется с точки зрения иерархической кластеризации вершин данного графа, называемой «резьбой». Резьбу можно описать как некорневое двоичное дерево , листья которого помечены вершинами данного графа. Удаление любого ребра из этого дерева разбивает дерево на два поддерева и, соответственно, разбивает вершины дерева на два кластера. Сформированные таким образом кластеры вершин составляют семейство ламинарных множеств : любые два кластера вершин (а не только два дополнительных кластера, образованных удалением одного и того же ребра) либо не пересекаются, либо один содержится в другом. Определенная таким образом ширина резьбы — это максимальное количество ребер, соединяющих два дополнительных кластера. Ширина вырезания графа — это минимальная ширина любой иерархической кластеризации. ^{[ 1 ]}

Графы вырезания ширины один являются в точности паросочетаниями . Графы вырезающей ширины два - это в точности те графы, которые образованы из непересекающихся объединений графов путей и графов циклов . Графы вырезания шириной три представляют собой субкубические частичные 2-деревья. Это означает, что их максимальная степень равна трем и что они являются подграфами последовательно-параллельных графов . Все остальные графы имеют ширину резьбы не менее четырех. ^{[ 2 ]}

Вычислительная сложность

Ширина вырезания в целом NP-сложна , но может быть вычислена за полиномиальное время в плоских графах . ^{[ 1 ]} Его можно аппроксимировать с точностью до константы того же коэффициента аппроксимации , что и сбалансированные разрезы . ^{[ 3 ]} для которого текущий коэффициент наилучшего приближения равен $O({\sqrt {\log n}})$ . ^{[ 4 ]} Он также доступен для работы с фиксированными параметрами : для любого фиксированного параметра. $k$ , проверяя, не превышает ли ширина резьбы $k$ , и если да, то поиск иерархической кластеризации, реализующей эту ширину, может быть выполнен за линейное время . ^{[ 5 ]} В общем, точное вычисление ширины резьбы на мультиграфе с $n$ вершины и $m$ края, можно сделать вовремя $O(2^{n}n^{3}\log n\log \log n\log m)$ . ^{[ 6 ]}

Связанные параметры

Ширина вырезания — это лишь один из нескольких параметров ширины графа, которые измеряют, насколько древовидным является данный граф. Другие включают ширину дерева и ширину ветки . Ширина ветвления графа определяется аналогично ширине вырезания с использованием иерархической кластеризации, но для ребер графа, а не для его вершин; они называются ветвящимися разложениями . Вырезание графа можно преобразовать в разложение ветвей, прикрепив каждое ребро графа к одной из двух его конечных точек и развернув каждый лист вырезания в поддерево, представляющее присоединенные к нему ребра. Используя эту конструкцию, можно показать, что для любого графа ширина вырезания больше или равна половине ширины ветви и меньше или равна степени, умноженной на ширину ветви. Поскольку ширина дерева и ширина ветвей всегда находятся в пределах постоянных коэффициентов друг друга, аналогичные границы можно использовать для связи ширины резьбы с шириной дерева. ^{[ 7 ]}

Другой параметр ширины, определяемый количеством ребер, охватывающих разрезы в графе, — это его ширина разреза , определяемая с использованием линейного порядка вершин графа и системы разбиений, отделяющих более ранние от более поздних вершин в этом порядке. ^{[ 5 ]} В отличие от ширины резьбы, эта система разделов не включает в себя перегородку, отделяющую каждую вершину от остальных вершин, поэтому (несмотря на использование более ограниченного класса семейств разрезов) ширина разреза может быть меньше ширины резьбы. Однако ширина резьбы всегда не превышает максимальной ширины реза и максимальной степени графа. ^{[ 7 ]}

Ссылки

^ Jump up to: ^а ^б Сеймур, Пол Д .; Томас, Робин (1994), «Маршрутизация вызовов и крысолов», Combinatorica , 14 (2): 217–241, doi : 10.1007/BF01215352 , S2CID 7508434
^ Бельмонте, Реми; ван 'т Хоф, Пим; Каминский, Марцин; Паулюсма, Даниэль; Тиликос, Димитриос М. (2013), «Характеристика графов небольшой ширины резьбы», Discrete Applied Mathematics , 161 (13–14): 1888–1893, doi : 10.1016/j.dam.2013.02.036 , MR 3056995
^ Хуллер, Самир; Рагхавачари, Баладжи; Янг, Нил (апрель 1994 г.), «Проектирование деревьев потоков нескольких товаров», Information Processing Letters , 50 (1): 49–55, arXiv : cs/0205077 , doi : 10.1016/0020-0190(94)90044-2
^ Арора, Санджив ; Рао, Сатиш ; Вазирани, Умеш (2009), «Расширяющие потоки, геометрические вложения и разделение графов» (PDF) , Журнал ACM , 56 (2): A5:1–A5:37, doi : 10.1145/1502793.1502794 , MR 2535878 , S2CID 263871111
^ Jump up to: ^а ^б Тиликос, Димитриос М.; Серна, Мария Дж .; Бодлендер, Ханс Л. (2000), «Алгоритмы конструктивного линейного времени для малой ширины резания и резания», Ли, Д.Т.; Тенг, Шан-Хуа (ред.), «Алгоритмы и вычисления», 11-я Международная конференция, ISAAC 2000, Тайбэй, Тайвань, 18–20 декабря 2000 г., Труды , конспекты лекций по информатике, том. 1969, Springer, стр. 192–203, номер документа : 10.1007/3-540-40996-3_17 , ISBN. 978-3-540-41255-7
^ Оум, Санг-ил (2009), «Точный расчет ширины ранга», Information Processing Letters , 109 (13): 745–748, CiteSeerX 10.1.1.483.6708 , doi : 10.1016/j.ipl.2009.03.018 , MR 2527717
^ Jump up to: ^а ^б Эппштейн, Дэвид (2018), «Влияние планаризации на ширину», Журнал графовых алгоритмов и приложений , 22 (3): 461–481, arXiv : 1708.05155 , doi : 10.7155/jgaa.00468 , S2CID 28517765

[seytho-1] Jump up to: ^а ^б Сеймур, Пол Д .; Томас, Робин (1994), «Маршрутизация вызовов и крысолов», Combinatorica , 14 (2): 217–241, doi : 10.1007/BF01215352 , S2CID 7508434

[bhkpt-2] Бельмонте, Реми; ван 'т Хоф, Пим; Каминский, Марцин; Паулюсма, Даниэль; Тиликос, Димитриос М. (2013), «Характеристика графов небольшой ширины резьбы», Discrete Applied Mathematics , 161 (13–14): 1888–1893, doi : 10.1016/j.dam.2013.02.036 , MR 3056995

[kry-3] Хуллер, Самир; Рагхавачари, Баладжи; Янг, Нил (апрель 1994 г.), «Проектирование деревьев потоков нескольких товаров», Information Processing Letters , 50 (1): 49–55, arXiv : cs/0205077 , doi : 10.1016/0020-0190(94)90044-2

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

[tsb-5] Jump up to: ^а ^б Тиликос, Димитриос М.; Серна, Мария Дж .; Бодлендер, Ханс Л. (2000), «Алгоритмы конструктивного линейного времени для малой ширины резания и резания», Ли, Д.Т.; Тенг, Шан-Хуа (ред.), «Алгоритмы и вычисления», 11-я Международная конференция, ISAAC 2000, Тайбэй, Тайвань, 18–20 декабря 2000 г., Труды , конспекты лекций по информатике, том. 1969, Springer, стр. 192–203, номер документа : 10.1007/3-540-40996-3_17 , ISBN. 978-3-540-41255-7

[oum-6] Оум, Санг-ил (2009), «Точный расчет ширины ранга», Information Processing Letters , 109 (13): 745–748, CiteSeerX 10.1.1.483.6708 , doi : 10.1016/j.ipl.2009.03.018 , MR 2527717

[eppstein-7] Jump up to: ^а ^б Эппштейн, Дэвид (2018), «Влияние планаризации на ширину», Журнал графовых алгоритмов и приложений , 22 (3): 461–481, arXiv : 1708.05155 , doi : 10.7155/jgaa.00468 , S2CID 28517765

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]