WikiSort.ru - Не сортированное

В теории графов декомпозиция на ветви неориентированного графа G — это иерархическая кластеризация рёбер графа G, представленная некорневым бинарным деревом T с рёбрами из G в качестве листьев. Удаление любого ребра из T делит рёбра графа G на два подграфа, а шириной декомпозиции считается максимальное число общих вершин в любом подграфе, полученным таким образом. Ширина ветвления графа G — это минимальная ширина любой декомпозиции графа G на ветви.

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

Определения

Некорневое бинарное дерево — это связный неориентированный граф без циклов, в котором каждый нелистовой узел имеет в точности три соседа. Декомпозиция на ветви может быть представлена как некорневое бинарное дерево T вместе с биекцией между листьями дерева T и рёбрами заданного графа G = (V,E). Если e — любое ребро дерева T, то удаление e из T делит его на два поддерева T₁ и T₂. Это разделение дерева T на поддеревья порождает разделение рёбер, ассоциированных с листьями дерева T, на два подграфа графа G, G₁ и G₂. Такое деление графа G на два подграфа называется e-разделением.

Ширина e-разделения — это число вершин графа G, которые инцидентны как рёбрам из E₁, так и рёбрам из E₂. То есть это множество вершин, общих для подграфов G₁ и G₂. Ширина декомпозиции на ветви — это максимальная ширина любого e-разделения. Ширина ветвления графа G — это минимальная ширина декомпозиций по ветвям графа G.

Связь с шириной дерева

Декомпозиция графа на ветви тесно связана с древесной декомпозицией, а ширина ветвления тесно связана с древесной ширине. Две эти величины отличаются не более чем на постоянный множитель. В частности, в статье, в которой они предложили ширину ветвления, Нейл Робертсон^[en] и Пол Сеймур^[en][1] показали, что для графа G с древесной шириной k и шириной ветвления b > 1

${\displaystyle b-1\leq k\leq \left\lfloor {\frac {3}{2}}b\right\rfloor -1.}$

Ширина нарезки

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

Алгоритмы определения ширины ветвления обычно работают путём сведения к эквивалентной задаче определения ширины нарезки. В частности, ширина нарезки срединного графа в точности вдвое больше ширины ветвления исходного графа^[2].

Алгоритмы и сложность

Задача определения, имеет ли граф G декомпозицию на ветви с шириной, не превосходящей k, является NP-полной, если G и k являются входными данными задачи^[2]. Однако графы с шириной ветвления, не большей k, образуют семейство графов, замкнутое по минорам^[3], откуда следует, что вычисление ширины ветвления является фиксированно-параметрически разрешимой^[en] задачей — существует алгоритм для вычисления оптимальной декомпозиции на ветви, время работы которого на графах с шириной ветвления, не превосходящей k для некоторой постоянной k, линейно зависит от размера графа^[4]

Для планарных графов ширина ветвления может быть вычислена за линейное время. Это контрастирует с древесной шириной, для которой сложность вычисления на планарных графах является хорошо известной открытой проблемой^[5]. Исходный алгоритм вычисления ширины ветвления для планарных графов Пола Сеймура^[en] и Робина Томаса решал задачу за время O(n²) на графе с n вершинами, а их алгоритм для построения декомпозиции на ветви работал за время O(n⁴)^[2]. Позднее последний был ускорен до O(n³)^[6].

Как и в случае древесной ширины, ширина ветвления может быть использована в качестве базиса алгоритмов динамического программирования для многих NP-трудных задач оптимизации, и в этих алгоритмах время решения будет экспоненциальным от ширины входного графа или матроида^[7][8]. Например, Кук и и Сеймур^[9] применили основанный на ширине ветвления метод динамического программирования к задаче слияния частичных решений задачи коммивояжёра в одно глобальное решение путём формирования разреженного графа из объединения частичных решений, для чего использовалась эвристическая спектральная кластеризация для нахождения хорошей декомпозиции на ветви, после чего к полученной декомпозиции они применили динамическое программирование. Фомин и Тиликос^[10] убеждают, что ширина ветвления работает лучше, чем древесная ширина, при разработке фиксированно-параметрически разрешимых алгоритмов на планарных графах по многим причинам — ширина ветвления может быть теснее ограничена функцией параметра, чем ограничение древесной ширины, она может быть вычислена за полиномиальное время и алгоритм вычисления ширина ветвления не имеет больших скрытых констант.

Обобщения для матроидов

