Частичное k-дерево — это вид графа, либо подграф k-дерева, либо граф с древесной шириной, не превосходящей k. Много комбинаторных NP-трудных задач на графах решаются за полиномиальное время, если ограничиться частичными k-деревьями c некоторым ограниченным значением k.
Миноры графов
Для любой фиксированной константы k частичные k деревья замкнуты относительно операции взятия миноров графов, а потому по теореме Робертсона – Сеймура, такое семейство графов может быть описано конечным набором запрещённых миноров. Частичные 1-деревья — это в точности леса и их единственным запрещённым минором является треугольник. Для частичных 2-деревьев единственным запрещённым минором является полный граф с четырьмя вершинами. Однако при возрастании значения k далее число запрещённых миноров растёт. Для частичных 3-деревьев имеется четыре запрещённых минора — полный граф с пятью вершинами, октаэдральный граф с шестью вершинами, Граф Вагнера с восемью вершинами и граф пятигольной призмы с десятью вершинами[1].
Динамическое программирование
Много алгоритмических задач, NP-полных для произвольных графов, могут быть эффективно решены для частичных k-деревьев с помощью динамического программирования, если использовать древесную декомпозицию этих графов[2][3][4].
Связанные семейства графов
Если семейство графов имеет древесную ширину, ограниченную числом k, то оно является подсемейством частичных k-деревьев. Семейства графов с этим свойством включают кактусы, псевдолеса, параллельно-последовательные графы, внешнепланарные графы, графы Халина и графы Аполлония[1]. Например, параллельно-последовательные графы являются подсемейством частичных 2-деревьев. Более строго, граф является частичным 2-деревом тогда и только тогда, когда любой его шарнир является параллельно-последовательным.
Графы потока управления, возникающие при трансляции структурированных программ также имеют ограниченную древесную ширину, что позволяет некоторые задачи, такие как распределение регистров, выполнять эффективно[5].
Примечания
Литература
- 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..
- Hans L. Bodlaender. Proc. 15th International Colloquium on Automata, Languages and Programming. — Springer-Verlag, 1988. — Т. 317. — С. 105–118. — (Lecture Notes in Computer Science). — doi:10.1007/3-540-19488-6_110.
- 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..
- 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..
Эта страница в последний раз была отредактирована 10 августа 2023 в 06:13.
Обычно почти сразу, изредка в течении часа.