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

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

Батищев Д.И., Старостин Н.В., Филимонов А.В.

Введение

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

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

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

Многоуровневые алгоритмы  предполагают широкие возможности  по настройке алгоритма, поскольку  позволяют достаточно легко интегрировать  в структуру алгоритма различные  эвристики, направленные на улучшение  получаемого решения. Не смотря на очевидные  достоинства многоуровневых методов, разработка и исследование этого  класса алгоритмов применительно к  графовым и гиперграфовым моделям у нас в стране – редкое явление. За рубежом такого рода методами занимаются G.Karypis, V.Kumar[GKVK1], B.Hendrickson, R.Leland[BHRL], S. Barnard, H. Simon [SBHS] и др.

Еще одним примером способа  сокращения вычислительной сложности  решающих алгоритмов может служить  введение элементов рандомизации. Данное направление дало толчок к развитию методов эволюционных вычислений (подкласс методов случайного поиска), что позволило построить универсальные и достаточно мощные алгоритмы для широкого класса задач. У нас в стране разработкой такого типа алгоритмов занимались Л.А. Растригин[LRBK1, LRBK2, LRBK3, LRBK4], Ю.И. Неймарк[YNVG1, YNVG2], Б.П. Коробков, В.М. Курейчик, А.М. Мелихов, Л.С. Бернштейн, А.П. Рыжков, Г.И. Орлова, Я.Г. Дорфман, И.Л. Букатова, Д.Б. Юдин и другие. Методы эволюционных вычислений не гарантируют обнаружения оптимального решения. Однако практический интерес к ним не ослабевает, а наоборот усиливается. Объяснить это можно тем обстоятельством, что эти методы позволяют исследовать и находить приемлемые решения таких задач, решение которых при помощи традиционных методов оказывается затруднительным, а в некоторых случаях и просто невозможным.

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

1. Основные определения  и понятия гиперграфовых структур

Гиперграф — это такое  обобщение графа, когда ребрами  могут быть не только двухэлементные, но и любые подмножества вершин. Подобные объекты в математике известны давно, однако введение термина «гиперграф»  связано с успешным распространением на них ряда важных понятий и методов  теории графов [FR, HPSK, LLMP, NK, PL, VV]. Приведем основные понятия и их определения.

Рис. 1. Классическое изображение гиперграфа – диаграмма Венна [BBFR]. Вершины – пронумерованные окружности, гиперребра – прямоугольники с буквенными метками

Пусть V — конечное непустое множество вершин, E — конечное множество гиперребер. Пара (V,E) называется гиперграфом с множеством вершин V и множествомгиперребер E. Каждое гиперребро представляется некоторым подмножеством множества вершин, однако, нужно заметить, что понятие «гиперребро» неотождествимо с понятием «подмножество множества вершин». Ребра идентифицируются как различные сущности, даже если они представлены одинаковыми подмножествами множества вершин. Иными словами, определением гиперграфа допускается существование во множестве E ребер, различных по сути, но представленных одинаковыми подмножествами множества V. На рисунке 1 представлен пример подобной ситуации. В гиперграфе H(V, E), V={v₁, v₂, v₃, v₄, v₅, v₆}, E={e_a, e_b, e_c, e_d, e_e}, изображенном в диаграмме Венна два ребра содержат одни и те же вершины e_d={v₄, v₆}, e_e={v₄, v₆}, хотя e_d и e_e суть два различных элемента E. Под элементом гиперграфа будем понимать его вершину или гиперребро, т.е. любой элемент множества VÈE.

Введем соответствие между  вершинами V={v₁,v₂,…,v_n} и строками некоторой матрицы A(H), ребрами E={e₁,e₂,…,e_m} и ее столбцами, тогда гиперграф H(V,E) может быть задан своей матрицей инциденций A(H) = ||a_ij||, где

Ниже представлена матрица  инциденций для гиперграфа (см. рис. 1).

Два гиперграфа H=(V,E) и H'=(V',E') называются изоморфными, если между множествами вершин и семействами гиперребер можно установить взаимно однозначное соответствие V «V' и E «E' такое, что

"vÎV "v'ÎV' "eÎE "e'ÎE' { v «v' & e «e' & vÎe Þ v'Îe' }.

Множество вершин и множество  ребер гиперграфа H обозначаются символами VH и EH соответственно. Число |VH| вершин гиперграфа H называется его порядком и обозначается через |Н|. Если |Н|=п, |EH|=m, то H называется  
(п,т)-гиперграфом.

