Древесная ширина (теория графов)

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

В теории графов древесная ширина неориентированного графа — это число, ассоциированное с графом. Древесную ширину можно определить несколькими эквивалентными путями: как размер наибольшего множества вершин в древесном разложении, как размер наибольшей клики в хордальном дополнении графа, как максимальный порядок убежища при описании стратегии игры преследования на графе или как максимальный порядок ежевики, набора связных подграфов, которые касаются друг друга. Древесная ширина часто используется в качестве параметра в анализе параметрической сложности[англ.] алгоритмов на графах. Графы с шириной дерева, не превосходящей k, называются частичными k-деревьями. Многие другие хорошо изученные семейства графов также имеют ограниченную ширину дерева.

Понятие ширины дерева ввёл Халин (Halin 1976) основываясь на другом параметре, числе Хадвигера, с которым древесная ширина имеет ряд общих свойств. Позже древесную ширину переоткрыли Робертсон и Сеймур[1], и с тех пор она изучалась многими авторами.[2]

Определение

[править | править код]
Граф с восемью вершинами и его древесное разложение, которое имеет шесть вершин. Каждое ребро графа соединяет две вершины, и эти вершины входят в список некоторой вершины дерева вместе, а каждая вершина входит в список каждой вершины поддерева. Каждая вершина дерева содержит список максимум в три вершины, так что ширина этого разложения равна двум.

Древесное разложение графа G = (V, E) — это дерево T, вершинами X1, ..., Xn которого являются подмножества V, удовлетворяющие следующим свойствам[3]:

  1. Объединение всех множеств Xi равно V. Таким образом, любая вершина графа содержится хотя бы в одном множестве.
  2. Если Xi и Xj оба содержат вершину v, то все остальные вершины дерева Xk на (единственном) пути из Xi в Xj также содержат v. Это эквивалентно утверждению, что вершины дерева, содержащие v, образуют связное поддерево T.
  3. Для любого ребра (v, w) графа G существует подмножество Xi, содержащее и v, и w. То есть вершины смежны в графе если только соответствующие поддеревья имеют общую вершину в дереве T.

Ширина разложения дерева — это размер его наибольшего множества Xi минус единица (таким образом у деревьев ширина древесного разложения 1).

Древесная ширина tw(G) графа G — это минимальная ширина всех возможных разложений графа G. В этом определении из размера множества вычитается единица чтобы древесная ширина дерева была равна единице.

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

Древесную ширину можно описать также в терминах убежищ, функций, описывающих стратегии уклонения для некоторых игр преследования на графе. Граф G имеет древесную ширину k в том и только в том случае, когда в нём есть убежище порядка k + 1, но нет убежища с большим порядком. Здесь убежище порядка k + 1 — это функция β, которая отображает каждое множество X с максимум k вершинами в G в одну из связных компонент графа G \ X и для которой выполняется свойство монотонности

при .

Ежевика порядка четыре на 3×3 графе-решётке, существование которой показывает, что граф имеет древесную ширину как минимум  3

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

Любой полный граф Kn имеет древесную ширину n − 1. Это легче всего видеть, если использовать определение древесной ширины в терминах хордальных графов — полный граф уже хордален, и добавление рёбер не может уменьшить размер наибольшей клики.

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

Ограниченная древесная ширина

[править | править код]

Семейства графов деревьев ограниченной ширины

[править | править код]

Для любой фиксированной константы k графы с древесной шириной, не превосходящей k, называются частичными k-деревьями. Другие семейства графов с ограниченной древесной шириной включают кактусы, псевдолеса, параллельно-последовательные графы, внешнепланарные графы, графы Халина и графы Аполлония[5]. Графы потока управления, появляющиеся при трансляции структурных программ, также имеют ограниченную древесную ширину, что позволяет эффективно выполнять некоторые задачи, такие как распределение регистров.[6]

