Многоуровневая декомпозиция гиперграфовых структур

Введением вершины v₀ÎV в гиперребро e₀ гиперграфа H назовем операцию перехода от H к гиперграфу H'=(V,E'), где

E'=(E \ e₀)È{e*}, e*=e₀È{v₀}.

Удалением вершины v₀Îe₀ из гиперребра e₀ гиперграфа H назовем операцию перехода от H к гиперграфу H'=(V,E'), где

E'=(E \ e₀)È{e*}, e*=e₀ /{v₀}.

Введением вершины v₀ÏV гиперграфа H назовем операцию перехода к гиперграфу H'=(V',E), где

V'=VÈ{v₀}.

Пусть существует такая вершина v₀ÎV. Тогда сильным удалением вершины v₀ назовем переход от гиперграфа H к H'=(V',E'), где

V'=V \ {v₀}, E'= E \ E(v₀).

Обозначим через E(v₀)={e | eÎE, v₀Îe} совокупность ребер гиперграфа H, содержащих вершину v₀. Тогда слабым удалением вершины v₀ назовем переход от гиперграфаH к H'=(V',E'), где

V'=V \ {v₀}, E'= E \ E(v₀)ÈE*, E*={e* | e*=e \{v₀}¹Æ, eÎE(v₀)}.

Рис. 15. Пусть исходный гиперграф H – гиперграф, изображенный на рис. 15. Гиперграфы H’ получены удалением вершины под номером 1. Слева показан результат слабого удаления вершины, а справа – результат сильного удаления вершины

Таким образом, сильное удаление вершины сопровождается слабым удалением  всех инцидентных гиперребер, а слабое удаление вершины сопровождается удалением вершины из всех инцидентных ей гиперребер. На рисунке 15 приведен результат операций удаления вершины.

Пусть имеется часть H'=(V',E') гиперграфа H=(V,E). Слабым удалением части H' из гиперграфа H назовем переход от гиперграфа H к H''=(V'',E''), где

V''=V \ V',

, где E*={e*: e*=e\V'¹Æ, eÇV'¹Æ, eÎE \ E'}.

Сильным удалением  части H'=(V',E') из гиперграфа H=(V,E) назовем переход от гиперграфа H к H''=(V'',E''), где

V''=V \ {vÎV | $ eΠE \ E' & vÎe},

.

Иными словами, слабое удаление части H' из графа H предполагает слабое удалении всех элементов части H' из графа H, а сильное удаление части H' из графа Hпредполагает сильное удалении всех элементов части H' из графа H (см. рис. 16).

Как уже отмечалось выше, операции удаления элементов гиперграфа приводят к появлению голых элементов. На рис. 18 изображен гиперграф H' c голым элементом – гиперребром e₆. Операцию удаления из гиперграфа H всех голых элементов будем назвать операцией очистки (чистки) гиперграфа H. Результатом операции является очищенный гиперграф H.

Рис. 16. Беря за H гиперграф, изображенный сверху, а за его часть H*=(V*,E*) (выделен красным) на множестве вершин V*={v₁,v₃} и гиперребер E*={e₂,e₄}. Слева показан гиперграф H’, полученный как результат слабого удаления из H его части H*. Справа показан гиперграф H’’, полученный как результат сильного удаления из H его части H*

Если часть H'=(V',E') гиперграфа H=(V,E) является полнореберным подграфом или полновершинным суграфом гиперграфа H, то результат удаления (как сильного, так и слабого) из H подграфа H' приведет к получению гиперграфа H^* на голых элементах, а чистка гиперграфа H^* приведет к получению (0,0)–гиперграфа.

Очевидно, что операции сильного и слабого удаления компоненты приведут к одинаковым результатам. Т.е. если часть H'=(V',E') гиперграфа H=(V,E) является компонентой, а H¹=(V¹,E¹) – есть результат сильного удаления и H²=(V²,E²) – есть результат слабого удаления компоненты H' из H, то V¹=V²=V\V’ и E¹=E²=E\E’.

Пусть V'ÍV. Тогда стягиванием (отождествлением) подмножества вершин V' гиперграфа H=(V,E) назовем переход к гиперграфу H''=(V'',E''), где

V''=V \V' È{v₀}, v₀ – новая вершина (v₀ÏV),

, где E*={e* | e*=(e\V')È{v₀}, e\V'¹Æ, eÇV'¹Æ, eÎE}.

Таким образом, операция стягивания множества вершин в одну заключается (см. рис. 17): 1) во введении новой вершины; 2) во введении новой вершин во все  гиперребра, инцидентные хотя бы одной вершине из стягиваемого множества; 3) слабому удалению всех вершин, принадлежащих стягиваемому множеству.

Вершину, образующуюся при  стягивании некоторого множества вершин, будем называть гипервершиной (псевдовершиной).

В результате стягивания система  внутренних гиперребер для множества вершин V' (т.е. гиперребра eÎEH которые eÍV') заменятся на множество гиперребер вида e*={v₀}. Для исключения подобных ситуаций выгодно использовать операции стягивания усеченного подграфа.

