close

Вход

Забыли?

вход по аккаунту

?

Программирование задач на графах ограниченной древовидной ширины.

код для вставкиСкачать
Программные продукты и системы
тическое значение кластера определялось по наибольшей подгруппе схожих элементов, и уже относительно их делалось предположение о верном
или неверном распределении оставшихся.
Мерой качества служила аккуратность кластеризации, вычисляемая по формуле
.
Качество обобщающей кластеризации. Для
оценки качества обобщающей кластеризации использовался модифицированный индекс Девиса–
Болдуина, перенесенный в пространство схожести
[3]. Эта метрика качества достаточно легко вычисляется и показывает хорошие результаты при
оценках обобщающей кластеризации.
Рассмотрим попарную меру схожести
между элементами и .
Используем
, где N – количество кластерных структур для создания обобщенной структуры кластеров;
1, если ui и u j принадлежат к одному

l
voteij   и тому же кластеру в структуре Cl ,
 0 в противном случае.

Центральный элемент
обобщенного кластера
– это элемент с максимальной средней
схожестью в кластере:
.
Индекс Девиса–Болдуина в пространстве схожести определяется следующим образом:
,
№ 4, 2011 г.
где
– количество кластеров в обобщенной кластерной структуре;
и
– средняя попарная схожесть в структурах
и
соответственно. Малые значения
означают, что сходство между элементами из разных кластеров
(
) мало, а между элементами, принадлежащими одному и тому же кластеру (
), велико. Разбиение, минимизирующее
, является оптимальным.
Подытоживая, отметим, что в ходе проекта по
анализу социальных сетей [4] была разработана
методология двухэтапной кластеризации пользователей. Установлено, что обобщающая кластеризация позволяет выделять более сложные кластерные структуры, чем кластеризация по отдельным
характеристикам пользователей, что увеличивает
значимость кластеризации для аналитиков сети.
К недостаткам данного метода следует отнести
длительное время работы, что в данном случае является менее значимым по сравнению с эффективностью техники.
Литература
1. Ester M., Kriegel H.-p., Jorg S., and Xu X. Portland. A
density-based algorithm for discovering clusters in large spatial
databases with noise // Conf. on Knowledge Discovery in
Databases and Data Mining, 1996.
2. Duarte F.J. [et al]. On Consensus Clustering Validation.
IAPR Int. Conf. on Structural, syntactic and statistical pattern
recognition, 2010.
3. Reich M. [et al]. GenePattern 2.0. Nature Genetics 38. 2006.
№ 5, pp. 500–501.
4. Simoes J. [et al]. Exploring Influence and Interests among
Users within Social Networks. Computational Social Networks:
Springer-Verlag, 2011.
УДК 519.178+004.021
ПРОГРАММИРОВАНИЕ ЗАДАЧ НА ГРАФАХ
ОГРАНИЧЕННОЙ ДРЕВОВИДНОЙ ШИРИНЫ
В.В. Быкова, к.т.н.
(Институт математики Сибирского федерального университета, г. Красноярск,
bykvalen@mail.ru)
Рассматривается современный подход к разработке эффективных алгоритмов решения оптимизационных задач
на графах ограниченной древовидной ширины. Подход основан на динамическом программировании с использованием дерева декомпозиции графа. В рамках этого подхода предлагается точный алгоритм решения задачи о вершинном покрытии. Применяется преобразование дерева декомпозиции, позволяющее сократить размер таблиц динамического программирования. Алгоритм излагается с помощью языка реляционной алгебры. Время выполнения
алгоритма линейно зависит от числа вершин и экспоненциально от древовидной ширины исходного графа.
Ключевые слова: алгоритмы на графах, дерево декомпозиции, динамическое программирование, вершинное покрытие, реляционная алгебра.
Многие проблемы реальной жизни, связанные
с дискретными объектами, могут быть смоделированы как оптимизационные задачи на графах. К
сожалению, подавляющее большинство оптимиза-
ционных задач на графах являются NP-трудными
и для них не найдено эффективных (полиномиальных по времени) алгоритмов решения. Возможный путь преодоления этой проблемы  выяв101
Программные продукты и системы
ление классов графов, для которых NP-трудные
задачи эффективно разрешимы. Представительный класс подобных графов образуют частичные
k-деревья  графы, обладающие ограниченной
древовидной шириной [1]. В него входят, например, ациклические, хордальные, последовательнопараллельные графы, графы Халина.
Другая возможность преодоления высокой вычислительной сложности NP-трудных графовых
задач  это организация процедуры поиска оптимального решения по принципу «разделяй и властвуй». Для частичных k-деревьев, когда k  положительная целая константа, этот принцип
эффективно реализуется методом динамического
программирования на основе дерева декомпозиции графа. Сочетание декомпозиционного метода
с декомпозиционным представлением входного
графа составляет суть одного из современных
подходов разработки эффективных алгоритмов
решения большого класса важных практических
задач, выражаемых на языке теории графов и комбинаторной оптимизации [1].
В статье кратко излагаются основные идеи
данного подхода. Предлагается алгоритм решения
задачи о вершинном покрытии для графов ограниченной древовидной ширины. В алгоритме применяется новый алгоритмический прием, направленный на практическое снижение потребления
времени и памяти подобных алгоритмов.
Дерево декомпозиции и древовидная ширина
графа. Везде далее G=(V, E)  неориентированный конечный связный граф без петель и кратных
ребер, n=|V| и m=|E|. Пусть G(V)  подграф графа
G=(V, E), индуцированный множеством VV. Говорят, что множество вершин VV образует сепаратор графа G=(V, E), если граф G(V \ V) имеет
более одной компоненты связности. Множество
вершин VV называется кликой графа G, если
G(V) – полный граф.
Древовидная ширина графа G=(V, E) определяется через дерево декомпозиции, которое представляет собой пару (M, T), устанавливающую
разбиение множества вершин и множества ребер
графа G, где M={Xi | i  I}  семейство подмножеств множества V, называемых мешками, а
T=(I, W)  дерево, узлам которого сопоставлены
эти мешки. Данное разбиение должно отвечать
следующим требованиям [1]:
1) iI Xi=V;
2) для всякого ребра графа G обязательно имеется хотя бы один мешок, содержащий обе вершины этого ребра;
3) для любой вершины vV графа G множество узлов {iI | vXi} индуцирует связный подграф, являющийся поддеревом дерева T.
Вершины дерева T принято называть узлами,
чтобы избежать путаницы с вершинами графа G.
Ширина дерева декомпозиции (M, T) определяет102
№ 4, 2011 г.
ся величиной max {(|Xi|1) | iI}. Древовидная
ширина (treewidth) графа G, обозначаемая tw(G),
есть наименьшая ширина всех допустимых его деревьев декомпозиции. Когда граф G не является
связным, считается, что tw(G)=0. Если G  полный n-вершинный граф, то tw(G)=n1. Таким образом, обязательно 0tw(G)n–1.
Дерево декомпозиции графа G  это специальная конструкция, которая не только определяет
древовидную ширину графа, но и представляет его
структуру с точностью до клик и сепараторов:
всякая клика графа G всегда целиком вложена в
отдельный мешок дерева декомпозиции (M, T); в
фундаментальном дереве декомпозиции пересечение любых двух мешков Xi и Xj, отвечающих двум
смежным узлам i и j дерева T, неизменно образует
сепаратор графа G. Дерево декомпозиции (M, T)
без вложенных и кратных мешков имеет O(n) узлов и называется фундаментальным. Оно неизбыточно с точки зрения представления клик и сепараторов графа G. Важно отметить, что всякое дерево декомпозиции (M, T) графа G=(V, E) есть не
что иное, как дерево соединений ациклического
гиперграфа H=(V, M), ребрами которого выступают мешки Xi, iI. Это обстоятельство дает возможность для любой пары (M, T) проверить справедливость указанных свойств 13 дерева декомпозиции с помощью полиномиального теста на
ацикличность гиперграфа [2, 3].
Древовидная ширина отражает меру древовидности графа G: чем меньше tw(G), тем ближе граф
G к дереву и тем меньше у него по мощности клики и сепараторы. Так, все обычные n-вершинные
деревья (n2) имеют единичную древовидную
ширину, размер всякой клики такого дерева равен
2, а размер каждого сепаратора равен 1. Граф G
обладает ограниченной древовидной шириной, если tw(G)k и k  положительная целая константа,
не зависящая от n. Например, если G  последовательно-параллельный граф, то tw(G)2, а для всякого графа Халина постоянно tw(G)=3. Ограниченная древовидная ширина  это наследственное
свойство графа: если tw(G)k, то tw(G)k для
любого подграфа G=G(A), AV. Примечательно,
что многим приложениям теории графов свойственны графы небольшой древовидной ширины.
Например, графы зависимостей между синтаксическими конструкциями естественного языка и
графы программ, написанных на языках C++ и
Паскаль, имеют древовидную ширину не более 6,
а для графов большинства химических соединений характерна ширина не более 4 [1].
Динамическое программирование по дереву
декомпозиции. Как известно, динамическое программирование  это декомпозиционный метод
решения оптимизационных задач. Применение
данного метода к конкретной задаче предполагает
прежде всего выделение семейства подзадач и оп-
Программные продукты и системы
ределение рекуррентной процедуры, связывающей
оптимальные решения подзадач. В графовых задачах для этих целей весьма полезно корневое дерево декомпозиции входного графа.
Рассмотрим задачу П, которую требуется решить для графа G=(V, E) с tw(G)k, где k  положительная целая константа. Пусть для G известно
корневое
дерево
декомпозиции
(M, T),
M={Xi | iI} и T=(I, W), ширины k и с узлом r в
роли корня. Семейство подзадач в данном случае
можно задать следующим образом. Определим для
всякого узла iI множество вершин
Yi={vXj | j=i или j  потомок для i в T}. (1)
Множество Yi индуцирует в G подграф
Gi=G(Yi), а в T  поддерево с корневым узлом i.
Примечательно, что Yr=V и Gr=G. Тогда в качестве отдельной подзадачи Пi можно рассматривать
решение задачи П для Gi, iI.
Понятно, что для каждой конкретной графовой
задачи специфичны характеристики решений и
рекуррентные процедуры, связывающие значения
характеристик решений подзадач. Между тем сценарий действия алгоритмов, основанных на динамическом программировании по дереву декомпозиции, общий. Работа подобных алгоритмов
включает в себя два этапа:
1) для заданного графа G=(V, E) строится дерево декомпозиции ширины k, которое затем преобразуется в корневое дерево декомпозиции
(M, T) той же ширины;
2) решается задача П с помощью корневого
дерева декомпозиции (M, T).
В данной статье рассматривается только второй этап. Подходы к реализации первого этапа
можно найти, например, в работах [1, 3, 4]. Второй этап, в свою очередь, состоит из двух фаз:
 обход всех узлов дерева T снизу вверх от