Планарные графы не имеют ограниченной древесной ширины, поскольку n × n решётка — это планарный граф, имеющий древесную ширину в точности n. Таким образом, если F — это семейство минорно-замкнутых графов с ограниченной древесной шириной, оно не может включать всех планарных графов. Обратно, если некоторый планарный граф не может быть минором графов в семействе F, то существует константа k, такая что все графы в F имеют древесную ширину не больше k. Таким образом, следующие три условия эквивалентны друг другу:[7]

  1. F — семейство минорно-замкнутых графов ограниченной древесной ширины;
  2. Один из конечного числа запретных миноров для F планарен;
  3. F является семейством минорно-замкнутых графов, включающим не планарные графы.

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

[править | править код]
Четыре запретных минора для древесной ширины 3

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

Для больших значений k число запрещённых миноров растёт по крайней мере как экспонента от k.[10] Однако известные верхние границы размера и числа запрещённых миноров много выше этой нижней границы.[11]

Вычисление ширины дерева

[править | править код]

Определение, имеет ли заданный граф G древесную ширину, не превосходящую k, является NP-полной задачей.[12] Однако если k фиксировано, графы с древесной шириной k могут быть найдены и соответствующее древесное разложение построено в линейное время.[13] Время выполнения алгоритма зависит от k экспоненциально.

На практике алгоритм Шойхета и Гайгера (Shoikhet, Geiger 1997) может найти древесную ширину графов, имеющих размер до 100 вершин и древесную ширину вплоть до 11, путём нахождения хордального дополнения этих графов с оптимальной древесной шириной.

Решение других задач на графах с малой шириной дерева

[править | править код]

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

Как пример, задача раскраски графа древесной ширины k может быть решена с помощью динамического программирования на древесном разложении графа. Для каждого множества Xi древесного разложения и каждого разбиения вершин Xi на цвета алгоритм определяет, допустима ли полученная раскраска и может ли она быть расширена на все производные вершины разложения путём комбинирования информации одинакового типа и запоминания в этих вершинах. Результирующий алгоритм находит оптимальную раскраску графа с n вершинами за время O(kk + O(1)n), что делает эту задачу параметрически сложной с фиксированным параметром[англ.].

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

[править | править код]

Путевая ширина

[править | править код]

Путевая ширина графа имеет очень похожее на древесную ширину определение через древесное разложение, но ограничивается только теми разложениями, в которых результирующее дерево является путём. Другим способом можно определить путевую ширину исходя из интервального графа подобно определению древесной ширины с помощью хордальных графов. Как следствие, путевая ширина графа как минимум не меньше его древесной ширины, но может быть больше только на логарифмический множитель.[5] Ещё один параметр, ширина полосы графа[англ.], имеет похожее определение, опирающееся на правильные интервальные графы, и значение параметра не меньше путевой ширины. Кроме того, есть глубина дерева, число, ограниченное для минорно-замкнутых графов тогда и только тогда, когда семейство не включает все графы-пути, и вырожденность, мера разреженности графа, не превосходящая древесную ширину.

Размер минора решётки

[править | править код]

Поскольку древесная ширина решётки n × n равна n, древесная ширина графа G всегда больше или равна размера наибольшей квадратной решётки-минора графа G. В обратном направлении, существует функция f, такая, что древесная ширина не превосходит f(r), где r — размер наибольшей квадратной решётки-минора. Однако известные границы f не малы: f должна быть не меньше Ω(r2 log r) и не больше 202r5.[16] Более строгие границы известны для ограниченных семейств графов, что даёт эффективные алгоритмы для многих задач оптимизации на этих семействах графов по теории двухмерности[англ.].[17] Теорема Халина о решётках[англ.] даёт аналог связи между древесной шириной и размером минора решётки для неограниченных графов.[18]

Диаметр и локальная древесная ширина

[править | править код]