На рисунке 1 представлен (6,5)-гиперграф H, где VH={v₁,v₂,v₃,v₄,v₅,v₆}, EH={e_a,e_b,e_c,e_d,e_e , e_a={v₁,v₂,v₃}, e_b={v₂,v₃,v₅,v₆}, e_c={v₃,v₄,v₅}, e_d={v₄,v₆}, e_e={v₄,v₆}.

Ребра, представляемые равными  подмножествами, называются кратными ребрами гиперграфа. Гиперграф с кратными гиперребрами называют мультигиперграфом. Гиперребра могут иметь ориентацию (гипердуги), в этом случае гиперграф называют ориентированным или ультраграфом.

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

Диаграмма Венна (см. рис. 1), используемая для изображения гиперграфа не позволяет отобразить петли и  как следствие псевдогиперграфы. О других способах визуализации гиперграфовых структур речь пойдет ниже.

Если вершина vÎV принадлежит ребру eÎE, то будем говорить, что они инцидентны. Каждой вершине vÎV гиперграфа Н сопоставим множество E(v) всех инцидентных ей гиперребер. Число |E(v)| называется степенью вершины v, а |е| – степенью гиперребра е. В общем случае гиперребрами гиперграфа могут быть произвольные множества вершин (в том числе и пустые). Гиперребро со степенью равной 0 будем называть пустым, т.е. |е|=0. Вершина гиперграфа, не инцидентная никакому ребру, называетсяизолированной.

Две вершины v' и v" гиперграфа Н=(V,E) назовем смежными, если существует ребро еÎE, которое содержит обе эти вершины. Два гиперребра е' и е" гиперграфа Нназовем смежными, если е'Çе"¹Æ.

Для вершины v₀ гиперграфа H=(V,E) множество всех смежных вершин  называется окружением вершины v₀.

Для гиперграфа, изображенного  на рисунке 1, вершины под номерами 1 и 3 являются смежными. Окружение e(v₄)={v₃,v₅,v₆}.

Если в гиперграфе H нет кратных ребер и степень любого ребра е равна h (|е|=h), то гиперграф Н называется h-однородным (h-yниформным). Ясно, что всякий простой граф является 2-однородным гиперграфом. Тем самым граф – частный случай гиперграфа.

2. Визуализация гиперграфа

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

Рис. 2. Граф Кёнига для гиперграфа (двудольная техника), представленного на рис. 1

Во многих случаях для  визуализации гиперграфа H=(V,E) полезно использовать граф инциденций – это двудольный граф К(Н) с множеством вершин VÈE и множеством ребер {(v,e): (v,e)ÎV´E, vÎe}. Граф К(Н) называется кёниговым представлением гиперграфа Н. На рисунке 2 показано кёнигово представление гиперграфа, изображенного на рисунке 1, выполненное в двудольной технике (явно выделяются две доли в графе – доля вершин и доля гиперребер гиперграфа).

Рис. 3. Кёнигово представление ультраграфа

Кёнигово представление позволяет визуализировать не только мультигиперграфы, но и ультраграфы и псевдогиперграфы. В графе Кёнига для ультраграфов появляются дуги (см. рис. 3). В графе Кёнига для псевдогиперграфов (см. рис. 4) появляются кратные ребра.

Рис. 4. Пусть в псевдогиперграфе H имеется гиперребро d, заданное на совокупности вершин под номерами 4, 6 и 6 (вершина под номером 6 представлена в гиперребре два раза). В этом случае в графе K(H) появляется кратное ребро

Любому (n,m)-гиперграфу H=(V,E) без изолированных вершин можно сопоставить (m,n)-гиперграф Н*=(V*, E*), в котором V*=E, а E* – семейство всех множествE(v), vÎV. Гиперграф H* называется двойственным к H. Очевидно, что К(Н*) получается из К(Н) лишь переменой множеств V и E местами, причем все ребра сохраняются (см. рис. 5). Таким образом, К(Н*)@К(Н).

Рис. 5. Двойственный гиперграф H* к гиперграфу H (см. рис. 1). Кёнигово представление для двойственного гиперграфа H* совпадет с графом Кёнига (см. рис. 2)

Очевидно утверждение, что  не только любой конечный гиперграф  допускает кёнигово представление, но и, наоборот, каждый граф Кёнига является представлениемК(Н) некоторого конечного гиперграфа Н и определяет его однозначно с точностью до изоморфизма. Возникает естественное желание отказаться от построения теории гиперграфов, заменив ее изучением одних лишь графов Кёнига. Однако этого не происходит, так как многие положения о гиперграфах в терминах кёниговых представлений приобретают искусственный и громоздкий характер, скрывающий суть дела. Например, понятие хроматического числа обыкновенного графа G (а это частный случай гиперграфа – 2-однородный гиперграф) в терминах его представления K(G) определить весьма непросто. Напротив, в некоторых случаях, например в определении планарности гиперграфа, кёнигово представление играет весьма существенную роль.

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

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

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

Кёнигово представление почти не позволяет «читать» информацию об общих вершинах гиперребер. Другим недостатком кёнигова представления является значительное увеличение число элементов изображаемого графа. Предлагается техника изображение двойственного гиперграфа, лишенная описанных недостатков графа Кёнига.

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

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

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

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

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

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