листьев к корню r  вычисление необходимой информации и нахождение значений характеристик
подзадач;
 обход всех узлов дерева T сверху вниз от
корня r к листьям для конструирования оптимального решения задачи П для исходного графа G.
Вся нужная информация вычисляется и хранится в виде таблиц. Каждому узлу iI дерева T
соответствует таблица Ai, которая содержит информацию по задаче Пi. Метод динамического
программирования требует, чтобы эти таблицы
обладали следующими свойствами:
 для каждого узла iI решение задачи Пi
находится исключительно из таблицы Ai;
 для каждого листа iI дерева T таблица Ai
вычисляется непосредственно из G(Xi);
 для каждого внутреннего узла iI таблица
Ai создается из G(Xi) и таблиц, которые отвечают
прямым потомкам узла i в T.
Использование дерева декомпозиции способствует выполнению указанных выше свойств таб-
№ 4, 2011 г.
лиц, поскольку для каждого узла iI дерева T
справедливо высказывание: вершины графа Gi,
смежные с вершинами, находящимися вне Gi, обязательно содержатся в мешке Xi. Иными словами,
графы Gi=G(Yi) и G(V \ Yi) связаны между собой в
G только с помощью вершин из Xi. Заметим, что
таких вершин не более k+1. Следовательно, когда
необходимо от таблиц, созданных для потомков
внутреннего узла i, перейти к таблице Ai, то достаточно исследовать только вершины из Xi (вместо
Yi) и применять лишь таблицы прямых потомков
узла i.
Обход дерева T с O(n) узлами осуществим за
время O(n), где n=|V|. Поэтому для получения
эффективного алгоритма реализации двух фаз динамического программирования по дереву декомпозиции необходимо, чтобы каждая таблица Ai
вычислялась и обрабатывалась эффективно относительно n. Найти точное решение задачи Пi для
каждого узла i дерева T можно всегда полным перебором на основе таблицы Ai, в которой перечислены различные подмножества (как претенденты
на оптимальное решение) множества Xi, и таблиц
прямых потомков, если такие существуют. Предположим, что всякая вершина из Xi может находиться по отношению к возможному решению в q
состояниях. Например, в задаче о вершинном покрытии q=2 («принадлежит вершинному покрытию», «не принадлежит вершинному покрытию»),
а в задаче о доминирующем множестве q=3 («входит в доминирующее множество», «доминирует,
но не входит в доминирующее множество», «не
доминирует»). Тогда для узла i, являющегося листом в T, таблица Ai имеет размер O(k · qk), так как
|Xi|k+1, iI. Размер таблицы Ai для внутреннего
узла i с двумя прямыми потомками может достигать O(k · q2k). Ясно, что, чем больше арность дерева T (число прямых потомков узлов этого дерева), тем большего размера таблицы могут возникать в процессе вычислений. По этой причине
традиционно оперируют корневым бинарным деревом декомпозиции.
Если обработка одной строки каждой таблицы
Ai, iI, требует nO(1) времени, то время работы алгоритма, основанного на динамическом программировании по дереву декомпозиции, составляет
f(k) · nO(1). Здесь f(k)  функция, не зависящая от n
и содержащая экспоненциальные составляющие
вида O(qk), O(q2k), O(q3k) и т.п. Такие алгоритмы
называют FPT (Fixed-Parameter Tractable)-алгоритмами [5]. Они экспоненциальные лишь по
отношению к параметру k и полиномиальные относительно n. При фиксированном значении параметра FPT-алгоритмы теоретически эффективны по времени выполнения. Однако практически
эффективными они являются только при малых
значениях параметра. Это является главным препятствием практического применения FPT-алгоритмов, основанных на динамическом програм103
Программные продукты и системы
мировании по дереву декомпозиции. Поэтому
актуальны различные алгоритмические приемы,
направленные на предобработку входных данных
с целью снижения числа и размера таблиц динамического программирования. Таким приемом,
например, является приспособление дерева декомпозиции исходного графа к решаемой графовой задаче: снижение арности дерева до двух, определение различных типов узлов и т.п.
Важно отметить, что подобные приемы не дают дополнительных алгоритмических возможностей. Между тем их использование в ряде случаев
позволяет снизить потребности FPT-алгоритмов в
вычислительных ресурсах. Предлагается FPT-алгоритм решения задачи о вершинном покрытии с
шириной дерева декомпозиции графа в роли
параметра. В данном алгоритме применяется специальное преобразование заданного дерева декомпозиции (введение дополнительных узлов-сепараторов) и привлекается аппарат реляционной
алгебры (алгебры таблиц) [2].
Вычисление наименьшего вершинного покрытия. Подмножество VV образует вершинное покрытие графа G=(V, E), если каждое ребро
из E инцидентно хотя бы одной вершине из V.
Покрытие V называется наименьшим, если число
вершин в нем наименьшее среди всех покрытий
графа G. Число вершин в наименьшем покрытии
графа G называется числом покрытия этого графа
и далее обозначается через (G). В оптимизационной постановке задача о вершинном покрытии
графа формулируется следующим образом. Задан
граф G=(V, E). Требуется найти наименьшее вершинное покрытие графа G. Эта задача является
типичной NP-трудной задачей на графах, к которой сводятся многие подобные задачи. Применительно к графам ограниченной древовидной ширины будем полагать, что исходный граф G=(V, E)
задан вместе со своим деревом декомпозиции ширины k, где k  положительная целая константа.
Прежде чем приступить к решению задачи методом динамического программирования, предлагаем преобразовать заданное дерево декомпозиции
графа G следующим образом.
Шаг 1. Удалить из дерева декомпозиции кратные и вложенные мешки, то есть получить фундаментально дерево декомпозиции графа G.
Шаг 2. Выбрать произвольный узел rI в роли
корня и снизить арность дерева до двух. Последнее действие осуществить так. Если внутренний
узел iI обладает одним или двумя прямыми потомками, то ничего не делать. Если внутренний
узел iI имеет в качестве прямых потомков узлы
j1, …, jd, d3, то выполнить клонирование узла i в
узлы i1, …, id1 и приписать каждому из них мешок
Xi. Отношение подчиненности между узлами установить, как показано на рисунке 1.
104
№ 4, 2011 г.
Xi
i
...
j2
j1
Xi
jd  1
i1
Xi
j1
jd
i2
...
Xi
j2
id  1
jd1
jd
Рис. 1
Шаг 3. Для любых двух узлов i, jI, смежных
в T и имеющих мешки Xi и Xj соответственно, добавить промежуточный узел s и сопоставить ему
множество вершин S=XiXj (рис. 2). Заметим,
что S  сепаратор графа G.
Xi
i
Xi
Xj
j
Xs = Xi  Xj
Xj
i
s
j
Рис. 2
Таким образом, исходное дерево декомпозиции
пополнится O(n) узлами. Результирующее дерево
декомпозиции (M, T), M={Xi | iI}, T=(I, W), будет иметь O(n) узлов, ширину k и узел r в роли
корня. В нем возможны только четыре типа узлов:
 узел-лист  узел, у которого нет потомков;
 узел-сепаратор  узел s с одним прямым