Говорят, что семейство F графов имеет ограниченную локальную древесную ширину, если древесная ширина графов в семействе ограничена сверху[англ.] функцией от диаметра. Если любой минор члена семейства F также входит в F, то F имеет ограниченную локальную древесную ширину в том и только в том случае, когда один из запрещённых миноров Fверхушечный граф.[19] Первоначальное доказательство этого результата показывало, что древесная ширина в семействе графов без миноров, являющихся вершинными графами, растёт не быстрее удвоенной экспоненты от диаметра.[20] Позднее это было сведено просто к экспоненте [17] и, наконец, к линейной границе.[21] Ограниченная локальная древесная ширина тесно связана с алгоритмической теорией двухмерности[англ.][22], и любое свойство графа, которое можно определить в рамках логики первого порядка, может быть вычислено для графов из семейства, не содержащих миноров-вершинных графов, за только слегка суперлинейное время.[23]

Некоторые классы графов, не замкнутые относительно миноров, всё же имеют ограниченную локальную древесную ширину. В частности, это 1-планарные графы, то есть графы, которые можно нарисовать на плоскости с максимум одним пересечением одного ребра, и более общие графы, которые можно нарисовать на поверхности ограниченного рода с ограниченным числом пересечений рёбер. Как и в случае семейств минорно-замкнутых графов с ограниченной локальной древесной ширины, это свойство прокладывает путь к эффективным аппроксимационным алгоритмам для таких графов.[24]

Число Хадвигера и S-функции

[править | править код]

Халин (Halin 1976) определяет класс параметров графов, который он называет S-функциями, и этот класс включает ширину дерева. Эти функции имеют в качестве области определения графы, а в качестве области значений — целые числа, и они должны принимать значение нуль на графах без рёбер и должны быть монотонными относительно миноров, то есть увеличиваться на единицу при добавлении новой вершины, которая смежна всем предыдущим вершинам. Требуется также, чтобы значение функции от графа было равно большему из значений на двух подмножествах, пересечение которых является вершинным сепаратором и кликой одновременно. Множество всех таких функций образует полную решётку по отношению к операциям поэлементной минимизации и максимизации. Верхний элемент в этой решётке — древесная ширина, а нижний — число Хадвигера, размер максимального полного минора в заданном графе.

Примечания

