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

Рис. 7. Техника изображения двойственного гиперграфа в виде помеченного псевдографа

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

Слева (см. рис. 8) приведена  техника визуализации гиперграфа, в  которой акцент делается на гиперребрах. Гиперребра группируются в шины, а вершины распределяются слева и справа от шины и соединяются с каждым графическим изображением инцидентного гиперребра отрезком. Допускается разбивать шины на непересекающиеся части. Подобный способ визуализации гиперграфа будем называть шинной техникой.

Справа (см. рис. 8) приведена  техника визуализации гиперграфа, в  которой акцент делается на связанных  компонентах гиперграфа системой гиперребер. Вершины группируются по блокам. Блок изображается прямоугольником. Для набора вершин из блока определятся система гиперребер. Каждое гиперребро изображается либо горизонтальной, либо вертикальной прямой, разрезающей прямоугольник блока на две части. Таким образом, прямоугольник блока разрезается на прямоугольные фрагменты со сторонами, которым соответствуют либо гиперребра, либо стороны ограничивающего прямоугольника блока. Каждая вершина помещается в тот фрагмент, который наилучшим образом для нее подходит и соединяется с каждым графическим изображением инцидентного гиперребра отрезком. Подобный способ визуализации гиперграфа будем называть блочной техникой.

Обе техники позволяют  естественно «сворачивать» разные гиперребра, определенные на одном множестве вершин (см. рис. 9). Два гиперребра определенные на одном множестве вершин можно изобразить в «свернутом» виде. На рисунке ребра g и h определены на одном множестве {v1,v3,v6} 

 

Рис. 8. Пример техники изображения гиперребер как системы отрезков и точек. Слева приведен гиперграф (см. рис. 1), изображенный в технике группировки гиперребер в шину (шинная техника). При этой технике система гиперребер изображается параллельными отрезками (либо вертикальными, либо горизонтальными). Справа приведен пример того же гиперграфа, изображенный в технике группировки вершин по блокам (блочная техника). Блок изображается в виде ограничивающего прямоугольника. Гиперребра изображаются как вертикальными, так и горизонтальными отрезками. На рисунке ребра g и e определены на одном множестве {v4,v6}

Блочную и шинную техники  можно комбинировать между собой (см. рис. 9). В случае визуализации гиперграфов  больших порядков предлагается разбивать  множество вершин гиперграфа на группы (блоки). Осуществлять группировку можно  исходя из разных критериев, например, можно минимизировать связи между  разными блоками. Содержимое каждого  блока можно изображать в блочной  технике. Систему гиперребер, не попавших целиком в один блок (межблочные гиперребра), можно изображать в шинной технике. Способ визуализации гиперграфа, использующий комбинацию блочной и шинной техники будем называть блочно-шинной техникой.

Рис. 9. Блочно-шинная техника изображения гиперграфа

Блочно-шинная техника обеспечивает легкость «чтения» информации:

• о степени вершины и ее связях с гиперребрами и другими вершинами (только в пределах блока);
• о степени гиперребра и связях гиперребра с вершинами;
• о компонентах гиперграфа и связях между ними (при разбиении гиперграфа на блоки с минимизаций внешних связей).

Блочно-шинная техника предоставляет возможность скрывать содержимое блоков, тем самым смещать акцент восприятия на межблочные связи (см. рис. 10). Позволяет содержимое крупных блоков выполнять в блочно-шинной технике (т.е. появляются иерархии блоков).

Рис. 10. Блочно-шинная техника изображения гиперграфа допускает сокрытие содержимого блоков, и изображать содержимое блоков в блочно-шинной технике

«Читабельность» изображения  гиперграфа, выполненного в блочно-шинной технике, во многом зависит: 1) от параметров (критерий, число блоков, число вершин в блоках и т.п.) и качества разбиения вершин по блокам; 2) от качества разбиения каждого блока на фрагменты (как прямая каждого гиперребра делит прямоугольник блока). В дальнейшем все изображения гиперграфов (по умолчанию) будем выполнять в блочно-шинной технике.

3. Части гиперграфа и  связность

Маршрутом в гиперграфе H=(V,E) называется конечная последовательность v₁,e₁,v₂,e₃,…v_l, составленная из его элементов таким образом, что вершины и ребра чередуются, а всякие два соседних элемента маршрута инцидентны. Началом и концом маршрута могут быть как вершина, так и гиперребро. Маршрут, в котором никакая пара соседних элементов не повторяется ни в прямом, ни в обратном порядке, называется цепью. Цепь называется простой, если она не содержит повторяющихся элементов гиперграфа.

Маршрут, начало и конец которого совпадают, называется циклическим. Если для цепи v₁,e₁,v₂,e₃,…v_l l>2 и v_l=v₁, то цепь называется циклом. Цикл называетсяпростым, если он не содержит повторяющихся элементов гиперграфа за исключением начала и конца.

Все эти понятия перенесены на гиперграф H с его кёнигова представления K(H), где они имеют обычный в теории графов смысл. В силу этого очевидна биекция между цепями (циклами) гиперграфа H=(V,E) и простыми цепями (простыми циклами) его кёнигова представления, концы которых принадлежат множеству V. 

 

Частью H'=(V',E') гиперграфа H=(V,E), называется гиперграф H'=(V',E'), где Æ¹V'ÍV, E'ÍE. В части гиперграфа H'=(V',E') все множество гиперребер E' можно поделить на две группы: внешние и внутренние гиперребра. Внешним гиперребром для части графа H' называется такое гиперребро eÎE', что $ vÎe, vÏV'. Внутренним гиперребром для части графа H' называется такое гиперребро eÎE', что для " vÎe, vÎV'. Часть H'=(V,E') гиперграфа H=(V,E) называется остовным гиперграфом (или фактором), т.е. для фактора VH'=VH.

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

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

