Русская Википедия:Декомпозиция графа на ветви

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

Файл:Branch-decomposition.svg
Декомпозиция на ветви решётки. Показано e-разделение. Разделение, декомпозиция, и сам граф имеют ширину три.

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

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

Определения

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

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

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

Декомпозиция графа на ветви тесно связана с древесной декомпозицией, а ширина ветвления тесно связана с древесной шириной. Две эти величины отличаются не более чем на постоянный множитель. В частности, в статье, в которой они предложили ширину ветвления, Шаблон:Не переведено 5 и Пол СеймурШаблон:Sfn показали, что для графа G с древесной шириной k и шириной ветвления Шаблон:Nowrap

<math>b -1 \le k \le \left\lfloor\frac{3}{2}b\right\rfloor -1.</math>

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

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

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

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

Задача определения, имеет ли граф G декомпозицию на ветви с шириной, не превосходящей k, является NP-полной, если G и k являются входными данными задачиШаблон:Sfn. Однако графы с шириной ветвления не большей k, образуют семейство графов, замкнутое по минорамШаблон:Sfn, откуда следует, что вычисление ширины ветвления является Шаблон:Не переведено 5 задачей: существует алгоритм для вычисления оптимальной декомпозиции на ветви, время работы которого на графах с шириной ветвления, не превосходящей k для некоторой постоянной k, линейно зависит от размера графа[1]

Для планарных графов ширина ветвления может быть вычислена за линейное время. Это контрастирует с древесной шириной, для которой сложность вычисления на планарных графах является хорошо известной открытой проблемойШаблон:Sfn. Исходный алгоритм вычисления ширины ветвления для планарных графов Пола Сеймура и Робина Томаса решал задачу за время O(n2) на графе с n вершинами, а их алгоритм для построения декомпозиции на ветви работал за время O(n4)Шаблон:Sfn. Позднее последний был улучшен до O(n3)Шаблон:Sfn.

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

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

Можно также определить понятие декомпозиции по ветвям для матроидов, что обобщает декомпозицию графов по ветвямШаблон:Sfn. Декомпозиция матроида по ветвям является иерархической кластеризацией элементов матроида, представленная как некорневое бинарное дерево с элементами матроида в качестве листьев. Для матроидов e-разделение можно определить тем же способом, что и для графов, а в результате получаем разделения множества M элементов матроида на два подмножества A и B. Если через ρ обозначить функцию ранга матроида, то ширина e-разделения определяется как Шаблон:Nowrap, а ширина декомпозиции и ширина ветвления матроида определяются аналогично определениям для графа. Ширина ветвления графа и ширина ветвления соответствующего Шаблон:Не переведено 5 могут отличаться. Например, путь из трёх рёбер и звезда из трёх рёбер имеют разные ширины ветвления, 2 и 1 соответственно, но для них графовый матроид один и тот же, и он имеет ширину ветвления 1Шаблон:Sfn. Однако для графов, не являющихся деревьями, ширина ветвления графа равна ширине ветвления ассоциированного графового матроидаШаблон:SfnШаблон:Sfn. Ширина ветвления матроида равна ширине ветвления его Шаблон:Не переведено 5, и из этого в частности следует, что ширина ветвления любого планарного графа, не являющегося деревом, равна ширине ветвления его двойственного графаШаблон:Sfn.

Ширина ветвления является важной компонентой попыток расширить теорию миноров графа на Шаблон:Не переведено 5 — хотя древесная ширина может быть также обобщена на матроидыШаблон:Sfn и играет в теории миноров графов бо́льшую роль, чем ширина ветвления, ширина ветвления имеет более удобные свойства в матроидахШаблон:Sfn. Робертсон и Сеймур высказали предположение, что матроиды, представимые любым конкретным конечным полем, Шаблон:Не переведено 5, что является аналогией теоремы Робертсона – Сеймура для графов, но гипотеза доказана только для матроидов с ограниченной шириной ветвленияШаблон:SfnШаблон:Sfn. Кроме того, если семейство матроидов, замкнутое по минорам и представимое конечным полем, не включает графовые матроиды всех планарных графов, то существует постоянная, ограничивающая ширину ветвления в семействе, что обобщает соответствующее утверждение для семейств графов, замкнутых по минорамШаблон:SfnШаблон:Sfn.

Для любого фиксированного k матроиды с шириной ветвления, не превосходящей k, могут быть распознаны за полиномиальное время алгоритмом, который получает доступ к матроиду через Шаблон:Не переведено 5 Шаблон:Sfn.

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

Файл:Branchwidth 3-forbidden minors.svg
Четыре запрещённых минора для графов ширины ветвления три.

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

Запрещённые миноры изучаются также и для ширины ветвления матроида, несмотря на отсутствие полной аналогии теоремы Робертсона — Сеймура в этом случае. Матроид имеет ширину ветвления единица тогда и только тогда, когда любой элемент является либо петлёй, либо копетлёй, так что единственным минимальным запрещённым минором является Шаблон:Не переведено 5 U(2,3), графовый матроид треугольного графа. Матроид имеет ширину ветвления два тогда и только тогда, когда он является графовым матроидом графа с шириной ветвления два, так что минимальными запрещёнными минорами являются графовые матроиды графа K4 и неграфовый матроид U(2,4). Матроиды с шириной ветвления три не вполне квазиупорядоченны без дополнительного предположения представления над конечным полем, но, тем не менее, матроиды с любой ограниченной шириной ветвления имеют конечное число минимальных запрещённых миноров, которые имеют число элементов, зависящих от ширины ветвления не более чем экспоненциальноШаблон:SfnШаблон:Sfn.

Примечания

Шаблон:Примечания

Литература

Шаблон:Refbegin

Шаблон:Refend

Шаблон:Rq

Партнерские ресурсы
Криптовалюты
Магазины
Хостинг
Разное

  1. ↑ Шаблон:Harvtxt. Фомин, Мацойт и Тодинка Шаблон:Harvtxt описывают алгоритм с улучшенной зависимостью от k, (2√3)k, но зависимость от числа вершин увеличивается от линейного к квадратичному.
  2. ↑ Шаблон:Harvtxt. Четвёртый запрещённый минор для древесной ширины три, граф пентагональной призмы, имеет граф куба в качестве минора, так что он не является минимальным для ширины ветвления три.
Источник — http://wikihandbk.com/ruwiki/index.php?title=Русская_Википедия:Декомпозиция_графа_на_ветви&oldid=9699653