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

Под фильтром понимается оператор F, на вход которого подается гиперграф H, а на выходе получается новый гиперграф FH. Исходный гиперграф назовем гиперграфом-прообразом. Кроме исходного гиперграфа H фильтр на вход получает условие фильтрации, которое можно представить в виде отображения j:A´Â→{0,1}. Отображение j каждой паре («атрибут», «значение») ставит в соответствие либо 0, либо 1. Значение 1 подразумевает, что элемент исходного гиперграфа, имеющий данный атрибут с данным значением, будет профильтрован – т.е. подвержен работе оператора фильтрации. Таким образом, отображение j:A´Â→{0,1} для гиперграфа H однозначно определяет множество элементов jH гиперграфа, для которых будет выполняться условие фильтрации:

jH = {cÎVÈE: $ a_iÎa_H(c): j(a_i, w_H(c,a_i))=1}.

Будем обозначать через jHV – множество вершин гиперграфа H, для которых выполняется условие фильтрации j, jHE – множество гиперребер гиперграфа H, для которых выполняется условие фильтрации j. Таким образом, jH = jHVÈjHE.

Элементы, для которых  НЕ выполняется условие фильтрации, “переходят” в новый гиперграф jH, причем набор атрибутов элемента и их значений в гиперграфе jHбудет таким же, как и в исходном гиперграфе H:

a_H(c)=a_FH(c) и w_H(c,a_i)=w_FH(c,a_i) для "a_iÎa_H(c), где cÎH/jH.

На рисунке 22 представлены изображения гиперграфа H и части  гиперграфа jH. 

 

Рис. 22. Изображения гиперграфа H и частей гиперграфа jH, удовлетворяющей условию фильтрации j= для cÎVHÈEH

6. Типы фильтров

Предлагается два типа фильтров: скрывающие фильтры и объединяющие фильтры. Для обозначения фильтров примем следующую форму записи:

FH=filter{ множество_элементов [ | разбиение_на_классы ] }H.

Здесь FH – результат работы фильтра; вместо filter указывается либо hide – скрывающий фильтр, либо join – объединяющий фильтр; множество_элементов описывает множество элементов, удовлетворяющих условию фильтрации; разбиение_на_классы (может быть опущено) описывает признак, по которому будет происходить разбиение множества элементов на классы, каждый класс будет подвержен действию, указанному в filter.

В общем случае скрывающий фильтр на входе принимает гиперграф H, а на выходе получает новый гиперграф FH = H/jH. Таким образом, результатом работы скрывающего фильтра есть исходный гиперграф без элементов, удовлетворяющих условию фильтрации. Ниже приведены определения некоторых частных случаев скрывающих фильтров:

• фильтр, скрывающий только гиперребра, получает гиперграф FH методом слабого удаления ребер jHE, которые удовлетворяют условию фильтрации.

Так, например, фильтр, скрывающий гиперребра c атрибутом attr со значением val можно записать так:

FH=hide{eÎEH: attrÎa(e) & w(e,attr)=val}H; 

 

• фильтр, скрывающий вершины, получает гиперграф FH методом слабого удаления вершин jHV, которые удовлетворяют условию фильтрации.

Так, например, фильтр, скрывающий вершины, для которых определен  атрибут attr можно записать так:

FH=hide{vÎVH: attrÎa(v)}H; 

 

• фильтр, скрывающий усеченный подграф, получает гиперграф FH методом слабого удаления множества вершин jVH и множества внутренних гиперребер, удовлетворяющих условию фильтрации j.

Так, например, фильтр, скрывающий усеченный подграф, образованный на множестве вершин V'ÍV, можно записать так:

FH=hide{сÎV'È{eÎE: $! vÎV \ V' & vÎe}}H;

• фильтр, скрывающий кусок гиперграфа, получает гиперграф FH методом сильного удаления множества вершин jHV.

Так, например, фильтр, скрывающий кусок гиперграфа, образованный на множестве вершин V'ÍV, можно записать так:

FH=hide{сÎV'È{eÎE: V'Çe¹Æ}}H. 

 

На рисунке 23 изображен  гиперграф и результаты работы разных скрывающих фильтров при одном и  том же условии фильтрации. На рисунке 23 изображены гиперграфы:

H₁=hide{eÎEH: lockÎa(e) & w(e,lock)=on}H,

H₂=hide{vÎVH: lockÎa(v) & w(v,lock)=on}H,