потомком j; если i  родитель узла s, то Xs=Xi
Xj, XsXi, XsXj;
 узел-расширение  узел i с одним прямым
потомком s; в данном случае XsXi;
 узел-объединение  узел i с двумя прямыми
потомками l и j (здесь XlXjXi).
В качестве подзадачи рассмотрим решение задачи о вершинном покрытии для графа Gi=G(Yi),
где Yi  множество вершин, определенное по (1) и
отвечающее поддереву дерева T с корнем iI.
Пусть c(Z)  число вершин, образующих некоторое вершинное покрытие Z графа Gi. Данная величина является естественной характеристикой
покрытия и целевой функцией в задаче о вершинном покрытии.
Программные продукты и системы
При обходе дерева T снизу вверх и вычислении
таблиц Ai следует различать четыре возможные
ситуации, соответствующие четырем типам узлов.
Дадим описание этих ситуаций, используя язык
реляционной алгебры.
Ситуация 1: узел-лист i с мешком Xi. Задача
для графа G(Xi) решается полным перебором. Для
этого создается таблица Ai по следующим правилам. В таблице p+1 столбцов и 2p строк, где p=|Xi|,
отдельная строка для каждого из 2p различных
подмножеств ZXi. Состав вершин, входящих в Z,
представляется битовой шкалой b: b(v) = 1, если
vZ, и b(v)=0 в противном случае. Последний
столбец c(Z) содержит характеристику Z: c(Z)=|Z|,
если Z  вершинное покрытие для графа G(Xi),
иначе c(Z)=. Заметим, что |Z|= b(v), vXi.
Ситуация 2: узел-сепаратор s с одним прямым
потомком j. В данном случае XsXj. Пусть для узла j ранее уже была построена таблица Aj. Тогда
таблица As вычисляется по формуле
As=S(Aj),
(2)
где   реляционная операция проекции, которая
выбирает из таблицы Aj подмножество столбцов
S=Xs{c(Z)}. В полученной таблице As возможны
строки, совпадающие по индикаторам вершин из
Xs и имеющие разные значения целевой функции
c1(Z), c2(Z), …, ch(Z), h1. Поэтому для всех таких
строк полагается
c(Z)=min {c1(Z), c2(Z), …, ch(Z)}
(3)
и в As оставляется только одна из них. После этого
результирующая таблица As содержит только ту
информацию из Aj, которая необходима для согласования ее с таблицей Ai, где i  родитель узла s.
Ситуация 3: узел-расширение i с одним прямым потомком s, для которого XsXi. Пусть для
узла s ранее уже была создана таблица As. Вначале
формируется таблица Ai так, как будто бы узел i
является листом. Затем таблица Ai связывается с
таблицей As с помощью реляционной операции
естественного соединения (), и результат записывается в Ai:
Ai=AiAs.
(4)
Поскольку XsXi, при выполнении естественного соединения в таблице Ai появляется лишь
один дополнительный столбец со значениями c(Z)
из таблицы As. Пусть Ai.c(Z) и As.c(Z)  значения
характеристики для ZXi, включенные в результирующую таблицу Ai из исходных таблиц Ai и As
соответственно. В этих обозначениях формула пересчета значений c(Z) для Ai имеет вид
c(Z)=Ai.c(Z)+As.c(Z) b(v),
(5)
где суммирование берется по всем vXs.
Ситуация 4: узел-объединение i с двумя прямыми потомками l и j. Заметим, что в данном случае узлы l и j являются узлами-сепараторами и
XlXjXi. Пусть им соответствуют таблицы Al и
Aj. Аналогично ситуации 3 вначале формируется
таблица Ai так, как будто бы узел i является лис-
№ 4, 2011 г.
том. Далее по формулам (4), (5) таблица Ai связывается с таблицей Al, а затем полученная таблица
 с таблицей Aj. Таким образом, ситуация 4 сводится к двукратному повторению действий, определенных для ситуации 3.