Иными словами полнореберный подграф образуется (при V'ÌV) из исходного гиперграфа H слабым удалением вершин – таким, которое не сопровождается удалением ребер. При образовании усеченного подграфа происходит сильное удаление вершин – вместе со всеми инцидентными ребрами (см. рис. 11). Таким образом, матрица инциденций полнореберного подграфа получается из матрицы исходного гиперграфа удалением некоторых строк. В случае усеченного подграфа требуется еще удалить все те столбцы, которые содержат единицу хотя бы в одной из удаляемых строк.

Рис. 11. Граф H=(V,E), где V={v₁,v₂,v₃,v₄,v₅,v₆}, E={e_a,e_b,e_c,e_d,e_e,e_f}. Подграф H’=(V’,E) и суграф H’’=(V’’,E’’) образованы множеством вершин V’=V/{v₄,v₆}

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

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

По аналогии с предыдущими  понятиями, полновершинный суграф образуется (при E'ÌE) из исходного гиперграфа H слабым удалением гиперребер – таким, которое не сопровождается удалением вершин. При образовании усеченного суграфа происходит сильное удаление гиперребер – вместе со всеми инцидентными вершинами (см. рис. 12). Матрица инциденций полновершинного суграфа получается из матрицы исходного гиперграфа удалением некоторых столбцов. В случае усеченного суграфа требуется еще удалить все те строки, которые содержат единицу хотя бы в одном из удаляемых столбцов.

Рис. 12. Граф H=(V,E) изображен на рис. 11. Полновершинный суграф H’’’=(V,E’) и усеченный суграф H’’’’=(V’’’’,E’) образованы множеством гиперребер E’=E/{e_a,e_d}

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

Часть H' гиперграфа Н будем называть очищенным гиперграфом Н, если в H' получен из Н удалением всех голых элементов. Матрица инциденций очищенного гиперграфа получается из матрицы исходного гиперграфа удалением всех нулевых строк (строки, содержащие только нули) и нулевых столбцов (столбцы, содержащие только нули).

В кёниговом представлении K(H) слабому удалению вершины v гиперграфа H соответствует обычное удаление вершины vÎV, сильному удалению v из H – удаление вершины vÎV вместе со всеми смежными ей вершинами множества E. Аналогичный смысл для K(H) имеет удаление гиперребер гиперграфа H.

Рис. 13. Граф H=(V,E) изображен на рис. 11. Кусок H^{^}=(V^{^},E^{^}’) образован множеством вершин V’={v₄,v₆}

Часть H'=(V',E') гиперграфа H=(V,E) называется куском, образованном на множестве V'ÍV, если

E' = {eÎE | $ vÎV' vÎe}.

Таким образом, кусок гиперграфа есть очищенный полнореберный подграф (см. рис. 13).

Вершины u и v гиперграфа H называются связанными, если u=v или в Н существует (u,v)-цепь. Легко видеть, что отношение связанности есть отношение эквивалентности на множестве вершин гиперграфа. Классы этого отношения называются областями связности гиперграфа H, а порожденные областями связности подграфы называются компонентами (связными компонентами) гиперграфа Н. Количество компонент гиперграфа H обозначается через k(Н). Если k(H)=1, то гиперграф Н называетсясвязным. Очевидно, что k(Н)=k(K(Н)), где k(K(Н)) – число компонент графа K(H).

Очевидны три следующих  утверждения. Компонента H' гиперграфа Н является усеченным подграфом, если гиперграф не содержит голых ребер. Компонента H' гиперграфа Н является усеченным суграфом, если гиперграф не содержит голых вершин. Компонента H' гиперграфа Н является куском.

Две вершины гиперграфа называются независимыми (несмежными), если нет ни одного гиперребра одновременно инцидентного данным вершинам. Множество вершин гиперграфа называется независимым, если все пары этого множества вершин независимы. Пустое множество вершин по определению независимо. Как и в случае графов, наибольшее по мощности независимое множество вершин гиперграфа Н называется наибольшим независимым множеством вершин, а число вершин в этом множестве называется числом независимости гиперграфа Н и будем его обозначать через a₀(H). Через JH обозначается множество, элементами которого служат все независимые множества вершин гиперграфа Н.

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

4. Базовые операции над  гиперграфом

Алгоритмы в процессе работы могут осуществлять разнообразные  операции над структурой гиперграфа. Операции с гиперграфом предполагают переход от одного гиперграфа к другому. Такие операции, как удаление (вершины, ребра или подгиперграфа), стягивание (гиперребра, или множества вершин) – это операции, с помощью которых можно из имеющегося гиперграфа получить гиперграф с меньшим числом элементов. Имеются операции, позволяющие получать гиперграф с большим числом элементов. Это операции введения (вершины, гиперребра), расщепления (вершины, гиперребра). Есть такие операции, которые позволяют получать гиперграф с измененной структурой, но с точно таким же числом элементов, как и у исходного гиперграфа. Примером подобных операций могут служить операции введения и удаления вершины из гиперребра.  

 

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

E'=E È{e₀}.

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

E'=E \{e₀}.

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

E'=E \ {e₀}, V'=V \ {vÎV | vÎe₀}.

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

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

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

E₁={e' | e'=(e \ e₀)È{v₀}, eÎE \ {e₀}, eÇe₀≠Æ},

E₂={e | eÇe₀=Æ, eÎE \ {e₀}}.

Операция стягивания гиперребра означает отождествление инцидентных вершин к стягиваемому гиперребру. На рис. 14 приведен пример работы операции стягивания гиперребра.

Рис. 14. Слева показан исходный гиперграф H, справа результат H’ операции стягивания гиперребра e