Рис. 17. Исходный гиперграф изображен сверху, результат операции стягивания множества V’={v₁,v₂,v₃} приведет к гиперграфу H’ (показан слева). Результатом стягивания усеченного подграфа на множестве V’={v₁,v₂,v₃} является гиперграф H’’ (показан справа).

Стягивание (отождествлением) усеченного подграфа H' заключается в отождествлении всех элементов H' новой гипервершине гиперграфа:

V''=V \V' È{v₀}, v₀ – новая вершина (v₀ÏV),

, где E*={e*: e*=e\V'¹Æ, eÇV'¹Æ, eÎE \ E'}.

Таким образом, операция стягивания усеченного подграфа H' на множестве вершин (см. рис. 17) заключается: 1) во введении новой вершины; 2) во введении новой вершины во все гиперребра, инцидентные хотя бы одной вершине из VH'; 3) сильному удалению усеченного подграфа H'.

Для гиперребер определим аналог операции стягивания множества вершин. Пусть E'ÍE. Тогда отождествлением множества гиперребер E' из гиперграфа H=(V,E) назовем переход от гиперграфа H к H''=(V,E''), где

,  .

Таким образом, операция отождествления множества гиперребер (см. рис. 18) заключается: 1) во введении нового гиперребра; 2) во введении вершин, инцидентных хотя бы одному гиперребру из стягиваемого множества гиперребер, в новое гиперребро; 3) слабому удалению всех гиперребер из стягиваемого множества.

Рис. 18. Сверху изображен исходный гиперграф, результатом операции стягивания множества E’={e_a,e_b,e_c} будет гиперграф H’ (показан снизу). Новое гиперребро f как множество получено объединением гиперребер a, b и c как множеств.

В определенном смысле двойственными  к операциям отождествления вершин и гиперребер являются операции расщепления вершин и гиперребер соответственно.

Пусть H=(V,E) – гиперграф. Расщеплением вершины v₀ÎV назовем переход от исходного гиперграфа H к гиперграфу H'=(V',E'), предусматривающий последовательное выполнение следующих операций:

1. из множества E(v₀) инцидентных вершине v₀ гиперребер получить два множества M и N такие, что E(v₀)=MÈN;
2. ввести в гиперграф две вершины v_M и v_N ;
3. ввести вершину v_M во все гиперребра из M и ввести вершину v_N во все гиперребра из N;
4. произвести слабое удаление вершины v₀.

На рис. 21 представлен  пример расщепления вершины v₇ гиперграфа H', изображенного на рис. 19.

Рис. 19. Взяв за исходный гиперграф H, гиперграф, изображенный на рис. 19 слева (обозначен как H’), расщепим вершину v₇. E(v₇)={e_a,e_b,e_c}. Примем M={e_a,e_b}, N={e_a,e_c}. Результат расщепления - гиперграф H^{^}.

Пусть H=(V,E) – гиперграф. Расщеплением гиперребра e₀ÎE назовем переход от исходного гиперграфа H к гиперграфу H'=(V',E'), предусматривающий последовательное выполнение следующих операций:

1. из совокупности вершин, образующих гиперребро e₀ получить два множества M и N такие, что e₀=MÈN;
2. ввести два гиперребра e_M=M и e_N=N;
3. произвести слабое удаление гиперребра e₀.

На рис. 22 представлен  пример расщепления гиперребра e_f гиперграфа H', изображенного на рис. 20.

Рис. 20. Взяв за исходный гиперграф H, гиперграф изображенный на рис. 18 снизу (обозначен как H’), расщепим гиперребро e_f. E(e_f)={v₁,v₂,v₃,v₄,v₅,v₆}. Примем M={v₂,v₃,v₄,v₅}, N={v₁,v₆}. Результат расщепления - гиперграф H^, показан на рисунке

Очевидно, что операции расщепления  вершины и гиперребра не являются в общем случае однозначными, так как неоднозначен процесс получения двух подмножествM и N.

5. Атрибуты, операции фильтрации  и фильтры

В реальных задачах в гиперграфовые модели приходится добавлять разнообразную дополнительную информацию. В силу этого в действительности исследователям приходится работать с помеченными гиперграфами. Задавая на вершинах и гиперребрах гиперграфа H=(V,E) отображение a_H:VÈE→M, где M – некоторое семейство непустых (необязательно различных) подмножеств множества A, получим помеченный (взвешенный) гиперграф (H,a). Элементы множества A называются метками или атрибутами. В дальнейшем четверкой (V,E,a_H,w) будем обозначать помеченный гиперграф Н=(V,E,a_H,w).