Как только достигается корневой узел r и вычисляется таблица Ar, значение числа вершинного
покрытия графа G находится по формуле
(G)=min{c(Z) | ZXr}.
(6)
Для построения самого вершинного покрытия
следует выполнить спуск по T от корня к листьям.
Во всех четырех ситуациях размер формируемых таблиц составляет O(k ·2k), где k  ширина
заданного дерева декомпозиции исходного графа G. Эта оценка достигается за счет введения в
дерево декомпозиции узлов-сепараторов:
 для всякого узла-листа i таблица Ai имеет
размер O(k·2k), поскольку |Xi|k+1, iI;
 операция проекции, используемая в ситуации 2, не увеличивает размер таблицы;
 операция естественного соединения, применяемая в ситуации 3 для узла-расширения i с
прямым потомком s, дает таблицу размера
O(k·2k), поскольку XsXi. Между тем в общем
случае (для любого отношения вложенности между Xs и Xi) операция естественного соединения
двух таблиц размера O(k·2k) приводит к таблице
размера O(k·22k).
Как уже указывалось, обход дерева T всегда
можно реализовать за время O(n). Выполнение
проверки, является ли подмножество ZXi вершинным покрытием для графа G(Xi), также осуществимо за время O(n). Таким образом, время
работы алгоритма и потребность его в памяти сопоставимы с O(k·2k·n). Значит, чем меньше древовидная ширина графа G, тем меньше вычислительных ресурсов требуется для нахождения вершинного покрытия этого графа.
x
y
u
w
g
v
xyw
ywg
yu
gv
Рис. 3
5
y
4
yu
7
xyw
6
yw
3
ywg
g
2
gv
1
Рис. 4
105
Программные продукты и системы
Заметим, что в ситуации 4
A1
не важно, сколько прямых поg
v
c(Z)
томков имеет узел-объедине0
0