H₃=hide{сÎV'ÈE', V'={vÎVH: lockÎa(v) & w(v,lock)=on}, E'={eÎE: $! vÎV\V' & vÎe}}H,

H₄=hide{сÎV'ÈE', V'={vÎVH: lockÎa(v) & w(v,lock)=on}, E'={eÎE: V'Çe¹Æ}H.

Рис. 23. Изображения гиперграфа H и результатов работы скрывающих фильтров для следующего условия фильтрации

j=

 для cÎVHÈEH.

На рисунке: H₁ – результат работы фильтра, скрывающего только гиперребра; H₂ – результат работы фильтра, скрывающего только вершины; H₃ – результат работы фильтра, скрывающий усеченный подграф; H₄ – результат работы фильтра, скрывающий кусок

Другая группа фильтров –  объединяющие фильтры. Основная идея объединяющих фильтров заключается в применении операций стягивания элементов исходного гиперграфа H, удовлетворяющих условию фильтрации j. Предлагаются четыре базовых варианта объединяющего фильтра:

• фильтр, объединяющий гиперребра, получает гиперграф FH методом стягивания гиперребер jHE, которые удовлетворяют условию фильтрации, в одно новое гиперребро e₀. При этом гиперребро e₀ будет иметь некоторый атрибут a_i только том случае, если атрибут a_i имеют все гиперребра из jHE и значение атрибута будет равно b_j только том случае, если атрибут a_i со значением b_j имеют все гиперребра из jHE.

Так, фильтр, объединяющий гиперребра только гиперребра c атрибутом attr со значением val можно записать так:

FH=join{eÎEH: attrÎa(e) & w(e,attr)=val}H;

Рис. 24. Изображения гиперграфа H и результатов работы объединяющих фильтров для следующего условия фильтрации

j=

 для cÎVHÈEH.

На рисунке: H₁ – результат работы фильтра, объединяющего гиперребра; H₂ – результат работы фильтра, объединяющего вершины; H₃ – результат работы фильтра, объединяющего гиперребра по значению; H₄ – результат работы фильтра, объединяющего вершины по значению

• фильтр, объединяющий вершины, получает гиперграф FH методом стягивания вершин jHV, которые удовлетворяют условию фильтрации, в одну новую гипервершину v₀. При этом гипервершина v₀ будет иметь некоторый атрибут a_i только том случае, если атрибут a_i имеют все вершины из jHV; и гипервершина v₀будет иметь некоторый атрибут a_i со значением b_j только том случае, если атрибут a_i со значением b_j имеют все вершины из jHV;

Так, например, фильтр, объединяющий только вершины, для которых присутствует атрибут attr можно записать так:

FH=join{vÎVH: attrÎa(v)}H;

• фильтр, объединяющий гиперребра по значению атрибутов. Фильтр сначала разбивает все множество гиперребер jHЕ на классы эквивалентности по признаку равенства значений заданного атрибута a₀ – дополнительный параметр фильтра. Т.е. каждое значение атрибута a₀ определяет класс эквивалентности. Затем гиперребра каждого класса стягиваются в новое гиперребро. При этом каждое гиперребро e будет иметь некоторый атрибут a_i только том случае, если атрибут a_iимеют все гиперребра класса, и гиперребро e будет иметь некоторый атрибут a_i со значением b_j только том случае, если атрибут a_i со значением b_j имеют все гиперребра класса.

Так, фильтр, объединяющий гиперребра по значениям атрибута attr можно записать так:

FH=join{eÎEH: attrÎa(e) | w(e,attr)Π}H;

• фильтр, объединяющий вершины по значению атрибутов. Фильтр сначала разбивает все множество вершин jHV на классы эквивалентности по признаку равенства значений заданного атрибута a₀ – дополнительный параметр фильтра. Т.е. каждое значение атрибута a₀ определяет класс эквивалентности. Затем вершины каждого класса стягиваются в новую гипервершину. При этом каждая гипервершина v будет иметь некоторый атрибут a_i только том случае, если атрибут a_i имеют все вершины класса, и гипервершина v будет иметь некоторый атрибут a_i со значением b_j только том случае, если атрибут a_i со значением b_j имеют все вершины класса.

Так, фильтр, объединяющий вершины  по признаку делимости значения атрибута attr на два:

FH=join{vÎVH: attrÎa(v) | w(v, attr) mod 2Î{0,1}}H; 

 

На рисунке 24 изображен  гиперграф и результаты работы объединяющих фильтров при одном и том же условии фильтрации. На рисунке изображены гиперграфы:

H₁=join{eÎEH: lockÎa(e)}H,

H₂=join{vÎVH: lockÎa(v)}H,

H₃=join{eÎEH: lockÎa(e) | w(e, lock)}H,

H₄=join{vÎVH: lockÎa(v) | w(v, lock)Î{null,on,off}}H.

7. Атрибутивная связность  между гиперграфами

Пусть имеется помеченный гиперграф Н=(V,E,a,w), задано условие фильтрации j для некоторого фильтра F. Представим работу фильтров на уровне отдельных элементов. Очевидно, что после работы фильтра F для любого элемента c гиперграфа FH можно указать непустое множество элементов F^-1(c) исходного гиперграфа H, которые оказали влияние на формирование атрибутивной информации a_H(c) и w_H(c).

Результат работы фильтра FН=(FV,FE,a_F,w_F) назовем видом гиперграфа Н, если любая операция по изменению атрибутивной информации для любого элемента изFН приводит к изменению атрибутивной информации соответствующих элементов из Н по следующему правилу: добавление (изменение) атрибута a₀ÎA со значением b₀ÎÂдля элемента cÎFН приводит к добавлению (изменению) атрибута a₀ÎA со значением b₀Πдля всех элементов из F^-1(c)ÍН.

В тоже время, помеченный гиперграф Н=(V,E,a,w) будем называть основанием вида FН=(FV,FE,a_F,w_F), если любая операция по изменению атрибутивной информации для любого элемента из Н приводит к изменению атрибутивной информации соответствующих элементов из FН по следующему правилу: добавление (изменение) атрибута a₀ÎA со значением b₀Πдля элемента cÎН приводит к добавлению (изменению) атрибута a₀ÎA со значением b₀Πдля всех элементов F(c)ÍFН.

Пусть имеется пара помеченных гиперграфов H₁ и H₂. Будем говорить, что H₂ атрибутивно зависим от H₁ и обозначать H₁®H₂ (либо H₂¬H₁), если либо H₂является видом Н₁, либо H₁ является основанием Н₂.

Будем говорить, что H₁ и H₂ атрибутивно связаны и обозначать H₁«H₂, если H₁®H₂ и H₁¬H₂.

Рис. 25. Изображения гиперграфа H и его видов:

H₂=join{vÎVH: lockÎa(v) | w(v, lock)}H,

H₃=join{eÎEH: lockÎa(e)}H₂,

H₄= join{vÎVH: lockÎa(v)}H₂. 

 

 

 

Очевидны следующие утверждения.

• Суперпозиция фильтров F есть фильтр, т.е. если F₁ и F₂ – фильтры, тогда и F₁F₂ – тоже фильтр.
• Если H₁® H₂ и H₂® H₃ , тогда H₁® H₃.
• Если H₁« H₂ и H₂« H₃ , тогда H₁«H₃.
• Отношение « является отношением эквивалентности.

Число суперпозиций фильтров F, примененных к гиперграфу H назовем порядком вида гиперграфа H, если между ними имеется отношение гиперграф–вид. Таким образом, Н – это вид нулевого порядка гиперграфа H; FН – вид первого порядка гиперграфа H, если H¬FH; FFН – вид второго порядка гиперграфа H, если H¬FFH.

Рис. 26. Связи на уровне атрибутивной информации между видами и основаниями. На рисунке изображены гиперграф H и его виды, представленные на рис. 29. Добавление нового атрибута attr со значением b к элементу v₁₂ вида H₄ привело к цепной реакции добавления атрибута attr=b к элементам v₁₀, v₁₁ вида H₂,так как именно эти элементы оказали влияние на формирование атрибутивной информации a_H4(v₁₂) и w_H4(v₁₂). В свою очередь изменилась атрибутивная информация для следующих элементов исходного гиперграфа H: v₁, v₂, v₃, v₄, v₇, v₈. Синхронно с изменениями атрибутивной информации элементов v₁₀, v₁₁ вида H₂ и произошло изменение соответствующих элементов v₁₀, v₁₁ вида H₃ 

 

На рисунке 25 представлено изображение основания H и его вида H₂, который получен слиянием одного множества вершин {v₁,v₂,v₃,v₈} в одну гипервершину v₁₀ и другого множества вершин {v₄,v₇} в одну гипервершину v₁₁. В свою очередь, сам гиперграф H₂ является основанием для двух видов H₃ и H₄. Вид H₃ получен посредством применения операции отождествления множества гиперребер {e₁, e₂, e₄, e₅} в одно новое гиперребро e₇. Вид H₄ получен слиянием вершин v₁₀ и v₁₁ в одну гипервершину v₁₂. Если изменить атрибутивную информацию любого из видов, то синхронно измениться атрибутивная информация у соответствующих элементов основания. Так, на рисунке 26 элементу v₁₂ вида H₄ добавлен новый атрибут attr со значением b, что привело к добавлению соответствующего атрибута элементам v₁₀ и v₁₁ основания H₂, что, в свою очередь, привело к добавлению атрибута attr=b элементам v₁,v₂,v₃,v₄,v₇ и v₈ основания H. С другой стороны, так как изменилась атрибутивная информация элементов v₁₀ и v₁₁основания H₂, атрибут attr=b будет добавлен к элементам v₁₀ и v₁₁ вида H₃. Таким образом, гиперграфы H₃ и H₄ также являются видами гиперграфа H, и в свою очередь, гиперграф H является основанием для видов H₃ и H₄.