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

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

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

Введение

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

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

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

Многоуровневые алгоритмы  предполагают широкие возможности  по настройке алгоритма, поскольку  позволяют достаточно легко интегрировать  в структуру алгоритма различные  эвристики, направленные на улучшение  получаемого решения. Не смотря на очевидные  достоинства многоуровневых методов, разработка и исследование этого  класса алгоритмов применительно к  графовым и гиперграфовым моделям у нас в стране – редкое явление. За рубежом такого рода методами занимаются 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).

a

b

c

d

e

A(H)=

1 0 0 0 0 1 1 0 0 0 1 1 1 0 0 0 0 1 1 1 0 1 1 0 0 0 1 0 1 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.