Частичное k -дерево
В теории графов частичное , либо как k -дерево — это тип графа, определяемый либо как подграф k -дерева граф с шириной дерева не более k . [1] Многие NP-трудные комбинаторные задачи на графах разрешимы за полиномиальное время, если ограничиться частичными k -деревьями и ограниченными значениями k .
Миноры графа
[ редактировать ]
Для любой фиксированной константы k частичные k -деревья замкнуты относительно операции миноров графа , и поэтому по теореме Робертсона-Сеймура это семейство можно охарактеризовать в терминах конечного набора запрещенных миноров . Частичные 1-деревья — это в точности леса , а их единственный запрещенный минор — треугольник.Для частичных 2-деревьев единственный запрещенный минор представляет собой полный граф с четырьмя вершинами. Однако количество запрещенных миноров увеличивается при больших значениях k . Для частичных 3-деревьев существует четыре запрещенных минора: полный граф с пятью вершинами, октаэдрический граф с шестью вершинами, восьмивершинный граф Вагнера и пятиугольная призма с десятью вершинами. [2]
Динамическое программирование
[ редактировать ]Многие алгоритмические задачи, которые являются NP-полными для произвольных графов, могут быть эффективно решены для частичных k -деревьев с помощью динамического программирования с использованием древовидного разложения этих графов. [3]
Родственные семейства графов
[ редактировать ]Если семейство графов имеет ограниченную ширину дерева , то оно является подсемейством частичных k -деревьев, где k — граница ширины дерева.Семейства графов с этим свойством включают графы-кактусы , псевдолеса , последовательно-параллельные графы , внешнепланарные графы , графы Халина и аполлоновы сети . [2] Например, последовательно-параллельные графы являются подсемейством частичных 2-деревьев, и, более строго, граф является частичным 2-деревом тогда и только тогда, когда каждый из его двусвязных компонентов является последовательно-параллельным.
возникающие Графы потока управления, при компиляции структурированных программ определенные задачи, такие как распределение регистров . , также имеют ограниченную ширину дерева, что позволяет эффективно выполнять на них [4]
Примечания
[ редактировать ]Ссылки
[ редактировать ]- Арнборг, С.; Проскуровски, А. (1989), «Алгоритмы с линейным временем для NP-трудных задач, ограниченных частичными k- деревьями», Discrete Applied Mathematics , 23 (1): 11–24, doi : 10.1016/0166-218X(89)90031- 0 .
- Берн, МВт; Лоулер, Эл . ; Вонг, AL (1987), «Вычисление оптимальных подграфов разложимых графов в линейном времени», Journal of Algorithms , 8 (2): 216–235, doi : 10.1016/0196-6774(87)90039-3 .
- Бодлендер, Ханс Л. (1988), «Динамическое программирование на графах с ограниченной шириной дерева», Proc. 15-й Международный коллоквиум по автоматам, языкам и программированию , Конспекты лекций по информатике, том. 317, Springer-Verlag, стр. 105–118, doi : 10.1007/3-540-19488-6_110 , hdl : 1874/16258 , ISBN 978-3-540-19488-0 .
- Бодлендер, Ханс Л. (1998), «Частичный k -дендрарий графов с ограниченной шириной дерева», Theoretical Computer Science , 209 (1–2): 1–45, doi : 10.1016/S0304-3975(97)00228-4 , HDL : 1874/18312 .
- Торуп, Миккель (1998), «Все структурированные программы имеют небольшую ширину дерева и хорошее распределение регистров», Information and Computation , 142 (2): 159–181, doi : 10.1006/inco.1997.2697 .