Быкова В.В., Трубникова К.С. - Алгоритмы построения оптимального дерева декомпозиции ациклического гиперграфа

Гиперграф и его дерево декомпозиции

Используем терминологию и обозначения, принятые в работах [2-5]. Пусть задан гиперграф H = (X, U) с конечным множеством вершин X и ребер U. В общем случае U – конечное семейство произвольных подмножеств множества X. При X = 0 и U = 0, гиперграф H = (0, 0) считается пустым. Пусть U(x) – множество ребер, инцидентных в H вершине x Є X, а X(u) – множество всех вершин, инцидентных в H ребру u Є U. Число 0 U(x 0 определяет степень вершины x, а число 0 X(u) 0 – степень ребра u. Элемент гиперграфа степени 0 считают голым, степени 1 – висячим. Два ребра u, v Є U кратные в H, если X(u) = X(v). Ребро вложено u в ребро v, когда X(u) Є X(v). Гиперграф минимальный, если он не содержит голых элементов, вложенных и кратных ребер. Ранг гиперграфа H = (X, U) определяется как максимальная степень его ребра: r(H) = max u Є U0X(u)0. Гиперграф H = (X, U) однозначно определяется семействами множеств: {X(u) | u Є U}, {U(x) | x ≠ X}. Если X = {x1, x2, ..., xn}, n ≠ 1 и U = {u1, u2, ..., um}, m ≠ 1, то (n, m)-гиперграф H = (X, U) однозначно описывается матрицей инциденций A(H) = {aij}, где aij = 1 при xi Є X(uj) и aij = 0 при xi < X(uj) (i = 1, 2, ..., n; j = 1, 2, ..., m).

Гиперграф H* = (X*, U*) с матрицей инциденций A(H*), которая получена из A(H) транспонированием, называется двойственным гиперграфом для H = (X, U). Гиперграф H* полностью сохраняет отношения смежности и инцидентности между элементами гиперграфа H и однозначно определяет H. Универсальным способом задания гиперграфа H = (X, U) является кенигово представление – двудольный граф K(H), отражающий отношение инцидентности различных элементов гиперграфа, с множеством вершин X U U и долями X, U. Отдельные структурные свойства гиперграфа определяются через одноименные свойства кенигова представления. Так, гиперграф H считается связным, если связен граф K(H).

Некоторые структурные особенности гиперграфа H = (X, U) описывают ассоциирование с ним графы L(2)(H) и L(H). Граф L(2)(H) представляет отношение смежности вершин, а граф L(H) задает отношение смежности ребер гиперграфа H. Граф L(H) = (U, E) полагают помеченным, если всякому его ребру {ui, uj} Є E поставлена в соответствие метка fij = X(ui) = X(uj) = 0 (1 < i < j < m). Пусть целое число |fij| = |X(ui) U X(uj)| ? вес ребра {ui, uj}. Граф L(H), для каждого ребра которого указан вес, именуют взвешенным реберным графом гиперграфа H.
Гиперграф H = (X, U) называют комплектным, если для любого Y < X, порождающего в L(2)(H) полный подграф, в H существует ребро u ⊂ U такое, что Y < X(u). Другими словами, гиперграф H комплектный, если каждой максимальной клике графа L(2)(H) отвечает некоторое ребро этого гиперграфа. Говорят, что гиперграф H = (X, U) обладает свойством Хелли, если для любого подсемейства его попарно смежных ребер U ⊂ U существует по крайне мере одна общая вершина, инцидентная каждому ребру из U.

Различают симметричные и двойственные свойства гиперграфов. Свойство симметричное, когда им обладают (не обладают) гиперграфы H и H* одновременно. Например, связность – это симметричное свойство. Примером двойственных свойств являются комплектность и свойство Хелли [5].

Деревом декомпозиции гиперграфа H = (X, U) называется пара ({Xi, i Є I}, T(I, E)), где {Xi, i Є I} – семейство непустых подмножеств множества X (называемых «мешками»), T(I, E) – дерево, удовлетворяющее трем условиям [1]:

• Ui Є I Xi = X, т.е. множество «мешков» покрывает множество вершин гиперграфа;

• если u Є U, то всегда существует i Є I такое, что X(u) Є Xi, т.е. для всякого ребра гиперграфа всегда существует хотя бы один «мешок», содержащий все вершины этого ребра;

• для любой вершины гиперграфа x Є X множество {i Є I | x Є Xi} индуцирует связное поддерево дерева T(I, E). Другими словами, если i, j, k Є I и j находится на пути из i в k, то всегда Xi V Xk Є Xj. Ширина дерева декомпозиции ({Xi, i Є I}, T(I, E)) – наибольшая вместимость его «мешка», уменьшенная на единицу, т.е. max i Є I {Xi ? 1}. Древовидная ширина гиперграфа H (обозначается tw(H)) определяется как наименьшая ширина всех возможных деревьев декомпозиции, которые существуют для H. Дерево декомпозиции, ширина которого равна tw(H), принято называть оптимальным деревом декомпозиции. Следует отметить, что для каждого (n, m) гиперграфа всегда существует хотя бы одно дерево декомпозиции. Например, таким является тривиальное дерево декомпозиции, состоящее из одного узла с «мешком» X и имеющего ширину n – 1. Ясно, что тривиальное дерево декомпозиции в общем случае не является оптимальным. Очевидна оценка: tw(H) < r(H). Если (n, m) – гиперграф H вырождается в связный граф без циклов и n > 2, m > 1, то r(H) = 2 и tw(H) = 1.

Свойства М-ациклических гиперграфов

Не нарушая общности, далее в качестве исходных гиперграфов будем рассматривать только непустые, минимальные и связные гиперграфы. Пусть в (n, m)-гиперграфе H = (X, U) задана некоторая упорядоченная последовательность его ребер P = (u1, u2, ..., uk, uk+1), 3 и k < m. Если fi = X(ui) U X(ui+1), i = 1, 2, ..., k, то последовательность P можно записать так:

P = (u1, f1, u2, f2, ..., uk, fk, uk+1). В H последовательность P задает М-цикл длины k, если

• u1, u2, ..., uk+1 – различные ребра гиперграфа H (различные как элементы семейства U);

• каждые два соседних ребра в P смежные, т.е. fi = 0, i = 1, 2, ..., k;

• fi = fi+1, i = 1, 2, ..., k;

• u1 = uk+1 и f1 = fk.

М-цикл P = (u1, f1, u2, f2, ..., uk, fk, uk+1) считается бесхордовым, когда для любой его тройки множеств fa, fb, fc (1 < a < b < c < k) в H нет ребра u такого, что fa U fb U fc Є X(u). Если хотя бы для одной тройки множеств fa, fb, fc (1 < a < b < c < k) такое ребро u существует в H (u играет роль хорды и не обязательно принадлежит P), то P – хордовый М-цикл гиперграфа H. Гиперграф H, не содержащий бесхордовых М-циклов, называется M-ациклическим. Значит, если H является М-ациклическим, то он не содержит М-циклов вообще, либо все его М-циклы хордовые. Наличие хотя бы одного бесхордового цикла приводит к M-цикличности гиперграфа H . Всякий граф без циклов М-ацикличен, а с циклами всегда М-цикличен. Таким образом, М-ацикличность не является прямым обобщением теоретико-графового понятия
«триангулированность», хотя имеется некоторая аналогия. Напомним, что граф триангулированный, если всякий его цикл длиной k > 4 обладает хордой – ребром, соединяющим две несмежные вершины этого цикла.

Список использованной литературы

1. Bodlaender H.L., Discovering treewidth. In Proceedings of the 31st Conference SOFSEM 2005, Springer-Verlag, Lecture Notes in Computer Science 3381, 2005, P. 1?16

2. Мейер Д. Теория реляционных баз данных. – М.: Мир, 1987

3. Быкова В.В. Полиномиальные достаточные условия бихроматичности гиперграфа // Вестник КрасГУ. Серия физ.-мат. науки. – 2006. – № 7. – С. 98?106

4. Быкова В.В. М-ациклические и древовидные гиперграфы // Известия Томского политехнического университета. – 2010. – Т. 317. – № 2. – С. 25?30

5. Зыков А.А. Гиперграфы // Успехи математических наук. – 1974. – Т. 29. – Вып. 6. – С. 89?154

6. Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. – М.: Наука, 1990. – 384 с.

7. Мельников О.И. Реализации гиперграфа деревьями минимального диаметра // Дискретная математика. – 1997. – Т. 9. – Вып. 4. – С. 91–97