4551
правка
Древесная ширина графа: различия между версиями
Материал из WEGA
нет описания правки
KEV (обсуждение | вклад) Нет описания правки |
Irina (обсуждение | вклад) Нет описания правки |
||
| Строка 20: | Строка 20: | ||
Графы с древесной шириной <math>k</math> известны также как частичные [[k-Дерево|<math>k</math>-деревья]]. | Графы с древесной шириной <math>k</math> известны также как частичные [[k-Дерево|<math>k</math>-деревья]]. | ||
---- | |||
== Ключевые слова и синонимы == | |||
Частичное k-дерево; размерность; k-разложимые графы | |||
== Постановка задачи == | |||
Древесная ширина графа определяется в терминах древесной декомпозиции. Древесная декомпозиция графа G = (V, E) состоит из подмножеств V, называемых контейнерами, и дерева T, такого, что | |||
• Для всех {v, w} 2 E существует i 2 I, такое, что v, w 2 Xi. | |||
• Для всех v 2 V множество fi 2 Ijv 2 Xig порождает связное поддерево T. | |||
Древесная ширина графа, рис. 1. Граф и его древесная декомпозиция ширины 2 | |||
Ширина древесной декомпозиции равна maxi2I jX | — 1, а древесная ширина графа G равна минимальной ширине древесной декомпозиции G. | |||
Альтернативное определение дается в терминах хордальных графов. Граф G = (V, E) является хордальным в том и столько том случае, если любой цикл длины не менее 4 содержит хорду, т.е. дугу между двумя непоследовательными вершинами цикла. Древесная ширина графа G не превышает значения k в том и только том случае, если G является подграфом хордального графа H, имеющего максимальную клику размером не более k. | |||
Также можно дать еще одно определение в терминах упорядочения вершин. Пусть я – перестановка (в данном контексте называемая схемой исключения) вершин G = (V, E). Повторить следующий шаг для i = 1, ..., : : ; j Vj: взять вершину ж (i), превратить множество ее соседей в клику, а затем исключить v. Ширина ж равна максимуму по всем вершинам той же степени после ее исключения. Древесная ширина G равна минимальной ширине по всем схемам исключения. | |||
Входными данными задачи нахождения древесной ширины являются неориентированный граф G = (V, E), предположительно представленный в виде списка смежности, и целое положительное число k < |V|. Необходимо определить, верно ли, что древесная ширина графа G не превышает k, и в случае положительного ответа предложить древесную декомпозицию G с шириной не более k. | |||
== Основные результаты == | |||
Теорема 1 (Арнборг и др. [1]). Пусть даны граф G и целое число k. Задача определения того факта, что древесная ширина графа G не превышает k, является недетерминированной и имеет полиномиальное время выполнения (является NP-полной). | |||
Во многих вариантах применения древесной ширины и древесной декомпозиции графа исключительно важен случай, когда k предполагается фиксированной константой. Арнборг и др. [1] в 1987 году предложили алгоритм решения этой задачи за время O(nk+2). Было разработано несколько более быстрых алгоритмов для решения задачи при фиксированном значении k; обзор этих алгоритмов см, например, в [6]. | |||
Теорема 2 (Бодлендер [4]). Для каждого фиксированного значения k существует алгоритм, который для заданного графа G = (V, E) и целочисленного k может определить, верно ли, что древесная ширина G не превышает k, и в случае положительного ответа предложить древесную декомпозицию G с шириной не более k за время O(n). | |||
Теорема 2 имеет только теоретическую значимость: на практике этот алгоритм работает слишком медленно из-за большого константного коэффициента, скрытого в O-нотации. В случае древесной ширины, равной 1, задача эквивалентна задаче распознавания деревьев. Для случаев древесной ширины 2 и 3 были предложены эффективные алгоритмы, основанные на небольшом множестве правил редукции [2]. | |||
Для поиска древесной ширины часто используются две эвристики – минимального заполнения и минимальной степени. При применении эвристики минимальной степени выбирается вершина v с минимальной степенью. Граф G0 строится в результате превращения окрестности вершины v в клику и последующего удаления вершины v и инцидентных ей дуг. Хордальный суперграф H0 графа G0 вычисляется рекурсивным образом при помощи эвристики. Затем строится хордальный суперграф H графа G в результате добавления вершины v и инцидентных ей дуг из G в H0. Эвристика минимального заполнения работает сходным образом, однако в данном случае выбирается такая вершина v, чтобы количество ребер, добавляемых для превращения ее окрестности в клику, было минимально возможным. | |||
Теорема 3 (Фомин и др. [9]). Существует алгоритм, который для данного графа G = (V, E) определяет его древесную ширину и находит его древесную декомпозицию минимальной ширины за время O(1:8899n). | |||
Бушитте и Тодинка [8] показали, что древесная ширина может быть вычислена за полиномиальное время для графов, имеющих полиномиальное число минимальных сепараторов. На этой основе были разработаны алгоритмы с полиномиальным временем выполнения для нескольких классов графов – таких как перестановочные графы или слабо триангулированные графы. | |||
== Применение == | |||
Один из основных способов применения понятий древесной ширины и древесной декомпозиции заключается в следующем: многие задачи, трудноразрешимые (например, NP-полные) в случае произвольных графов, становятся разрешимыми за полиномиальное или линейное время в случае графов с ограниченной древесной шириной. К числу задач, для которых может быть применена эта техника, относятся многие классические графовые и сетевые задачи – такие как нахождение гамильтонова контура, дерева Штейнера, вершинного покрытия, независимого множества и раскраски графа – однако она может применяться и к множеству других задач. Она также используется алгоритмом, разработанным Лауритценом и Шпигельхальтером [11], для решения задачи логического вывода на вероятностных сетях (байесовых или «сетях доверия»). Подобные алгоритмы обычно имеют следующий вид. Вначале вычисляется древесная декомпозиция ограниченной ширины, а затем выполняется динамический алгоритм, использующий эту древесную декомпозицию. Нередко время выполнения динамического алгоритма оказывается экспоненциальным относительно ширины используемой древесной декомпозиции, в силу чего ее желательно выбирать насколько возможно малой. | |||
Также известны общие характеристики классов задач, разрешимых за линейное время на графах с ограниченной древесной шириной. Наиболее важным является класс задач, которые можно сформулировать в терминах монадической логики второго порядка и ее расширений. | |||
Древесная ширина использовалась в контексте нескольких приложений или теоретических исследований, включая теорию миноров графов, базы данных, удовлетворение ограничений, распределение частот, компиляторную оптимизацию и электрические сети. | |||
== Открытые вопросы == | |||
Существуют алгоритмы нахождения древесной ширины с полиномиальным временем выполнения, гарантирующие нахождение ширины O(k log k) для графов с древесной шириной k, однако остается открытым вопрос, существует ли алгоритм аппроксимации для нахождения древесной ширины за полиномиальное время с постоянным качественным коэффициентом. Еще один давний вопрос заключается в том, существует ли алгоритм вычисления древесной ширины с полиномиальным временем выполнения для планарных графов. | |||
Также не решена задача разработки алгоритма для случая, когда граница древесной ширины графа k фиксирована – такого, чтобы время выполнения алгоритма как функция от n было полиномиальным, а как функция от k было значительно лучше, чем у алгоритма из теоремы 2. | |||
Основание степени для экспоненциального времени выполнения алгоритма из теоремы 3, вероятно, может быть улучшено. | |||
== Экспериментальные результаты == | |||
Были предложены и экспериментально протестированы различные алгоритмы вычисления древесной ширины (эвристики нахождения верхней границы, эвристики нахождения нижней границы, точные алгоритмы и методы предварительной обработки). Обзор результатов многих подобных проверок приведен в работе [7]. Вариант алгоритма Арнборга и др. [1] внедрили Шойхет и Гейгер [15]. Рориг [14] провел экспериментальную оценку алгоритма Бодлендера с линейным временем выполнения [4] и установил, что он оказывается непрактичным даже для малых значений k. Часто используются эвристики минимальной степени и минимального заполнения [10]. | |||
== Наборы данных == | |||
Набор тестовых графов и результаты применения многих алгоритмов на этих графах можно найти в библиотеке TreewidthLIB [16]. | |||
== См. также == | |||
* ''[[Путевая ширина графа]] | |||
== Литература == | |||
1. Arnborg, S., Corneil, D.G., Proskurowski, A.: Complexity of finding embeddings in a k-tree. SIAM J. Algebr. Discret. Methods 8, 277-284(1987) | |||
2. Arnborg, S., Proskurowski, A.: Characterization and recognition of partial 3-trees. SIAM J. Algebr. Discret. Methods 7, 305-314 (1986) | |||
3. Bodlaender, H.L.: A tourist guide through treewidth. Acta Cybernetica 11,1-23 (1993) | |||
4. Bodlaender, H.L.: A linear time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput. 25, 1305-1317(1996) | |||
5. Bodlaender, H.L.: A partial k-arboretum of graphs with bounded treewidth. Theor. Comp. Sci. 209,1-45 (1998) | |||
6. Bodlaender, H.L.: Discovering treewidth. In: P. Vojtas, M. Bielikova, B. Charron-Bost (eds.) Proceedings 31st Conference on Current Trends in Theory and Practive of Computer Science, SOFSEM 2005. Lecture Notes in Computer Science, vol. 3381, pp. 1-16. Springer, Berlin (2005) | |||
7. Bodlaender, H.L.: Treewidth: Characterizations, applications, and computations. In: Fomin, F.V. (ed.) Proceedings 32nd International Workshop on Graph-Theoretic Concepts in Computer Science WG'06. Lecture Notes in Computer Science, vol. 4271, pp. 1-14. Springer, Berlin (2006) | |||
8. Bouchitte, V., Todinca, I.: Listing all potential maximal cliques of a graph. Theor. Comput. Sci. 276,17-32 (2002) | |||
9. Fomin, F.V., Kratsch, D., Todinca, I., Villanger, I.: Exact (exponential) algorithms for treewidth and minimum fill-in (2006). To appear in SIAM Journal of Computing, Preliminary version appeared in ICALP 2004 | |||
10. Koster, A.M.C.A., Bodlaender, H.L., van Hoesel, S.P.M.: Treewidth: Computational experiments. In: Broersma, H., Faigle, U., Hurink, J., Pickl, S. (eds.) Electronic Notes in Discrete Mathematics, vol. 8, pp. 54-57. Elsevier, Amsterdam (2001) | |||
11. Lauritzen, S.J., Spiegelhalter, D.J.: Local computations with probabilities on graphical structures and their application to expert systems. J. Royal Stat. Soc. Ser. B (Methodological) 50, 157-224(1988) | |||
12. Reed, B.A.: Tree width and tangles, a new measure of connectivity and some applications, LMS Lecture Note Series, vol. 241, pp. 87-162. Cambridge University Press, Cambridge (1997) | |||
13. Reed, B.A.: Algorithmic aspects of tree width, pp. 85-107. CMS Books Math. Ouvrages Math. SMC, 11. Springer, New York (2003) | |||
14. Rohrig, H.: Tree decomposition: A feasibility study. Master's thesis, Max-Planck-Institut fur Informatik, SaarbrCicken, Germany (1998) | |||
15. Shoikhet, K., Geiger, D.: A practical algorithm for finding optimal triangulations. In: Proc. National Conference on Artificial Intelligence (AAAI '97), pp. 185-190. Morgan Kaufmann, San Fransisco(1997) | |||
16. Bodlaender, H.L.: Treewidthlib. http://www.cs.uu.nl/people/hansb/treewidthlib (2004) | |||
==Литература== | ==Литература== | ||
* Workshop. Herrsching, 1994 // Lect. Notes Comp. Sci., 1995, vol. 903. | * Workshop. Herrsching, 1994 // Lect. Notes Comp. Sci., 1995, vol. 903. | ||