ние. Если их d2, то действия,
определенные для ситуации 3,
0
1
1
надо повторить d раз. Очевид1
0
1
но, что исключение шага 2 по
1
1
2
преобразованию исходного деа)
рева декомпозиции (снижение
арности дерева) может сущеA3
ственно сократить число узлов
y
w
g
c(Z)
в T и уменьшить практические
потребности алгоритма в вы0
0
0

числительных ресурсах. При
0
0
1
1
этом возможно усложнение
0
1
0

программной реализации алгоритма применительно к си0
1
1
2
туации 4.
1
0
0

Иллюстрация работы ал1
0
1
2
горитма. Пусть задан граф G
1
1
0
2
вместе с деревом декомпозиции ширины 2 (рис. 3). Дерево
1
1
1
3
декомпозиции графа G, полуд)
ченное после преобразований
(в данном случае только добавления узлов-сепараторов 2,
5, 6 и выделения узла 7 в роли корня), изображено
на рисунке 4. Найдем наименьшее вершинное покрытие графа G с помощью предложенного выше
алгоритма.
Начнем с узла 1. Это узел-лист. Узел 2 является
узлом-сепаратором и родителем для узла 1. Таблицы A1 и A2 отвечают данным узлам (рис. 5а и 5б).
Согласно формулам (2), (3), A2=g(A1). Аналогично узлам 4 и 5 соответствуют таблицы A4, A5 (рис.
5в и 5г) и A5= y (A4). Узел 3  это узел-объединение по отношению к узлам 2 и 5. Для него таблица
A3 (рис. 5д) содержит локальную информацию
для подграфа G(X3). Естественное соединение A3
с таблицей A2, а затем с таблицей A5 по формулам
(4) и (5) дает таблицу A3 (рис. 5е). Узел 6 – вновь
узел-сепаратор, для которого A6= yw (A3) (рис.
5ж). Корневой узел 7  это узел-расширение по
отношению к узлу 6. В соответствии с формулами
(4) и (5) таблица A7 имеет вид, представленный на
рисунке 5з. Таблица A7 отвечает корневому узлу.
Применение формулы (6) к A7 дает (G)=3.
Спуск по дереву декомпозиции от корня к листьям определяет следующие наименьшие вершинные покрытия графа G: {x, y, g}, {x, g, u}, {y,
w, g}, {y, w, v}. Заметим, что для исходного графа
допустимы деревья декомпозиции, отличные от
дерева, указанного на рисунке 3. Решение задачи о
вершинном покрытии на их основе приведет, возможно, к другим оптимальным решениям, хотя
неизменным будет значение (G)=3.
Предложенный алгоритм можно применять для
взвешенной версии задачи о вершинном покры106
№ 4, 2011 г.
A2
A5
A4
g
c(Z)
c(Z)
y
c(Z)
y
u
0
1
0
0

