Ветка-разложение - Branch-decomposition

Разложение по ветвям сетка графика, показывая электронное разделение. Разделение, декомпозиция и граф имеют ширину три.

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

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

Определения

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

Ширина е-разделения - это количество вершин грамм которые относятся как к краю E₁ и к краю E₂; то есть это количество вершин, которые разделяют два подграфа грамм₁ и грамм₂. Ширина разложения ветвей - это максимальная ширина любого из его электронных разделений. Пропускная способность грамм - минимальная ширина ветвления разложения грамм.

Отношение к ширине дерева

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

${displaystyle b-1leq kleq leftlfloor {frac {3} {2}} bightfloor -1.}$

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

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

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

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

это НП-полный чтобы определить, грамм имеет разложение по ветвям шириной не более k, когда грамм и k оба рассматриваются как входы в проблему.^[2] Однако графики с максимальной пропускной способностью k сформировать минорно-замкнутое семейство графов,^[3] из чего следует, что вычисление ширины ветвления управляемый с фиксированными параметрами: существует алгоритм вычисления оптимальных разложений ветвей, время выполнения которых, на графиках ширины ветвления k для любой фиксированной постоянной k, линейно зависит от размера входного графа.^[4]

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

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

Обобщение на матроиды

Также возможно определить понятие разложения по ветвям для матроиды который обобщает разложения по ветвям графов.^[8] Разбиение по ветвям матроида - это иерархическая кластеризация элементов матроида, представленная в виде бинарного дерева без корня с элементами матроида на его листьях. Электронное разделение может быть определено так же, как и для графов, и приводит к разбиению множества M элементов матроида на два подмножества А и B. Если ρ обозначает функция ранга матроида, то ширина электронного разделения определяется как ρ (А) + ρ (B) - ρ (M) + 1, ширина разложения и ветвь матроида определяются аналогично. Ширина ветвления графа и ширина ветвления соответствующего графический матроид могут отличаться: например, трехгранный граф путей и трехгранный звезда имеют разную ширину ветвления, 2 и 1 соответственно, но оба они вызывают один и тот же графический матроид с шириной ветвления 1.^[9] Однако для графов, которые не являются деревьями, ширина ветвления графа равна ширине ветвления связанного с ним графического матроида.^[10] Ширина ветвления матроида равна ширине ветвления его двойной матроид, и, в частности, это означает, что ширина ветвления любого плоского графа, не являющегося деревом, равна ширине ветвления его двойственного.^[9]

Полоса пропускания - важный компонент попыток расширить теорию граф миноры к несовершеннолетние матроиды: несмотря на то что ширина дерева также можно обобщить на матроидов,^[11] и играет большую роль, чем ширина ветвления в теории миноров графов, ширина ветвления имеет более удобные свойства в настройке матроида.^[12] Робертсон и Сеймур предположили, что матроиды, представимые над любым конкретным конечное поле находятся квазиупорядоченный, аналогично Теорема Робертсона – Сеймура для графов, но пока это доказано только для матроидов с ограниченной шириной ветвления.^[13] Кроме того, если минорно-замкнутое семейство матроидов, представимых над конечным полем, не включает графические матроиды всех планарных графов, то существует постоянная граница ширины ветвления матроидов в семействе, обобщая аналогичные результаты для минорно-замкнутого графа. семьи.^[14]

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

Запрещенные несовершеннолетние

Четверка запрещенные несовершеннолетние для графиков с шириной ветвления три.

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

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

Примечания

Рекомендации