Ширина реза

График с шириной разреза 2. Для показанного порядка вершин слева направо каждая вертикальная линия пересекает не более двух ребер.

В теории графов ширина разреза — неориентированного графа это наименьшее целое число. $k$ со следующим свойством: существует упорядочение вершин графа такое, что каждый разрез , полученный разбиением вершин на более ранние и последующие подмножества упорядочения, пересекается не более чем $k$ края. То есть, если вершины пронумерованы $v_{1},v_{2},\dots v_{n}$, то для каждого $\ell =1,2,\dots n-1$, количество ребер $v_{i}v_{j}$ с $i\leq \ell$ и $j>\ell$ самое большее $k$.

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

Связь с другими параметрами

Ширина разреза связана с несколькими другими параметрами ширины графиков. В частности, он всегда не меньше ширины дерева или пути того же графа. Однако это не более чем ширина пути, умноженная на $O(\Delta )$, или ширина дерева, умноженная на $O(\Delta \log n)$ где $\Delta$ это максимальная степень и $n$ это количество вершин. Если семейство графов имеет ограниченную максимальную степень и его графы не содержат подразделений полных бинарных деревьев неограниченного размера, то графы в семействе имеют ограниченную ширину разреза. В субкубических графах (графах максимальной степени три) ширина разреза равна ширине пути плюс один.

Ширина разреза больше или равна минимальному числу делений пополам любого графа. Это минимально возможное количество ребер от одной стороны к другой для разделения вершин на два подмножества одинакового размера (или как можно более близкого к нему). Любая линейная компоновка графа, достигающая оптимальной ширины разреза, также обеспечивает деление пополам с одинаковым числом ребер, полученное разделением компоновки на первую и вторую половины. Ширина разреза меньше или равна максимальной степени, умноженной на пропускную способность графа , максимальное количество шагов, разделяющих конечные точки любого ребра в линейном расположении, выбранном для минимизации этой величины. В отличие от полосы пропускания, ширина разреза не изменяется, когда ребра подразделяются на пути, состоящие из более чем одного ребра. Это тесно связано с «топологической пропускной способностью», минимальной пропускной способностью, которую можно получить путем разделения ребер данного графа. В частности, для любого дерева оно зажато между топологической полосой пропускания $b^{*}$ и немного большее число, $b^{*}+\log _{2}b^{*}+2$.

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

Ширина разреза может использоваться для обеспечения нижней границы другого параметра, числа пересечений , возникающего при изучении графических рисунков . Число пересечений графа — это минимальное количество пар пересекающихся ребер на любом рисунке графа на плоскости, где каждая вершина касается только тех ребер, для которых она является конечной точкой. В графах ограниченной степени число пересечений всегда как минимум пропорционально квадрату ширины разреза. Более точная граница, применимая к графам, в которых степени не ограничены, выглядит следующим образом: $$\operatorname {crossings} (G)\geq {\frac {1}{1176}}\operatorname {cutwidth} (G)^{2}-\sum _{v\in V(G)}\left({\frac {\deg(v)}{4}}\right)^{2}.$$ Здесь поправочный член, пропорциональный сумме квадратов градусов, необходим для учета существования плоских графов , квадрат ширины разреза которых пропорционален этой величине, но число пересечений которых равно нулю. В другом стиле рисования графов, встраивании книги , вершины располагаются на линии, а ребра располагаются без пересечений в отдельные полуплоскости, страницы встречающиеся на этой линии. Ширина страницы встраивания книги определяется как наибольшая ширина любой из страниц с использованием того же порядка вершин.

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

Со временем можно определить ширину разреза и построить линейную планировку оптимальной ширины. $O(n\log n)$ для дерева ​ $n$ вершины. Для более общих графов это NP-трудно . Она остается NP-трудной даже для плоских графов максимальной степени три, а взвешенная версия задачи (минимизация веса ребер в любом разрезе линейного расположения) является NP-трудной, даже если входными данными является дерево.

Ширина разреза — одна из многих задач оптимального линейного расположения, которую можно решить точно в срок. $O(n2^{n})$ по алгоритму Хелда-Карпа , с использованием динамического программирования . Более быстрый квантовый алгоритм со временем $O(1.817^{n})$ также известно. Кроме того, он доступен для фиксированных параметров : для любого фиксированного значения $c$, можно проверить, имеет ли граф ширину разреза не более $c$, и если да, то найти для него оптимальный порядок вершин за линейное время . Точнее, с точки зрения обоих $n$ и $c$, время работы этого алгоритма ${\textstyle 2^{O(c^{2})}n}$. Альтернативный параметризованный алгоритм, более подходящий для графов, в которых небольшое количество вершин имеет высокую степень (что делает ширину разреза большой), вместо этого решает проблему за полиномиальное время. $n$ когда граф имеет вершинное покрытие ограниченного размера, путем преобразования его в задачу целочисленного программирования с небольшим количеством переменных и полиномиальными границами значений переменных. Остается открытым, можно ли эффективно решить проблему для графов ограниченной древовидной ширины, которые включали бы обе параметризации по ширине разреза и числу вершинного покрытия.

Cutwidth имеет схему аппроксимации с полиномиальным временем для плотных графов , но для графов, которые могут быть неплотными, лучший коэффициент аппроксимации равен известный ${\textstyle O{\bigl (}(\log n)^{3/2}{\bigr )}}$. Это основано на методе Тома Лейтона и Сатиша Рао , позволяющего уменьшить приблизительную ширину разреза до минимального числа делений пополам, теряя при этом коэффициент $\log _{2}n$ в коэффициенте аппроксимации, используя рекурсивное сечение пополам для упорядочивания вершин. Комбинируя этот метод рекурсивного деления пополам с другим методом Санджива Ароры , Рао и Умеша Вазирани для аппроксимации минимального числа деления пополам, дает указанный коэффициент аппроксимации. Согласно гипотезе расширения малого множества невозможно достичь постоянного коэффициента аппроксимации.

Приложения

Задача маршрутизации каналов, в которой пары пронумерованных контактов должны быть соединены по горизонтальным «каналам» в прямоугольной области.

Решение с использованием пяти каналов

Раннее мотивирующее применение ширины выреза включало маршрутизацию каналов в конструкции СБИС , в которой компоненты, расположенные сверху и снизу прямоугольной области интегральной схемы, должны быть соединены проводниками, которые соединяют пары контактов, прикрепленных к компонентам. Если компоненты могут располагаться в разном порядке слева направо, но выводы каждого компонента должны оставаться смежными, то это можно перевести в задачу выбора линейного расположения графа с вершиной для каждого компонента и ребро для каждого штырькового соединения. Ширина разреза графа контролирует количество каналов, необходимых для маршрутизации цепи.

В белковой инженерии предположение о том, что ассоциированный граф имеет ограниченную ширину разреза, использовалось для ускорения поиска последовательностей мРНК , которые одновременно кодируют данную белковую последовательность и сворачиваются в заданную вторичную структуру .

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

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