0
1
1
1
0
1
1
1
1
1
0
1
1
1
в)
2
б)
A3
г)
A6
A7
y
w
g
c(Z)
y
w
c(Z)
x
y
w c(Z)
0
0
0

0
0
2
0
0
0

0
0
1
2
0
1
3
0
0
1

0
1
0

1
0
2
0
1
0

0
1
1
3
1
1
3
0
1
1
3
1
0
0

1
0
0
3
1
0
1
2
1
0
1
4
1
1
0
3
1
1
0
3
1
1
1
3
1
1
1
4
е)
ж)
з)
Рис. 5
тии, а его идеи  для решения других подобных
задач: нахождения наибольшего независимого
множества вершин, поиска наибольшей клики,
отыскания наименьшего доминирующего множества графа. Использование языка реляционной алгебры в описании алгоритма неслучайно. Как видно из изложенного в работе процесса согласования
таблиц динамического программирования в задаче
о вершинном покрытии, этот процесс подобен
процессу реализации запроса к реляционной БД,
где в качестве исходных отношений выступают
таблицы, отвечающие узлам дерева декомпозиции,
как будто бы все они есть листья. Каждому такому
запросу свойственны свои формулы пересчета
характеристик решений. Реляционный взгляд на
процесс динамического программирования по дереву декомпозиции позволяет при разработке алгоритмов использовать такие свойства ациклических БД, как квазистягиваемость и существование
монотонных планов соединения отношений.
Литература
1. Bodlaender H.L. Discovering treewidth. In Proceedings of
the 31st Conference SOFSEM 2005, Springer-Verlag, Lecture
Notes in Computer Science 3381, 2005, pp. 116.
2. Мейер Д. Теория реляционных баз данных. М.: Мир,
1987.
3. Быкова В.В. Алгоритм построения дерева декомпозиции
гиперграфа на основе ацикличности // Программные продукты
и системы. 2011. № 1(93). С. 6469.
4. Быкова В.В. Рекуррентные методы вычисления древовидной ширины гиперграфа // Изв. Томского политех. ун-та.
2011. Т. 318. № 5. С. 510.
5. Быкова В.В. FPT-алгоритмы и их классификация на основе эластичности // Прикл. дискр. математика. 2011. № 2(12).
С. 4048.
Документ
Категория
Без категории
Просмотров
11
Размер файла
2 894 Кб
Теги
ширины, древовидных, задачи, программирование, ограниченной, графах
1/--страниц
Пожаловаться на содержимое документа