[править | править код]
  • S. Arnborg, D. Corneil, A. Proskurowski. Complexity of finding embeddings in a k-tree // SIAM Journal on Matrix Analysis and Applications. — 1987. — Т. 8, вып. 2. — С. 277–284. — doi:10.1137/0608024..
  • Stefan Arnborg, Andrzej Proskurowski, Derek G. Corneil. Forbidden minors characterization of partial 3-trees // Discrete Mathematics. — 1990. — Т. 80, вып. 1. — С. 1–19. — doi:10.1016/0012-365X(90)90292-P..
  • S. Arnborg, A. Proskurowski. Linear time algorithms for NP-hard problems restricted to partial k-trees // Discrete Applied Mathematics. — 1989. — Т. 23, вып. 1. — С. 11–24. — doi:10.1016/0166-218X(89)90031-0..
  • M. W. Bern, E. L. Lawler, A. L. Wong. Linear-time computation of optimal subgraphs of decomposable graphs // Journal of Algorithms. — 1987. — Т. 8, вып. 2. — С. 216–235. — doi:10.1016/0196-6774(87)90039-3..
  • Umberto Bertelé, Francesco Brioschi. Nonserial Dynamic Programming. — Academic Press, 1972. — ISBN 0-12-093450-7..
  • Hans L. Bodlaender. Proc. 15th International Colloquium on Automata, Languages and Programming. — Springer-Verlag, 1988. — Т. 317. — С. 105–118. — doi:10.1007/3-540-19488-6_110..
  • Hans L. Bodlaender. A linear time algorithm for finding tree-decompositions of small treewidth // SIAM Journal on Computing. — 1996. — Т. 25, вып. 6. — С. 1305–1317. — doi:10.1137/S0097539793251219..
  • Hans L. Bodlaender. A partial k-arboretum of graphs with bounded treewidth // Theoretical Computer Science. — 1998. — Т. 209, вып. 1–2. — С. 1–45. — doi:10.1016/S0304-3975(97)00228-4..
  • Erik D. Demaine, Fedor V. Fomin, MohammadTaghi Hajiaghayi, Dimitrios M. Thilikos. Bidimensional parameters and local treewidth // SIAM Journal on Discrete Mathematics. — 2004. — Т. 18, вып. 3. — С. 501–511. — doi:10.1137/S0895480103433410..
  • Erik D. Demaine, MohammadTaghi Hajiaghayi. Diameter and treewidth in minor-closed graph families, revisited // Algorithmica. — 2004a. — Т. 40, вып. 3. — С. 211–215. — doi:10.1007/s00453-004-1106-1..
  • Erik D. Demaine, MohammadTaghi Hajiaghayi. Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms. — New York: ACM, 2004b. — С. 840–849..
  • Erik D. Demaine, Mohammad Taghi Hajiaghayi. Linearity of grid minors in treewidth with applications through bidimensionality // Combinatorica. — 2008. — Т. 28, вып. 1. — С. 19–36. — doi:10.1007/s00493-008-2140-4..
  • Reinhard Diestel. A short proof of Halin's grid theorem // Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg. — 2004. — Т. 74. — С. 237–242. — doi:10.1007/BF02941538..
  • Reinhard Diestel. Graph Theory // 3rd. — Springer, 2005. — ISBN 3-540-26182-6..
  • D. Eppstein. Diameter and treewidth in minor-closed graph families // Algorithmica. — 2000. — Т. 27, вып. 3-4. — С. 275–291. — doi:10.1007/s004530010020..
  • Markus Frick, Martin Grohe. Deciding first-order properties of locally tree-decomposable structures // Journal of the ACM. — 2001. — Т. 48, вып. 6. — С. 1184–1206. — doi:10.1145/504794.504798..
  • Alexander Grigoriev, Hans L. Bodlaender. Algorithms for graphs embeddable with few crossings per edge // Algorithmica. — 2007. — Т. 49, вып. 1. — С. 1–11. — doi:10.1007/s00453-007-0010-x..
  • Rudolf Halin. S-functions for graphs // Journal of Geometry. — 1976. — Т. 8. — С. 171–186. — doi:10.1007/BF01917434..
  • Jens Lagergren. Graph structure theory (Seattle, WA, 1991). — Providence, RI: American Mathematical Society, 1993. — Т. 147. — С. 601–621. — doi:10.1090/conm/147/01202..
  • Siddharthan Ramachandramurthi. The structure and number of obstructions to treewidth // SIAM Journal on Discrete Mathematics. — 1997. — Т. 10, вып. 1. — С. 146–157. — doi:10.1137/S0895480195280010..
  • Neil Robertson, Paul D. Seymour. Graph minors III: Planar tree-width // Journal of Combinatorial Theory, Series B. — 1984. — Т. 36, вып. 1. — С. 49–64. — doi:10.1016/0095-8956(84)90013-3..
  • Neil Robertson, Paul D. Seymour. Graph minors V: Excluding a planar graph // Journal of Combinatorial Theory, Series B. — 1986. — Т. 41, вып. 1. — С. 92–114. — doi:10.1016/0095-8956(86)90030-4..
  • Neil Robertson, Paul Seymour, Robin Thomas. Quickly excluding a planar graph // Journal of Combinatorial Theory. — 1994. — Т. 62, вып. 2. — С. 323–348. — doi:10.1006/jctb.1994.1073..
  • A. Satyanarayana, L. Tung. A characterization of partial 3-trees // Networks. — 1990. — Т. 20, вып. 3. — С. 299–322. — doi:10.1002/net.3230200304..
  • Paul D. Seymour, Robin Thomas. Graph Searching and a Min-Max Theorem for Tree-Width. // Journal of Combinatorial Theory, Series B. — 1993. — Т. 58, вып. 1. — С. 22–33. — doi:10.1006/jctb.1993.1027..
  • Kirill Shoikhet, Dan Geiger. Proc. AAAI '97. — 1997. — С. 185–190..
  • Mikkel Thorup. All structured programs have small tree width and good register allocation // Information and Computation. — 1998. — Т. 142, вып. 2. — С. 159–181. — doi:10.1006/inco.1997.2697..