Если отображение a_H ставит в соответствие каждому элементу гиперграфа действительное число (вектор из действительных чисел), то (H,a) будем называтьвзвешенным гиперграфом.

В общем случае a_H отображает вершину vÎV в набор атрибутов a_H(v)ÍA, приписанных этой вершине, и гиперребро eÎE в набор атрибутов a_H(e)ÍA, приписанных этому гиперребру.

Для гиперграфа H введем отображение w_H:(VÈE)´A→Â, которое каждой паре значений: элементу гиперграфа и его атрибуту ставит в соответствие значение атрибута. Здесь Â – это множество всевозможных значений атрибутов. Допустим, каждый элемент схемы характеризуется собственными габаритами: ширина и высота. В гиперграфовой модели этой схемы каждой вершине vÎV будет приписан набор a_H(v), состоящий из двух атрибутов «ширина» и «высота», а отображение w_H(v,a_i), где a_iÎa_H(v), укажет численное значение габарита.

Рис. 21. Изображение помеченного гиперграфа (H,a) с атрибутивной информацией (a,w_H), где VH={v₁,v₂,v₃,v₄}, EV={e_a,e_b}, A={color,x,y}; a_H(v₁)=a_H(v₂)=a_H(v₄)={color}, a_H(e_a)={color,x,y},a_H(v₃)={x,y}; w_H(v₂,color)=blue, w_H(v₃,y)=20; w_H(v₄,color)=red, w_H(e_a,color)=blue, w_H(e_a,y)=20. Таким образом, для v₂ и e_a определены атрибуты color со значением blue, а для v₁ и v₂определены атрибуты color без значения

Будем говорить, что элемент с гиперграфа H имеет атрибут a_i со значением b_j, если a_iÎa_H(с) и b_j=w_H(с,a_i). Соответственно, будем говорить, что элемент сгиперграфа H имеет атрибут a_i без значения, если a_iÎa_H(с) и отображение w_H(с,a_i) на указанном наборе значений не определено. Набор атрибутов a_H(с) и отображениеw_H(с): a_H(с) → будем называть атрибутивной информацией элемента сÎH. На рисунке 21 приведен пример изображения помеченного гиперграфа с атрибутивной информацией.

Можно привести массу алгоритмов, которые в процессе работы над  графом не меняют его структуру, но вводят в графовую модель дополнительную информацию. Подобная информация укладывается в графовую модель в виде специальных меток, которые приписываются элементам графа. Примером подобных алгоритмов могут служить алгоритмы раскраски графа. В этом случае информация принадлежности цветовому классу элемента графа носит глобальный характер и фактически в этой информации кодируется решение задачи. В других алгоритмах подобная дополнительная информация носит временный или вспомогательный характер. Так, например, в волновых алгоритмах схема распространения волны строится на приписывании специальных пометок для уже рассмотренных элементов графа.

Очевидно, что операции, позволяющие  менять атрибутивную информацию гиперграфа, являются не менее важным компонентом  в общей модели управления гиперграфом. Введем операции над атрибутами элементов  гиперграфа.

Пусть имеется помеченный гиперграф Н=(V,E,a,w). Добавление атрибута a₀ÎA без значения к элементу cÎVÈE предполагает переход к новому помеченному гиперграфу Н'=(V,E,a',w), где a'_H(c)=a_H(c)È{a₀}. Добавление атрибута a₀ÎA со значением b₀Πк элементу cÎVÈE предполагает переход к новому помеченному гиперграфуН'=(V,E,a',w'), где a'_H(c)=a_H(c)È{a₀}, w'_H(c,a₀)=b₀.

Противоположной операцией  добавлению атрибута является операция удаления атрибута. Удаление атрибута a₀ÎA элемента cÎVÈE предполагает переход к новому помеченному гиперграфу Н'=(V,E,a',w), где a'_H(c)=a_H(c)/{a₀}.

Важно не только добавлять  и удалять атрибуты, но и менять значение атрибута с одного на другое. Изменение значения атрибута a₀ÎA на значение b₀Πдля элементаcÎVÈE предполагает переход к новому помеченному гиперграфу Н'=(V,E,a,w'), где w'_H(c,a₀)=b₀. Удобно ввести специальное значение атрибута – null. Будем считать, что если атрибут имеет значение null, то этот атрибут не имеет значения. Т.е. если w_H(c,a₀)=null, то для элемента c гиперграфа H атрибут задан без значения. В этом случае, операция удаления значения атрибута формально сводится к операции изменения значения атрибута.