Можно также определить понятие декомпозиции по ветвям для матроидов, что обобщает декомпозицию графов по ветвям^[11]. Декомпозиция матроида по ветвям является иерархической кластеризацией элементов матроида, представленная как некорневое бинарное дерево с элементами матроида в качестве листьев. Для матроидов e-разделение можно определить тем же способом, что и для графов, а в результате получаем разделения множества M элементов матроида на два подмножества A и B. Если через ρ обозначить функцию ранга матроида, то ширина e-разделения определяется как ρ(A) + ρ(B) − ρ(M) + 1, а ширина декомпозиции и ширина ветвления матроида определяются аналогично определениям для графа. Ширина ветвления графа и ширина ветвления соответствующего графового матроида^[en] могут отличаться. Например, путь из трёх рёбер и звезда из трёх рёбер имеют разные ширины ветвления, 2 и 1 соответственно, но для них графовый матроид один и тот же, и он имеет ширину ветвления 1^[12]. Однако для графов, не являющихся деревьями, ширина ветвления графа равна ширине ветвления ассоциированного графового матроида^[12][13]. Ширина ветвления матроида равна ширине ветвления его двойственного матроида^[en], и, в частности, из этого следует, что ширина ветвления любого планарного графа, не являющегося деревом, равна ширине ветвления его двойственного графа^[12].

Ширина ветвления является важной компонентой попыток расширить теорию миноров графа на миноры матроидов^[en] — хотя древесная ширина может быть также обобщена на матроиды^[14] и играет в теории миноров графов бо́льшую роль, чем ширина ветвления, ширина ветвления имеет более удобные свойства в матроидах^[15]. Робертсон и Сеймур высказали предположение, что матроиды, представимые любым конкретным конечным полем, вполне квазиупорядоченны^[en], что является аналогией Теорема Робертсона – Сеймура для графов, но гипотеза доказана только для матроидов с ограниченной шириной ветвления^[16][15]. Кроме того, если семейство матроидов, замкнутое по минорам и представимое конечным полем, не включает графовые матроиды всех планарных графов, то существует постоянная, ограничивающая ширину ветвления в семействе, что обобщает соответствующее утверждение для семейств графов, замкнутых по минорам^[15][17].

Для любого фиксированного k матроиды с шириной ветвления, не превосходящей k, могут быть распознаны за полиномиальное время алгоритмом, который получает доступ к матроиду через оракула независимости^{[en] [18]}.

Запрещённые миноры

По теореме Робертсона — Сеймура графы с шириной ветвления k могут быть охарактеризованы конечным множеством запрещённых миноров. Графы с шириной ветвления 0 — это паросочетания, а минимальные запрещённые миноры в этом случае — это путь из двух дуг и треугольный граф (а также цикл из двух дуг, если рассматриваются мультиграфы)^[19]. Графы с шириной ветвления 1 — это графы, в которых каждая связная компонента является звездой, а минимальные запрещённые миноры для графов с шириной ветвления 1 — это треугольный граф (или цикл из двух дуг, если рассматриваются мультиграфы) и пути из трёх дуг^[19]. Графы с шириной ветвления 2 — это графы, в которых каждая двусвязная компонента является параллельно-последовательным графом, а единственным минимальным запрещённым минором является полный граф K₄ из четырёх вершин^[19]. Граф имеет ширину ветвления три тогда и только тогда, когда его древесная ширина равна трём и он не имеет граф гиперкуба в качестве минора. Таким образом, четыре запрещённых минора — это три из четырёх запрещённых миноров графов с древесной шириной три (граф октаэдра, полный граф K₅, и граф Вагнера) вместе с графом куба^[20].

Запрещённые миноры изучаются также для ширины ветвления матроида, вопреки отсутствия полной аналогии теоремы Робертсона — Сеймура в этом случае. Матроид имеет ширину ветвления единица тогда и только тогда, когда любой элемент является либо петлёй, либо копетлёй, так что единственным минимальным запрещённым минором является однородный матроид^[en] U(2,3), графовый матроид треугольного графа. Матроид имеет ширину ветвления два тогда и только тогда, когда он является графовым матроидом графа с шириной ветвления два, так что минимальными запрещёнными минорами являются графовые матроиды графа K₄ и неграфовый матроид U(2,4). Матроиды с шириной ветвления три не вполне квазиупорядоченны без дополнительного предположения представления над конечным полем, но, тем не менее, матроиды с любой ограниченной шириной ветвления имеют конечное число минимальных запрещённых миноров, которые имеют число элементов, зависящих от ширины ветвления не более чем экспоненциально^[21][22].

Примечания

Литература

Для улучшения этой статьи желательно: Проверить качество перевода с иностранного языка. Исправить статью согласно стилистическим правилам Википедии.