автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Многокритериальная задача размещения ациклических графов на плоскости

БЕЛАШ Александр Николаевич

На правах рукописи

МНОГОКРИТЕРИАЛЬНАЯ ЗАДАЧА РАЗМЕЩЕНИЯ АЦИКЛИЧЕСКИХ ГРАФОВ НА ПЛОСКОСТИ

05.13.18 - "Математическое моделирование, численные методы и комплексы программ"

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидатафизико-маггематических наук'

Ставрополь — 2006

Работа выполнена па кафедре «Высшая математика» Северо-Кавказского государственного технического университета (г.Ставрополь)

Защита состоится 23 декабря 2006 в ?-ООч на заседании диссертационного совета ДМ 212.245.09 в Северо-Кавказском государственном техническом университете по адресу:

355028, г. Ставрополь, пр. Кулакова, 2

С диссертацией можно ознакомиться в научной библиотеке Северо-Кавказского государственного технического университета

Научный руководитель:

доктор физико-математических наук,

профессор

A.M. Кочкаров

-доктор физико-математических наук, профессор А.Л. Симоновский -кандидат физико-математических наук, доцент А.Е. Ленский Высокогорный геофизический институт

Официальные оппоненты:

Ведущая организация:

Ученый секретарь

диссертационного совета

кандидат физико-математических наук

О.С. Мезенцева

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы.

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

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

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

Цель работы

Построение и исследование математической модели реализации крупного научно-исследовательского проекта, состоящего в представлении объектно-ориентированной модели крупного программного комплекса, с последующим ее

сведением к многокритериальной задаче размещения ациклических графов на плоскости.

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

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

Методы исследования

Все исследования, проведенные в настоящей работе, используют методы и подходы дискретной математики и теории графов, в частности. Аппарат теории графов наилучшим образом подходит для формального представления задач связанных с изменением и преобразованием дискретных объектов, какими являются структуры систем.

Научная новизна

Построение . многокритериальной задачи о размещении ациклических графов. Исследование этой задачи в применении к проблеме представления на плоскости объектно-ориентированной модели крупного программного комплекса.

Улучшение временной трудоемкости известных алгоритмов для нахождения решения задачи размещения ациклических графов на плоскости, построение новых алгоритмов.

Теоретическая значимость работы

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

Практическая ценность

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

Положения, выносимые на защиту

1. Математическая модель многокритериальной постановки размещения ациклических графов на плоскости. '

2. Алгоритм a¡ получения оптимального разбиения по критерию симметричного размещения графа.

3. Алгоритм а1 получения оптимального разбиения по критерию совпадающего направления ребер.

4. Алгоритм от, получения оптимального разбиения но критерию прямолинейности ребер.

5. Алгоритмы размещения предфрактального графа порожденного ациклической затравкой.

6. Алгоритмы перемещения графических объектов графа на плоскости.

Апробация работы

Основные результаты работы докладывались на следующих научно-технических конференциях: V Международная научно-практическая конференция «Компьютерные технологии в науке, производстве, социальных и экономических процессах». Новочеркасск, 2004, 1 Международная научно-техническая конференция «Инфотелекоммуннкацнонные технологии в науке, производстве и образовании». Ставрополь, 2004, Международная научно-техническая конференция «Информационно-вычислительные технологии и их применения». Пенза, 2005. Ш Международная научно-практическая конференция «Теория, методы проектирования, программно-техническая платформа информационных систем». Новочеркасск, 2005, VII Международная научно-практическая конференция «Информационная безопасность». Таганрог, 2005. II

Международная научно-практическая конференция «Исследование, разработка и применение высоких нехнологий в промышленности». С-т Петербург, 2006. Личный вклад автора

Обосновано применение ациклических графов для представления объектно-ориентированной модели программного комплекса. .

Разработаны алгоритмы с оценками и программный комплекс Graph Drawing А В получения оптимального размещения ациклического графа го различным критериям оптимальности. Также разработаны алгоритмы работы с графом и его графическими объектами, корректного перемещения их. Разработаны алгоритмы конструирования, удаления как графа целиком, так и его отдельных частей. Разработаны алгоритмы распознавания графа. Алгоритмы реализованы в среде Visual С++ 6.0 с MFC,

Структура и объем работы . ,

Диссертация состоит из введения, трех тематических глав, заключения, приложения и списка использованных источников из 106 наименований. Работа изложена на 125 страницах и содержит 25 рисунков, 1 таблицу, 33 страниц приложения.

СОДЕРЖАНИЕ РАБОТЫ Во введении обоснована актуальность выбранной темы диссертации, сформулированы цель, задачи исследования и положения, выносимые на защиту, кратко изложено содержание работы, изложены и проанализированы известные основные методики размещения ациклических графов.

В первой главе сформулирована многокритериальная постановка задачи размещения ациклических графов на плоскости.

При разработке крупных программных комплексов на базе объектно-ориентированного подхода к программированию возникает проблема построения иерархической структуры программного комплекса.

Пусть объектно-ориентированная модель некоторого программного комплекса Г представлена п виде ациклического графа G = (К, Е). В общем виде - множество вершин графа С = {Г,Е), | £| - множество ребер графа G = (У,Е),

Но в применении к практической задачи построения объектно-ориентированной модели программного комплекса Р, |Г| - число классов v,eK программного комплекса Я, а |£| - число линий связей е, еЕ, которые характеризуют отношения простого наследования и множественного наследования в комплексе Р. Если класс А наследует свои свойства от класса В, то ориентированное ребро е, е Е проводится от класса В по направлению к классу А. В данной задаче необходимо расположить ациклический граф программного комплекса Р на плоскости. Такое размещение обозначим х.

Пусть дан ациклический граф G = (K,£>, Этот граф будем располагать на целочисленной решетке. Разделим множество У на подмножества ¿..¿¡.„..¿,. Пусть ii.veK, (u,v)e£, а также ueî, и vei,, а также верно, что i>j. Тогда элементы (£.,} = (£,,*,,.„,£,) будем называть уровнями разбиения множества У. Разделение множества V будем производить последовательно по уровням разбиения. А само такое разбиение {¿.¡будем называть поуровневым разбиением множества V, относящемуся к некоторому размещению Множество таких размещений * назовем множеством допустимых решений X = X{G) * {*} (MДР).

Применительно к задаче об объектно-ориентированном программировании, L, {г = ,е!^) есть подмножество множества У н представляет собой множество классов находящиеся в подмножестве L,.

Качество размещения * на графе G задается векторко-целевой функцией (ВЦФ):

fW-i^W./ÎC^^W.^w.^W./vW) |дгеДГ(, (1)

где

I) критерий симме тричного размещения графа G,

W-li\NX„-NX«\^> min, /-1

s

где №t'„, Ai,Y„- - число вершин слева и справа от линии симметрии а- на уровне Я*j 1 Lj с Lk ,

2) критерий совпадающего направления ребер,

iw

/=■,(*) = min, ДЛЯ всех J>i

где у^ - псецдобулева переменная, к = ЦЦ, i.j = ],£,

Чтобы составить целевую функцию, введем вектор Y переменных, компоненты yLl (* = i.j = ¡7^7) которого определяют результат <0 eZ.,;

Ум ='

[О, в противном случае, к = 1,/п,

т-число ребер графа G,

£к- номер уровня начала ребра et,et е Е, Lu е L, номер уровня конца ребра е..*, е Е, Lv е I, Для того чтобы оптимизировать этот критерий необходимо получить строго восходящее изображение графа G. То есть необходимо, чтобы для всех ребер графа С, конечная координата каждого ребра была больше чем начальная.

3) /^f*)-критерий минимизации площади изображения

Fj(jt) = Sw -*■ min,

s.-M'.-H,.

где ü't - ширина размещения х; Я,-высота размещения дс.

определяется как максимальная величина из мощностей множеств .....¿,,

Ж, = шахJ.....нвысота получаемого размещения ИЛ определяется

по числу уровней в размещении Н, H^l-

■Площадь изображения представим себе в виде прямоугольника, площадь которого определяется произведением ширины Wt размещения х и его высоты И,.

4) ГДх) — критерий равномерности распределения вершин по площади всего изображения.

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

5) критерий минимизации количества пересечений ребер

Fj(*)= /7, -» min , где Пк-число пересечений на размещении

Под пересечением ребер графа будем понимать случай, когда ребра имеют общую точку не в вершине графа.

6) М- критерий прямолинейности ребер

. Пусть ребро е, б Е состоит из к звеньев. Тогда если ребра прямолинейны, то угловые коэффициенты всех звеньев будут равны между собой. Введем вектор z переменных, компоненты z,jjrl {i = im, j = ijt,/"=S£|) которого определяют результат Ft(x).

2

'■*'"' 10, л противном случае.

Иначе можно сказать, что коэффициент определяет число сгибов ребра

<?, е £.

к I " ^ I / / сг где т-число ребер графа с;

число звеньев в ребре е, е к, - угловой коэффициент звена л ребра е,« Е\ . , А^Л^*-номера конечного и начального уровней знена 5 ребра Е;

„ - номера ячеек в решетке размещения графа; /- номер ребра е{ е Е.

ж М

Решением задачи (I) является где л - есть множество Парето А" по векторному Критерию ^(ЛГ) = {(Г,[же Л1}.

Во второй главе описапы алгоритмы с оценками решения многокритериальной задачи размещения ациклических графов на плоскости.

2.1. Алгоритм а, получения оптимального разбиения по критерию симметричного размещения графа.

Теорема 2.1, В неориентированном графе С'а(С',£') без точек сочленения,

мостов, кратных ребер и петель возможен только один случай = </;у, где доля встречного потока заходящего слева на конечном шаге распределения т из

вершины V*; ¿О-доля встречного потока заходящего справа на конечном шаге распределения т из вершины V'.

Следствие 2.1.1. Получаемая укладка Г для центральной вершины Vш У графа С'-((",£')оптима.1ьнапо критерию ^ симметричного размещения С',

Алгоритм л, находит па графе С' равновесную вершину у' а У и строит размещение ге Л'.

Теорема 2.2. Максимальная высота И, получаемого размещения х е -V по алгоритму а, для графа С = {У\£') для нечетного числа вершин (¡>"Ь- 2я+1) равна

Е*"|/2]+1, а для четного числа вершин (¡С'|= 2п) равна \V'\!2 + \. Максимальная ширина W, получаемого размещения хе X равиа | (-"¡-1.

Теорема 23. Алгоритм от, строит размещение х, е X графа С = ((•",£') оптимальное по первому критерию ^¡{л,), по пятому критерию Fs{дг,), И оцениваемое по второму критерию по третьему критерию

^Н,WX & Ffa) < Нпо четвертому критерию 0£ ¿"„(х,) <»У, - по шестому

критерию 0SF1(*,)s2(/i+J,i), где /;-число пар связанных вершим лежащих на одной горизонтальной линии (L = consi), Р,- число пар связанных вершин лежащих на одной вертикальной линии..

Теорема 2.4. Вычислительная сложность алгоритма а, для графа С = ((-".Я'), с длиной маршрута П равной т (количество вершин в маршруте П равно пг), берущего свое начало от вершины v('e У равна

OKUdee»,' +X№gvM'-])).|t"|)

«3

2,2. Алгоритм а;получения оптимального разбиения по критерию совпадающего направления ребер

Задачей этого алгоритма является получение оптимального восходящего изображения графа G=(f,£). Восходящим считается изображение, в котором ориентация всех ребер направлена снизу вверх.

Теорема 2.6, Алгоритм сгг строит размещение х, е X графа С = (F, Е) оптимальное по второму по пятому критериям. И оцениваемому по

первому критерию 0Si,'(*,)<»-!, по третьему критерию (л/2]3 s s и', по четвертому критерию 03 /^(дг,)< п-1 и по шестому критерию 0 s Ft(i,)s -Зп.

Теорема 2.7. Вычислительная сложность алгоритма для получения изображения ациклического графа G = (У, Е) равна 0(п т) ■*■ 0{«J)

2.3. Алгоритм а, получения оптимального разбиения по критерию прямолинейности ре^ер,

Задачей этого алгоритма является получение размещения х е X графа С = (У, £), в котором все ребра прямолинейны. Основные идея этого алгоритма — укладка вершин графа в вершины правильного «- угольника по принципу спирали.

Теорема 2.8. Алгоритм а1 строит оптимальное разбиение ациклического графа С = (У,Е) по критерию прямолинейности ребер е, е Е, I = 1,|£| Теорема 2.9, Алгоритм а3 строит размещение = {У, £') фафа С = (К,£) оптимальное по первому критерию /¡¡едпо четвертому критерию по пятому и по шестому Fi(Lxl) критериям. И оцениваемому по второму критерию Л'5(Х|)£|£|/2 и по третьему критерию ^(х,) = 3, где площадь правильного п-угольника.

Теорема 2.10. Алгоритм а7 строит оптимальное разбиение ациклического графа о * (К,Е) по критерию прямолинейности ребер е( е Е, < = 1,|£| с оценкой сложности О(п).

2.4. Алгоритмы размещения прддфрактального графа порожденного ациклической затравкой

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

алгоритм получения оптимального разбиения по критерию

симметричного размещения графа в применении к предфра ¡стальному ациклическому графу;

алгоритм а, получения оптимального разбиения по критерию совпадающего направления ребер графа в применении к предфрактальному ациклическому графу;

алгоритм а6 получения оптимального разбиения по критерию прямолинейности ребер графа в применении к предфракталыюму ациклическому графу,

В третьей главе приведены алгоритмы перемещения графических объектов графа на плоскости:

• обработка процедуры OnLB Down (С Point point);

• обработка процедуры OnMouseMove(CPoint point);

• обработка процедуры OnLBLTp(CPoint point, inl Äsize);

К графическим объектам, представленным в программном комплексе GraphDrawmgAB, относятся прямоугольники с надписями (вершины графа) и линии (ребра графа).

Процедура OnLB Down (CPoint point) осуществляет процесс перемещения графических объектов на начальном этапе и определят статус конкретного события {на каком объекте и в каком его месте она должна выполнится). Важно, что распознавание связанной структуры осуществлялось с использованием рекурсивных функций.

В процедуре OnMouseMove(CPoint point) программно обрабатываются события, которые возникают при перемещении объектов графа по плоскости. Заслуживает внимания процедура динамической перерисовки объектов графа при перетаскивании, с учетом их связности между собой.

Процедура OnLBUpfCPomt point, int &size) осуществляет процесс перемещения объектов графа на завершающем этапе. С учетом того, что переменная size передается по ссылке, эта процедура правильно устанавливает размеры перемещаемых объектов графа.

Кроме того, в программном комплексе GraphDrawingAB разработаны алгоритмы распознавания , структуры графа только нз его (рафнческого изображения.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ

1. Разработана математическая модель многокритериальной постановки размещения ациклических графов на плоскости.

2. Разработан алгоритм а, получения оптимального разбиения по критерию симметричного размещения графа.

3. Разработан алгоритм аг получения оптимального разбиения по критерию совпадающего направления ребер.

4. Разработан алгоритм at получения оптимального разбиения по критерию прямолинейности ребер.

5. Разработаны алгоритмы размещения предфрактального графа порожденного ациклической затравкой.

6. Разработаны алгоритмы перемещения графических объектов графа на плоскости.

Основные результаты изложены в 20 публикациях, в том числе в 3 работах

из перечня изданий ВАК РФ.

1. Белаш А.Н. Теория игр. Материалы IX конференции.- Ставрополь, СевКавГТУ, 2002- С.5-6.

2. Белаш А.Н. Теоретике-игровое моделирование деятельности конкурирующих компаний на рынке сбыта. Вестник Северо-Кавказского государственного технического университета. - Ставрополь, СевКавГТУ, 2003, №3 (11) - С.129-130.

3. Белаш А.Н. Теоретико-игровое моделирование получения «Графа структуры» механической системы. Вестник Северо-Кавказского государственного технического университета. - Ставрополь, СевКавГТУ, 2003; №1 (7) - С Л15-117.

4. Белаш А.Н. Теоретико-игровой подход к укладке неориентированных графов на плоскости с минимальным числом пересечений линий связей. Вестник Северо-Кавказского гуманитарно-технического института. - Ставрополь, СевКавГТИ, 2003, Выпуск 3, Том 2 -С.261-265.

5. Белаш А.Н. Использование теоретико-игрового подхода к построению плоского ориентированного графа. Материалы III научной конференции профессорско-преподавательского состава, аспирантов и студентов СевероКавказского гуманитарно-технического института. Ставрополь: СевКавП'И, 2003 - С.70-71.

6. Белаш А.Н. Описание алгоритма плоской укладки графа в линию. Материалы V Международной научно-практической конференции «Компьютерные технологии в науке, производстве, социальных и экономических процессах». Новочеркасск, ЮРГТУ, 2004 - С.25-26.

7. Белаш А.Н. Подход к определению изоморфизма неориентированных графов с равными степенями вершин. Вестник Северо-Кавказского гуманитарно-технического института. - Ставрополь, СевКавГТИ, 2004, Выпуск 4- С.260-264.

8. Белаш А.Н. Представление неориентированного графа в виде натурального числа. Первая, международная научно-техническая конференция «Иифотелекоммуникацконные технологии в науке, производстве и образовании». Ставрополь: СевКавГТУ. 2004 - С.377-378.

9. Белаш А.Н. Равновесие потоков в неориентированных графах. Первая международная научно-техническая конференция «Инфотелекоммуникацнонные технологии в науке, производстве и образовании». Ставрополь: СевКавГТУ, 2004 - С.379-382.

10.Белаш А.Н. Теоретико-игровой подход к анализу узора графа и рациональной укладки графа на плоскости. Вестник Северо-Кавказского государственного технического университета. - Ставрополь, СевКавГТУ, 2004, №8 (7) - С.85-87,

11.Белаш А.Н. Алгоритм укладки неориентированных графов в линию. Материалы VII и аучно-практи ческой конференции «Информационная безопасность». Таганрог: ТРТУ, 2005- С.19-21,

12.Белаш А.Н. Аиализ алгоритма-гамма для получения плоской уклапки неориентированных графов. Деп. в ВИНИТИ Ks 795-В2005. Ставрополь, 2005-С.1-3.

13.Белаш А.Н. Как уложить неориентированный граф в произвольную конфигурацию? Деп. в ВИНИТИ № 796-В20051Ставрополь, 2005- C.I-3. 1

И.Белаш А.Н. Теоремы о равномерном распространении потока по неориентированному графу. Дел, в ВИНИТИ Ka 794-В2005. Ставрополь, 2005-С.1-6.

15.Белаш А.Н. Многокритериальная оптимизация в задачах размещения ациклических графов. Сборник материалов Международной научно-технической конференции «Информационно-вычислительные технологии н их приложения». Пенза, МНИЦ ПГСХА, 2005 - С. 17-20.

16.Белаш А.Н. Теорема о равновесии величии встречающихся потоков в неориентированном графе. Материалы Ш Международной научно-практической конференции «Теория, методы проектирования, Программно-техническая платформа корпоративных информационных систем». Новочеркасск: ЮРГТУ,2005-С.П7-П9.

17.Белащ А.Н., Чипига А.Ф, Программа обработки неориентированных графов GraphDrawi rgA В. Интеллектуальная собственность. Авторское право и смежные права. Свидетел ьство№2005611236. Москва, 2005.

18.Белаш А.Н., Кочкаров A.M. Способ решения задачи объектно-ориентированного программирования программного комплекса, "Вестник Северо-Кавказского государственного технического университета, — Ставрополь, СевКавГТУ, 2Ó06, №2 (7) - С.73-75.

19.Белаш А.Н. Алгоритм построения оптимальной по длине н ширине укладки ациклического графа. Сборник трудов второй международной научно-практической конференции "Исследование, разработка и применение высоких технологий в промышленности", Санкт-Петербург: Политехи, ун-т, 2006 -С. 102-103.

20.Бслаш А.Н., Чипига А.Ф. Построение структурного графа механической системы па плоскости. Известия высших учебных заведений. Северокавказский регион. Технические науки. - Новочеркасск, 2006, №1(!33) — С. 1013.

Подписано в печать 21.11.2006 г. Формат 60x34 1/16 Усл. печ. л. - 1,25 Уч.- излл,- 0,83 Бумага офсетная. Печать офсетная. Заказ 742 Тираж ЮОэк.). ГОУ ВПО «Северо-Кавказский государственный технически университет» 355029 ('.Ставрополь, пр, Кулако&а, 2

Издательство Северо-Кавказского государственного технического университет Отпечатано в типографии СевКпвГТУ

Оглавление.

Введение.

Глава 1. Многокритериальная постановка задачи размещения ациклических графов на плоскости.

1.1. Описание задачи размещения ациклических графов на плоскости.

1.2. Математическая модель задачи размещения ациклических графов на плоскости.

Глава 2. Алгоритмы с оценками решения многокритериальной задачи размещения ациклического графа на плоскости.

2.1. Алгоритм от, получения оптимального разбиения по критерию симметричного размещения графа.

2.2. Алгоритм аг получения оптимального разбиения по критерию совпадающего направления ребер.

2.3. Алгоритм а3 получения оптимального разбиения по критерию прямолинейности ребер.

2.4. Алгоритмы размещения предфрактального графа, порожденного ациклической затравкой.

Глава 3. Алгоритмы перемещения графических объектов графа на плоскости.

Актуальность темы

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

Автоматическое размещение графов - это задача конструирования геометрического представления графа, удовлетворяющего набору эстетических критериев. В последние пятнадцать лет эта проблема подвергается интенсивному изучению. Было опубликовано большое количество работ по рисованию графов, а с 1993 года проводятся ежегодные конференции по данной тематике [21].

В диссертационной работе впервые сделана многокритериальная математическая постановка задачи о размещении ациклических графов на плоскости, а также разработаны и математически сформулированы алгоритмы с оценками величин получаемых оптимизационных критериев задач размещения ациклических графов на плоскости, чтобы в конечном итоге решить практическую задачу построения объектно-ориентированной модели программного комплекса, и разработан, а также зарегистрирован программный комплекс GraphDrawingAB [26].

В работе на примере многокритериальной задачи размещения ациклических графов на плоскости продемонстрирована связь и переход от математической модели к исследованию многокритериальной задачи, сформулированной при построении модели [26].

Цели работы

Построение и исследование математической модели реализации крупного научно-исследовательского проекта, состоящего в представлении объектно-ориентированной модели крупного программного комплекса, с последующим ее сведением к многокритериальной задаче размещения ациклических графов на плоскости.

Исследование свойств ациклических графов, возникающих в многокритериальной задаче их размещения на плоскости.

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

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

Методы исследования

Все исследования, проведенные в работе, используют методы и подходы дискретной математики и теории графов в частности. Аппарат теории графов наилучшим образом подходит для формального представления задач, связанных с изменением и преобразованием дискретных объектов, какими являются структуры систем [36].

Научная новизна

Построение многокритериальной задачи о размещении ациклических графов. Исследование этой задачи в применении к проблеме представления на плоскости объектно-ориентированной модели крупного программного комплекса.

Улучшение временной трудоемкости известных алгоритмов для нахождения решения классической задачи размещения ациклических графов на плоскости, построение новых алгоритмов.

Теоретическая значимость работы

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

Практическая ценность

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

Положения, выносимые на защиту

1. Математическая модель многокритериальной постановки размещения ациклических графов на плоскости.

2. Алгоритм получения оптимального разбиения по критерию симметричного размещения графа.

3. Алгоритм а2 получения оптимального разбиения по критерию совпадающего направления ребер.

4. Алгоритм от, получения оптимального разбиения по критерию прямолинейности ребер.

5. Алгоритмы размещения предфрактального графа порожденного ациклической затравкой.

6. Алгоритмы перемещения графических объектов графа на плоскости.

Апробация работы

Основные результаты работы докладывались на следующих научно-технических конференциях: V Международной научно-практической конференции «Компьютерные технологии в науке, производстве, социальных и экономических процессах». Новочеркасск, 2004; I Международной научно-технической конференции «Инфотелекоммуникационные технологии в науке, производстве и образовании». Ставрополь, 2004; Международной научно-технической конференции

Информационно-вычислительные технологии и их применение». Пенза, 2005. III Международной научно-практической конференции «Теория, методы проектирования, программно-техническая платформа информационных систем». Новочеркасск, 2005. VII Международной научно-практической конференции «Информационная безопасность». Таганрог, 2005. II Международной научно-практической конференции «Исследование, разработка и применение высоких технологий в промышленности». Санкт Петербург, 2006.

Личный вклад автора

Обосновано применение ациклических графов для представления объектно-ориентированной модели программного комплекса.

Разработаны алгоритмы с оценками и программный комплекс GraphDrawingAB получения оптимального размещения ациклического графа по различным критериям оптимальности.

Разработаны алгоритмы и программный комплекс GraphDrawingAB корректного перемещения графических объектов графа по плоскости изображения.

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

• описание задачи размещения ациклических графов на плоскости;

• математическая модель задачи размещения ациклических графов на плоскости.

Во второй главе диссертации приведены алгоритмы решения многокритериальной задачи размещения ациклических графов на плоскости:

• алгоритм of, получения оптимального разбиения по критерию симметричного размещения графа;

• алгоритм а2 получения оптимального разбиения по критерию совпадающего направления ребер;

• алгоритм аъ получения оптимального разбиения по критерию прямолинейности ребер;

• алгоритмы размещения предфрактального графа порожденного ациклической затравкой.

В третьей главе диссертации описаны алгоритмы перемещения графических объектов графа на плоскости:

• обработка процедуры OnLBDown(CPoint point);

• обработка процедуры OnMouseMove(CPoint point);

• обработка процедуры OnLBUp(CPoint point, int &size).

Далее мы сконцентрируем свое внимание на изображении ациклических орграфов (дэгов). Выбор этого подкласса для рисования можно объяснить двумя причинами. Во-первых, преимущественное большинство реальных графов, встречающихся в программировании, являются ациклическими, а во-вторых, любой ориентированный (и тем более неориентированный) граф может быть преобразован в ациклический орграф путем смены или задания ориентации у части его ребер [29,35].

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

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

Если в набор входит алгоритм, имеющий квадратичную сложность, то нет смысла экономить на решении задач других этапов, применяя к ним линейные, но плохие эвристики [14].

Методы, основанные на поуровневом размещении (иерархический подход), хотя и не являются лидерами по всем эстетическим критериям, однако значительно опережают конкурентов на больших графах, возникших в реальных приложениях [10,30].

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

Существуют несколько различных техник размещения ациклических графов, каждая из которых ставит во главу угла один или несколько из перечисленных эстетических критериев и старается в меру возможностей удовлетворить оставшиеся критерии [28,31].

Например, можно решать задачу размещения ациклических графов сведением их к планарному графу и дальнейшему построению выпуклого изображения, используя особенности топологии планарных графов, с последующим восстановлением изначальной структуры. Так, например, хорошо изучена задача построения выпуклого изображения для планарных ациклических .у/ -графов, то есть графов, имеющих одну входную и одну выходную вершины, а также планарную укладку, в которой дуга, соединяющая эти вершины, лежит во внешней грани. Они допускают монотонное изображение с прямолинейными ребрами, внешняя грань которого есть заданный треугольник. Изображение в этом случае строится рекурсивно, путем выделения специальным образом -подграфов с меньшим множеством вершин, чем у исходного, и применения алгоритма к ним. При таком подходе, когда фиксируется внешняя грань и дуги изображены прямыми линиями, с возрастанием степеней вершин углы между смежными ребрами быстро уменьшаются, что сильно понижает читаемость изображения. Существует общий метод сведения произвольного планарного ациклического графа к 5/ -графу с сохранением планарности, однако само требование планарности исходного графа является слишком жестким. С одной стороны, задача удаления минимального количества ребер произвольного ациклического графа так, чтобы сделать граф планарным, является М'трудной, а с другой - не слишком подходит нашим целям, поскольку нарушает саму структуру исходного графа [21,29].

Задачу автоматического размещения ациклических графов можно также решать с помощью ортогональных техник, которые широко используются для графов произвольного вида и имеют хорошие временные показатели. Основным недостатком данного подхода является то, что теряется возможность отражения иерархичности графа, к тому же размещения, полученные с использованием ортогонального подхода, более разряжены, чем, например, плоские размещения, и соответственно имеют большую площадь, что понижает удобность изучения структуры графа. Следует отметить также, что при ортогональном подходе при изображении орграфов степени вершин более 4-х возникает проблема с появлением существенного разброса в размерах вершин. Дело в том, что у вершины для размещения инцидентных ей ребер, число которых превышает 4, требуется увеличить размер изображения, что может привести к одновременному наличию и слишком больших, и совсем маленьких вершин [21].

Для построения изображения дэгов наиболее широко применяется так называемый иерархический подход, который направлен на получение их поуровне-вого размещения. Данный подход является крайне интуитивным и позволяет для произвольного ациклического орграфа построить монотонное поуровневое представление с ребрами в виде ломаных или сплайнов в процессе последовательного решения следующих трех задач: распределение вершин по уровням так, чтобы все дуги следовали одному направлению [21]; выбор порядка вершин на уровне с целью минимизации пересечений ребер определение координат вершин на уровне с целью минимизации общей длины ребер и количества изломов [28].

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

Для успешного применения иерархического подхода система изображения графов (исходные данные, визуализирующая компонента, область применения) должна удовлетворять следующим ограничениям: исходный граф должен быть ациклическим мультиграфом или мультигра-фом, близким к ациклическому. Близость здесь следует понимать в том смысле, что смена ориентации малого количества дуг должна превратить граф в ациклический [21]; семантика графовой информации должна предполагать возможность построения монотонного изображения, подчеркивающего направленность или наличие некоторого порядка на множестве вершин [21]; система визуализации не должна предполагать проведение только прямолинейных ребер между вершинами графа. Ребра должны быть изображены в виде ломаных или сплайнов [48,14].

Канонически метод поуровневого изображения состоит из трех последовательно применяющихся шагов: распределение вершин по уровням. Каждой вершине и присваивается число Ци), указывающее уровень этой вершины, так, чтобы все дуги, соединяющие вершины, следовали от меньшего номера к большему, при этом вершины одного уровня не должны быть связаны между собой. Подразумевается, что все вершины одного уровня будут расположены на одной прямой - вертикальной или горизонтальной, - в зависимости от того, какое мы предпочитаем общее направление размещения: сверху вниз или слева направо. После проведения распределения вершин по уровням просматриваются все дуги: если дуга с = (//,v) проходит через несколько уровней, то есть /.(»)-L(v) > 1, то она удаляется из графа и заменяется на цепочку фиктивных вершин г,,.,^, каждая вершина V, соединена дугой с г,,, и ¿0'|+1) = ЗД + 1,а V, = у и \'к =« [16]; определение порядка вершин на уровне. Задача данного шага состоит в сортировке вершин на каждом из уровней. Порядок вершин определяет топологию конечного изображения и должен быть выбран с целью минимизации пересечений ребер графа [21]; определение координат вершин на уровне. На данном этапе каждой вершине присваивается вертикальная координата (при размещении в горизонтальном направлении) так, чтобы сохранить порядок вершин на уровне, который был вычислен на предыдущем шаге. Координата выбирается с целью минимизации общей длины ребер и количества изломов. Наконец, конечное изображение получается представлением каждого ребра в виде прямолинейного отрезка и удаления фиктивных вершин. В этом случае длинные ребра оказываются изображенными в виде ломанных [10,28].

Некоторые исследователи склонны выделять задачу проведения ребер в отдельный этап алгоритма. Это целесообразно делать, если ребра изображаются не каноническими ломаными а например сплайнами. Существуют эффективные методы проведения сплайнов, не пересекающих вершины графа и проходящих через заданные области плоскости [10,28].

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

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

Иерархический подход оказывается не очень удачным с точки зрения построения инкрементального размещения. Этот факт можно объяснить тем, что топология получаемого изображения очень сильно зависит от выделенной на первом шаге алгоритма иерархии вершин. А даже при локальных изменениях графа, как-то: удаление или добавление вершин, групп вершин или ребер, - не удается сохранить эту иерархию неизменной. Вопросы инкрементального размещения очень тесно переплетены с вопросами удовлетворения ограничений на получаемое изображение. В качестве ограничений, которые могут быть удовлетворены при таком подходе, можно назвать требование разместить две выделенные вершины с одного уровня иерархии как можно ближе друг к другу, а также выравнивание вертикальных координат вершин с разных уровней иерархии [10].

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

Задачей распределения вершин по уровням является присваивание каждой вершине ее конечной горизонтальной координаты. Для этого исходный ациклический граф G = (V,Е) должен быть приведен к поуровневому ациклическому графу. Поуровневое разбиение есть разделение V на подмножества i,,/,,,.,/.,,, так, что для каждого ребра {и,у) е Е, где и е Ци V <= , верно то, что /' > /. Высотой разбиения будем называть количество уровней А, а шириной и - число вершин на самом большом уровне. Зазором ребра (и,у), где иеЦ и уеназывается разность /'- /.

Разбиение называется сжатым, если не существует ребра с зазором, большим единицы. После разбиения вершин по уровням всем вершинам одного уровня присваивается одна горизонтальная координата, то есть Гх=/ для всех вершин с уровня Л, [48].

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

Рисунок 1 - Пример графа, не имеющего сжатого изображения

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

Для построения сжатого разбиения произвольного ациклического графа применяется техника вставки фиктивных вершин (рис. 2). Фиктивные вершины добавляются в граф вдоль длинных ребер, то есть ребер с зазором, большим единицы. Для каждого такого ребра (и,V), иеЬ, и с зазором А-= /'-./> 1 добавляется к-1 вершин икл, таких, что итеЦп [14].

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

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

Рисунок 2 - Вставка фиктивных вершин

Можно сформулировать набор критериев, которые стоит принимать во внимание при построении поуровневого разбиения [21].

Во-первых, искомое размещение графа должно быть компактным. Поскольку площадь фактически зависит только от количества уровней и максимального количества вершин на одном уровне, то компактизации можно добиться уменьшением одной из этих величин. При этом высота графа оказывается ограниченной снизу длиной максимального пути в графе. Существуют простые методы, позволяющие достичь нижней оценки на высоту разбиения, однако минимизация ширины есть ЫР-трудная задача, которая в реальных системах может быть решена только приближенно. В связи с этим различием необходимо учесть, что предпочтение выбора величины для минимизации зачастую определяется на уровне визуализирующей системы. Если вершины графа изображаются не просто точками, а областями на плоскости, причем имеющими некоторые текстовые надписи, то при горизонтальной укладке наиболее важной становится высота разбиения, а при вертикальной - ширина. Это может быть еще одним хорошим поводом для использования горизонтального следования уровней в изображении графа [48].

Следующий важный критерий к разбиению вершин - это минимизация количества вершин. Такое желание связано с тем, что введение фиктивных вершин повышает общую сложность алгоритма. Если мы рассматриваем достаточно плотный граф, в котором длинных ребер (){N), то после их удаления мы получим ("ДАТ2)фиктивных вершин. Немаловажно также и то, что чем больше мы вводим фиктивных вершин, тем больше получится в конечном размещении изломов на дугах. Таким образом, кроме минимизации общего числа вершин необходимо минимизировать максимальную длину ребра, то есть число фиктивных вершин, заменяющих одну дугу, потому что чем длиннее ребро и чем больше на нем изломов, тем сложнее при изучении изображения проследить соответствующую связь в графе. Ну и поскольку сложность всех шагов алгоритма размещения графа зависит от общего количества вершин, то мы должны стремиться к тому, чтобы не слишком увеличить это количество при добавлении фиктивных вершин. К сожалению, одновременная минимизация высоты разбиения и количества фиктивных вершин уже оказывается NP-трудной задачей [28].

Поуровневое размещение иногда должно учитывать ограничения, налагаемые семантикой исходного графа. Так, в некоторых приложениях часть вершин оказывается предраспределениой по уровням. Это предраспределение может быть вызвано желанием выделить некоторые вершины или явно указать последовательность появления вершин (time-lines). Чаще всего такая задача может быть сведена к исходной путем предварительного слияния вершин с одинаковым предопределенным рангом [14].

Распределение по длиннейшему пути позволяет разместить их по уровням так, чтобы высота получающегося разбиения оказалась минимальной. Для этого надо поместить все строки (вершины без выходящих дуг) на уровень , а каждую оставшуюся вершину - на уровень Lptl, где р- длина наибольшего пути от этой вершины до ближайшего стока [35,36].

Следует отметить, что данный способ построения разбиения является инвариантным относительно направления дуг. При построении разбиения от стоков мы получим граф со всеми стоками, расположенными на одном уровне, но аналогичным образом разбиение можно построить и от источников (вершин без входящих дуг), и при этом все источники будут расположены на одном уровне. Очевидно, что высота обоих разбиений будет одинакова, однако ширина может отличаться на сколь угодно большую величину (рис. 3). Поскольку данный алгоритм является линейным, то представляется разумным построить оба разбиения и выбрать из них наименее широкое [14].

Основной недостаток распределения по длиннейшему пути - это отсутствие оптимизации на ширину разбиения [14].

Рисунок 3 - Два способа распределения по методу длиннейшего пути

К сожалению, задача нахождения разбиения с минимальной шириной и при этом с ограниченной высотой является ЫР-полной. ЫР-полнота задачи следует из сведения к ней известной ЫР-полной задачи составления расписания для мультипроцессора. Каждая вершина ациклического графа может представлять работу, которая может быть выполнена на любом из процессоров за единичное время. Ребро графа представляет ограничение предшествования на выполняющиеся работы. Составления расписания для мультипроцессора есть распределение работ по И^ процессорам так, чтобы все они могли быть выполнены за время, не превосходящее Н. Понятно, что такое расписание существует, если есть графа по уровням с высотой, не большей Н, и шириной, не большей IV [48].

Эквивалентность задачи поуровневого разбиения задаче составления расписания для мультипроцессора позволяет сразу же воспользоваться результатами, достигнутыми в этой области. Существует ряд эвристик для решения задачи составления расписания, и эти эвристики могут быть применены к нашей задаче. Например, известная эвристика Кофман-Графама позволяет построить разбиение шириной IV, и при этом его высота не будет превосходить (2-2!\У)1гтт, где Итт-минимально возможная высота разбиения шириной IV [35].

Стоит заметить, что минимизируемая данными способами ширина разбиения может оказаться все равно неудовлетворительной, поскольку алгоритм не учитывает последующую вставку фиктивных вершин. В полученном графе могут оказаться уровни с огромным количеством ребер, идущих через них, и эти ребра будут заменены фиктивными вершинами, что расширит такие уровни. Однако, учитывая то, что в конечном изображении графа фиктивные вершины будут снова заменены ребрами, можно сказать, что данный способ построения разбиения является вполне приемлемым, если ширина дуг графа мала по сравнению с размерами вершин. В противном случае предлагаются модификации эвристики Кофман-Графама, учитывающие ширину, «приносимую» фиктивными вершинами [26].

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

-/,,,, где (m,v)- ребро с ограничениями: иуУ,Е

Lv-Lv>\

I4;,LV> 1.

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

После построения поуровневого разбиения встает задача определения порядка расположения вершин на каждом уровне нашего графа. Нахождение такого распределения с целью минимизации количества пересечения ребер и есть задача данного этапа алгоритма [28].

В первую очередь стоит отметить, что количество пересечений ребер в по-уровневом графе не зависит от конечных координат вершин, а зависит только от их относительного положения внутри каждого уровня. Таким образом, задача данного этапа является не геометрической, а всего лишь комбинаторной. Однако эта задача является NP-полной уже для графа, имеющего всего лишь два уровня, и, более того, NP-полной эта задача остается, даже если есть всего лишь одна вершина со степенью, большей единицы на каждом из уровней [30,21].

Задачу минимизации пересечений ребер как в случае двух уровней, так и глобальную, можно естественным образом сформулировать в виде задачи целочисленного программирования. Однако, несмотря на возможность при использовании такой формулировки получения точного решения исходной задачи, такой подход может быть применен только для очень маленьких графов. Практические реализации показывают, что в разумное время решение задачи может быть найдено лишь для графов, содержащих не более 15 вершин (в случае глобальной оптимизации) и не более 60 вершин для каждого из уровней (в случае минимизации пересечений лишь для двух соседних уровней) [16].

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

• выбору способа фиксации уровней. При рассмотрении двух смежных уровней положение вершин на одном из уровней можно считать фиксированным и выбирать оптимальное расположение вершин другого уровня. Возможно также фиксирование положения вершин уровней при рассмотрении уровня Ц [10];

• выбору порядка, в котором просматриваются пары соседних уровней. Уровни могут просматриваться слева направо или наоборот, возможно также чередование направлений просмотра [10];

• выбору критериев окончания просмотров. Это может быть фиксированное количество просмотров или же просмотры делаются, пока они уменьшают или существенно уменьшают общее количество пересечений [10].

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

Существует ряд методов, позволяющих решать задачу минимизации количества пересечений для двух уровней [30].

Пусть имеется двудольный граф О = (/,,,/,2,£), где Ц - множество вершин первого уровня, 12- вершины второго уровня, Е- множество ребер. Па основе фиксированного расположения вершин на первом уровне строится расположение вершин на втором уровне. Как уже было сказано, данная задача является ЫР-полной, и для нахождения ее приближенного решения используются следующие эвристики [29].

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

Понятно, что заданное таким образом отношение не может образовывать отношение линейного или частичного порядка. В противном случае обычная сортировка вершин решила бы нашу ЫР-полную задачу, по крайней мере, за квадратичное время. Иллюстрирует данное замечание следующий пример. На рисунке 4 изображены два уровня иерархии с целью определения набора отношений между вершинами А, В, С.

Рисунок 4 - Расположение вершин на двух соседних уровнях

Однако закон трихотомии (для пары (А,В) справедливо одно и только одно из соотношений А < В, А = В, А > В) для нашего отношения выполняется. А это означает, что возможна устойчивая сортировка вершин, то есть сортировка, при которой выполняются условия упорядоченности и устойчивости [21].

Выполнение такого упорядочивания и составляет суть методов, основанных на сортировке. Такие методы должны быстро считать потенциальное количество пересечений. Это может быть сделано напрямую за 0(|£|2), а незначительными усилиями убыстрено до 0(^Сил.), где Сиу- количество пересечений, образуемое парой вершин и и у. Подобный подсчет возможных пересечений для каждой пары нужно выполнить лишь один раз - это и задаст порядок на множестве вершин. Дальнейшая сортировка не изменит установившихся между вершинами отношений [21].

Первый из таких алгоритмов похож по своей идее на метод пузырька. Предлагается просматривать поочередно все пары соседних вершин и менять их местами, если при этом уменьшается количество пересечений. Процесс заканчивается, когда после очередного полного просмотра всех вершин второго уровня количество пересечений не уменьшилось (неупорядоченная пара не была найдена). Сложность данного алгоритма - 0{\Ь2\2), так как для конечного упорядочивания может потребоваться вплоть до \1г\ просмотров. Результат работы такого алгоритма сильно зависит от выбора начального расположения, так как оперирует перестановками только в терминах соседних вершин [53].

Другой метод, позволяющий упорядочить множество вершин, основан на идее быстрой сортировки. Сначала выбирается «средняя» вершина, а все остальные вершины разбиваются на два множества в зависимости от того, в каком огч ношении они находятся с выбранной вершиной. Затем подобная процедура рекурсивно применяется к каждому из получившихся множеств. В худшем случае временная сложность данного алгоритма так же, как и алгоритма быстрой сортировки, является квадратичной, однако в среднем алгоритм требует всего лишь 0(\L21log|/.21) операций [48,26].

Идея следующего метода тоже использует концепцию сортировки вершин на уровне, хотя явно не прибегает при этом к заранее установленному отношению порядка на множестве вершин. Метод под названием «отсев» (sifting) на каждом шаге берет одну из вершин и пытается ее вставить в такое место, чтобы породить при этом наименьшее количество пересечений ребер. Для этого вершину пытаются последовательно вставить в каждое из возможных мест и считают количество получившихся пересечений. Поскольку при сдвиге вершины на одну позицию изменение количества пересечений можно посчитать за константное время (используя предварительно накопленную информацию), то алгоритм имеет квадратичную временную сложность и по своей сути похож на сортировку вставками [48].

Как уже было отмечено, любой основанный на сортировке алгоритм упорядочивания вершин, должен работать с набором отношений между парами вершин, и вычисление этих отношений не может быть выполнено за линейное время. Поэтому любой из упомянутых методов будет тоже иметь нелинейную сложность [29].

На практике наиболее широко используются линейные алгоритмы, основанные на методе барицентров. Координата вершины \>eLz определяется как-среднее арифметическое координат всех ее связей с уровня /,,: где = {уеГ:(и,у)€/•:}.

Если после перестановки координаты каких-либо двух вершин совпадают, то они разносятся на минимальное расстояние, порядок при этом определяется произвольно. Самая распространенная модификация этого метода - метод медиан, где вместо среднего арифметического используется координата среднего соседа с уровня /,,, то есть если и^и2,.,ит е Л,- вершины смежные г, причем х, (//,)< х, (и, )<.<х, («„,), тогда координата х2(у) = тесКу)определяется как х,), где а\% = т/2. В случае, когда тей(у) = тес!(и) и \> имеет нечетную степень, а и-четную, то V ставится перед и; если же четность степеней совпадает, то порядок выбирается произвольно. Для каждой вершины и значение ее медианы может быть найдено за время 0(|ЛГ(«)| , что делает эту эвристику настолько же быстрой, как и метод барицентров [14,10].

Пусть минимально возможное число пересечений ребер для данного графа, где х, - расположение вершин /„,, число пересечений, остающихся после применения метода барицентров, тсс1(0,хх)- число пересечений, остающихся после применения метода медиан.

Сформулируем ряд утверждений:

Утверждение 1. Если для данного графа О возможно размещение без пересечения ребер, то и метод медиан, и метод барицентров его находят, то есть если размещение х, такое, что ор1(0,х]) = О, тогда а\^{0,хх) = тес1(С,х]) = О.

Утверждение 2. Для любого п существует двудольный граф <7 - (/.,, Л2, Е), где |А|| = //, |/>:| = 2, и размещение х, вершин Л, такие, что о\^(0,х1)/ор1(0,х]) пропорционально п1'2.

Утверждение 3. Для любого п существует двудольный граф О = (/.,,/.,,/-;), где \1'г\ = п, |^2| = 2> и размещение х, вершин /,, такие, что тЫ (Gх() / ор1 ((/', х,') > 3-0(1///).

Утверждение 4. Для двудольного графа G = (L],L2,Ii) и любого размещения х, вершин Л, верно неравенство med{G',x[)<2-opt{G',x\), если все вершины Л, не имеют более трех ребер [21].

Известны также следующие модификации метода медиан: средние медианы, когда для вершин с четной степенью присваивается среднее арифметическое значение позиций вершин с соседнего уровня, и пЫ(и)-для нечетных степеней [21]; полумедианы, когда для вершин с четной степенью в качестве значения медианы берется значение, полученное по методу барицентров [21]; взвешенные медианы, когда происходит уточнение метода средних медиан в случае вершин с четной степенью, большей двух. В этом случае взвешенная медиана определяется как теа(и) =----- , left + right где lefi = xl(vjl2)-xl(vl) и right = xl(vj)-x1(v;/2+1). Такая стратегия сдвигает вершины к той стороне, где ее соседи располагаются наиболее плотно [30,48].

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

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

Аргументация такого подхода состоит в том, что визуальное восприятие запутанности графа и количества пересечений ребер зависит не только от самого числа пересечений, но и от их взаимного расположения. Авторы подхода утверждают, что полученные таким образом представления выглядят зачастую даже лучше, чем представления, имеющие действительно минимальное количество пересечений ребер [35,36].

Несмотря на ^-полноту задачи в такой постановке (в силу ЫР-полноты задачи минимизации удаляемых дуг при получении планарного двухуровневого графа), ее несомненным преимуществом перед задачей минимизации пересечений является наличие хороших эвристик для нахождения решения с гарантированной оценкой худшего случая. Сама задача нахождения минимального числа дуг для нахождения планарного двухуровневого ациклического графа естественным образом формулируется в виде задачи линейного целочисленного программирования, позволяя для небольших графов находить ее точное решение [87].

Существуют другие эвристики расположения вершин на втором уровне. Суть алгоритма вероятностной эвристики заключается в «жадной» вставке вершин на основе предварительно подсчитанной для каждой вершины вероятности образования пересечений. Такая вероятность определяется суммой пересечений для каждого из ребер, инцидентных данной вершине в полном двудольном графе [14].

Алгоритм Тутти состоит в предварительном определении позиций вершин на двух крайних уровнях с последующим решением системы разряженных линейных уравнений: х(и) =-!— У *(»')+—-— для определения координат вершин на всех промежуточных уровнях.

Данная эвристика позволяет свести задачу к известной задаче о назначениях. Для каждой вершины определяется число с1ц как верхняя оценка количества пересечений, образованных ребрами, инцидентными вершине /, в том случае, если вершину поместить на место }. Как и в вероятностной эвристике, ^ вычисляются путем дополнения графа до полного. Далее для матрицы 1) = (Ли) решается задача о назначениях, то есть выбирается п элементов так, чтобы покрыть ими каждую колонку и каждый столбец матрицы и при этом минимизировать сумму их значений [14].

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

После определения порядка вершин на уровне необходимо определить их настоящие вертикальные координаты. Канонически, в иерархическом подходе, ребра графа изображаются в виде ломаных с точками излома, находящимися в фиктивных вершинах, поэтому задача определения окончательных координат всех вершин одновременно является и задачей проведения ребер. Если же ребра графа имеют какую-либо другую форму и/или способ проведения, то соответствующие критерии должны быть рассмотрены при решении задачи о постановке вершин [26].

В случае изображения ребер в виде ломаных задача определения окончательных координат вершин решается из соображений минимизации числа изломов в проводимых затем ребрах. При этом должен быть учтен и не нарушен порядок следования вершин на каждом из уровней. В такой постановке задача формализуется следующим образом. Пусть у нас есть путь р = (\\,г2,.,\>к) , в котором вершины являются фиктивными. Если бы такой путь был изображен прямолинейным отрезком, то для /от 2 до к-1 должно выполняться равенство углов наклона отрезков ломаной к -1

Затем, определяя функцию я{р) как

1-2 я, = о'о'л■)- ж )) + >•(»',), к -1 мы можем попытаться глобально минимизировать суммарное отклонение от прямолинейности: р учитывая ограничение >'(и')~Ж)><7Для всех пар вершин, расположенных на одном уровне так, что вершина н- расположена выше вершины г . В этом случае </ будет минимально возможным вертикальным расстоянием между вершинами [48].

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

Также возможно введение дополнительных весов, которые призваны, чтобы распрямлять именно длинные ребра - как потенциальных обладателей большого количества изломов: и,г)<-.Е где со(и,\>)- мера важности спрямления ребра (//,г), 0.(и,\>)~ коэффициент для спрямления длинных ребер. Авторы подхода предлагают определить П(е) следующим образом: £Х<?)=8, если оба конца ребра являются фиктивными вершинами, С1(е)=2, если только одна из конечных вершин фиктивная, и = 1 в остальных случаях [14].

Здесь следует отметить два существенных отрицательных момента данного способа определения вертикальных координат вершин. Во-первых, решение данной минимизационной задачи с квадратичным относительно количества вершин набором ограничений может потребовать существенных временных ресурсов. Во-вторых, точное решение с красивыми прямолинейными ребрами может тем не менее оказаться никуда негодным ввиду чрезмерно разросшейся площади изображения. Для избегания разрастания ширины изображения можно усилить налагаемые на вертикальные координаты ограничения, однако это лишь увеличит сложность задачи и, возможно, элиминирует существование точного решения [48,26].

Ввиду перечисленных проблем, возникающих при попытках найти точное решение глобальной задачи спрямления ребер, на практике широко применяются эвристические подходы к решению данной проблемы [16].

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

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

Хорошие результаты могут быть получены применением методов, основанных на упругосиловой физической модели. В таких алгоритмах положение вершины определяется силами, действующими на нее со стороны других вершин через ребра «пружины» или ребра «резиновые жгуты». На такую систему накладывается ряд ограничений, для того, чтобы предотвратить чрезмерное сближение вершин и сохранение предварительно вычисленного порядка вершин на уровне. Для определения окончательных координат на уровне можно использовать метод «маятника», который интерпретирует вершины как грузы, подвешенные на ребра-струны. Далее такая система приходит в движение под действием гравитационного поля, и вершины, толкая друг друга (но не перескакивая), занимают положение, соответствующее минимуму потенциальной энергии системы [21].

Заключение

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

Проведено исследование свойств ациклических графов, возникающих в многокритериальной задаче их размещения на плоскости.

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

В первой главе производится многокритериальная постановка задачи размещения ациклических графов на плоскости. В частности, перечислены и математически формализованы критерии, которые участвуют в многокритериальной оптимизации вышеописанной проблемы. А также доказана теорема 1.1, которая состоит в том, что всякий ориентированный граф С = (У,Е) объектно-ориентированной модели программного проекта Р является ациклическим графом.

Во второй главе диссертационной работы разрабатываются алгоритмы с оценками решения многокритериальной задачи размещения ациклического графа:

• Алгоритм а, получения оптимального разбиения по критерию симметричного размещения графа;

• Алгоритм а2 получения оптимального разбиения по критерию совпадающего направления ребер;

• Алгоритм а} получения оптимального разбиения по критерию прямолинейности ребер.

В третьей главе диссертационной работы были разрабатываются алгоритмы и блок-схемы перемещения графических объектов графа.

1. Авондо-Бодино Дж. Графы гиперграфы. Париж, 1970.

2. Алгоритмы и программы решения задач на графах и сетях / Нечепуренко М.И., Поков В.К., Майнагашев С.М. и др. Новосибирск: Наука. Сиб. отд-ние, 1990.

3. Асанов М.О., Баранский В.А., Расин В.В.Дискретная математика: графы, матроиды, алгоритмы. Ижевск: НИЦ «Регулярная и хаотическая динамика», 2001.

4. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. -М.: Мир, 1979.

5. Берж К. Теория графов и ее применения. Пер. с фр. М.: Иностранная литература., 1962.

6. Валенкин Н.Я. Комбинаторика. М.: Наука, 1969.

7. Визинг В.Г. О числе ребер в графе с данным радиусом: Доклады АН СССР, 173 (1967).

8. Г.Шилдт. Самоучитель С++:/ Пер. с англ.-3-e изд. СПб.: БХВ-Петербург, 2002.

9. Гаврилов Г.П., Сапоженко A.A. Сборник задач по дискретной математике. -М.: Наука, 1977.

10. Ю.Галкина В.А. Дискретная математика: комбинаторная оптимизация на графах. М.: Гелиос АРВ, 2003.

11. П.Грин Д., Кнут Д. Математические методы анализа алгоритмов. М.: Мир, 1987.

12. Гроссман И., Магнус В. Группы и их графы. М.: Мир, 1971.

13. Гудман С., Хидетниеми С. Введние в разработку и анализ алгоритмов. М.: Мир, 1981.

14. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. -М.: Мир, 1982.

15. Донец Г.А. О нижней границе числа вершин плоских критических графов. //Кибернетика, 4 (1971), 76-85

16. Евстигнеев В.А. Применение теории графов в программировании. -М: Паука, 1985.

17. Емеличев В.А., Перепелица В.А. Сложность дискретных многокритериальных задач. //Дискретная математика. 1994. Вып. 1. - С.3-33

18. Емеличев Р., Мельников О., Сарванов В., Тышкевич Р. Лекции по теории графов. М.: Наука, 1990.

19. Зыков А.А. Основы теории графов. М.: Наука, 1987.

20. Камерон П., Дж. Ван Линт. Теория графов, теория кодирования и блок-схемы./ Пер. с англ. М.: Наука, 1980.

21. Касьянов В.Н., Евстигнеев В.А. Графы в программировании: обработка, визуализация и применение. СПб.: БХВ - Петербург, 2003.

22. Кнут Д. Искусство программирования для ЭВМ: сортировка и поиск. Т.З. -М.:Мир, 1978.

23. Комбинаторный анализ. Задачи и упражнения. Учебное пособие/ Под ред. Рыбникова К.А. М.:Наука, 1980.

24. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. М.: МЦНМО, 1999.

25. Кофман А. Введение в прикладную комбинаторику. М.:Наука, 1975.

26. Кочкаров A.M. Распознавание фрактальных графов: Алгоритмический подход. Нижний Архыз: Издательский центр «CYGNUS», 1998.

27. Кристофидес Н. Теория графов. Алгоритмический подход. Пер с англ. М. Мир. 1978.

28. Курейчик В.М. Генетические алгоритмы и их применение. Таганрог: Изд-во ТРТУ, издание второе, дополненное, 2002.

29. Курейчик В.М. и др. Комбинаторные аппаратные модели и алгоритмы в САПР /В.М. Курейчик, В.М. Глушань, Л.И. Щерабаков. М. Радио и связь, 1990.

30. Майника Э. Алгоритмы оптимизации на сетях и графах. М: Мир, 1981.

31. Мельников О.И. Занимательные задачи по теории графов.-Минск: НТООО «Тетрасистем». 2001

32. Нефедов В.Н. Осипова В.А. Курс дискретной математики. М.: МАИ, 1992.

33. Новиков Ф.А. Дискретная математика для программистов. СПб.: Питер, 2004.

34. Норенков И.П. САПР системы автоматизированного проектирования. - М., Высш. Шк., 199635.0ре О. Графы и их применение М.: Мир, 1965.

35. Зб.Оре О. Теория графов М.: Наука, 1980.

36. Препарата Ф., Шеймос М. Вычислительная геометрия М.: Мир, 1989.

37. Райзер Дж. Комбинаторная математика. М.: Мир, 1966.

38. Рейнгольц Э., Нивергельт 10., Део Н. Комбинаторные алгоритмы. Теория и практика. М.: Мир, 1980.

39. Риордан Дж. Введение в комбинаторный анализ. М.: ИЛ, 1963.

40. Рыбников К.А. Введение в комбинаторный анализ М.: МГУ, 1972.

41. Свами М. Тхуласираман К. Графы сети и алгоритмы. М.:Мир, 1984.

42. Смирнова О.М. Алгоритм автоматической раскладки диаграммы классов CASE-средства Real. СПбГУ. Дипломная работа. 2000.

43. Татт У. Теория графов/ Пер с англ. М.Мир, 1988.

44. Уилсон Р. Введение в теорию графов/ Пер с англ. М.: Мир, 1977.

45. Форд Л.Р., Фалкерсон Д.Р. Потоки в сетях. М.: Мир, 1966.

46. Харари Ф. Применение в экономике теории графов, изд-во «Прогресс». М.: 1966.

47. Харари Ф. Теория графов/ Пер с англ. В.П. Козырева. Изд. 2-е. М.: Едиториал УРСС, 2003.

48. Харари Ф., Палмер Э. Перечисление графов. М.: Мир, 1977.

49. Холл М. Комбинаторика. -М.: Мир, 1970.

50. Холл П. Вычислительные структуры. Введение в нечисленное программирование. М.: Мир, 1978.

51. Battista G., Eades P., Tamassia R., Tollis I. Graph Drawing. Algorithms for the Visualization of Graphs. New Jersey: Prentice Hall, 1999.

52. Battista G., Garg A., Liotta G., Tamassia R., Tassinari E., Vargiu F. An experimental comparison of four graph drawing algorithms // Computational Geometry, 1997, 7(5-6), pp. 303 325.

53. Behzad M.A criterion for the planarity of a total graph, Proc. Cambridge Philos. Soc.? 63 (1967)? 679-681.

54. Berge C. Two theorems in graph theory, Proc. Nat. Acad. Sci. USA. 43 (1957).

55. Bertolazzi P., Di Battista G. Optimal upward planarity testing of single source digraphs // SIAM J.Comput. 1998. - Vol. 27, N1. - P. 132-169.

56. Bertolazzi P., Di Battista G. Upward drawings of triconnected digraphs // Algorithmica. 1994. - Vol. 6, N 12. - P.476-497.

57. Biedl T. New Lower bonds for orthogonal graph drawings // Lect. Notes in Comp. Sci.- 1996. Vol. 1027. P.28-39.

58. Biedl T. Orthogonal graph visualization: The three-phase method with applications. PhD thesis, RUTCOR, Rutgers University, May 1997.

59. Biedl T., Kant G. A better heuristic for orthogonal graph drawings // Lect. Notes Comput. Sci. 1994. - Vol. 855,- P. 24-35.

60. Biedl T., Kaufmann M. Area-efficient static and incremental graph drawings // Lect. Notes Comput. Sci. 1997. - Vol. 1284. - P. 37-52.

61. Brown E., Johnson L. A class of planar four colorable graphs. Israel J. Math., 11 (1972)/

62. Cai J., Han X. An 0(m log n)- time algorithm for the maximal subgraph problem//SIAM J.Comput.- 1993,-Vol.22-P. 1142-1162.

63. Chan T. Optimizing area and aspect radio in straight-line orthogonal tree drawings // Lect. Notes Comput. Sci. 1997. - Vol. 1190. - P.63-75.

64. Chiba N., Nishizeki T. A linear algorithm for embedding planar graphs using PQ-Trees // J. Comput. Syst. Sci. 1985. - Vol. 30, N 1. - P. 54-76.

65. Cliiba N., Nishizeki T. Drawing planar graphs nicely // Acta Inform. 1985. - Vol. 22.-P. 187-201.

66. Chrobak M. A linear-time algorithm for drawing planar graphs // Inform. Process. Lett.- 1995,-Vol. 54.-P.241-246.

67. Chrobak M. Convex drawings of graphs in two and three dimensions // Proc. 12th Annu. ACM Sympos. Comput. Geom. 1996. - P.319-328.

68. Chrobak M. Minimum-width grid drawings of Plane Graphs // Lect. Notes Comput. Sci. 1995. -Vol. 894.-P. 104-110.

69. Cvetcovic D., Rowlinson P., Simic S. Eigenspaces of graphs. Cambridge university press. 1997

70. De Fraysseix H. A depth-first-search characterization of planarity // Ann. Discrete Math.-1982.-Vol. 13.-P.75-80.

71. De Fraysseix H. How to draw a planar graph on a grid // Combinatorica- 1990-Vol.10-P.41-51.

72. Di Battista G. Algorithms for plane representation of acyclic graphs // Theoret. Comput. Sci. 1998,- Vol. 61.-P.175-198.

73. Di Battista G. Algorithms for visualization of graphs Prentice Hall, 1999.

74. Di Battista G. Area Requirement and Symmetry Display of Planar Upward Drawings //Discrete Comput. Geom. 1992.-Vol. 1.- P.381-401.

75. Di Battista G. Incremental planarity testing // Proc. 30th Annu. IEEE Sympos. Found. Comput. Sci. 1989,- P. 436-441.

76. Djidjev H. A linear algorithm for the maximal planar subgraph problem // Lect. Notes Comput. Sci. 1995.

77. Drawings graphs: Methods and Models / Kaufmann M. Springer, 2001 - (Lect. Notes in Comput. Sci.; Vol. 25).

78. Formann M. Drawing graphs in the plane width high resolution // SIAM J. Comput-1993,- Vol.22.- P. 1035-1052.

79. Frutcherman T., Reingold E. Graph Drawing by Force-directed Placement // Software Practice and Experience, 1991, vol. 21, pp. 1129-1164.

80. Garey M.R., Johnson D.S. Crossing number is NP-complete // SIAM J. Algebraic Discrete Methods.- 1983. Vol. 4, N 3. - P. 312-316.

81. M. Eiglsperger et al., Mixed Planarization, JGAA, 7(2) 203-220 (2003)

82. Makinen E., Seiranta M. Genetic algorithms for drawing bipartite graphs // International Journal of Computer Mathematics, 1994, vol. 53, No 3, pp. 157 166.

83. Reinhard Diestel. Graph Theory. Electronic edition. Springer Verlag New York. 2000

84. Sugiyama К. Graph Drawing and Applications for Software and Knowledge Engineers. Singapore: Mainland Press, 2002.

85. Tamassia R., Battista G., Batini С. Automatic graph drawing and readability of diagrams // IEEE Transactions on Systems Man Cybernetics, 1998,18(1), pp.61-79.

86. Белаш А.Н. Алгоритм укладки неориентированных графов в линию. //Материалы VII научно-практической конференции «Информационная безопасность». Тез. докл. Таганрог: ТРТУ, 2005. - С.19-21.

87. Белаш А.Н. Анализ алгоритма-гамма для получения плоской укладки неориентированных графов. Ставрополь, Северо-Кавказский государственный технический университет, 2005. Деп. в ВИНИТИ № 795-В2005 - С. 1-3.

88. Белаш А.Н. Как уложить неориентированный граф в произвольную конфигурацию? Ставрополь, Северо-Кавказский государственный технический университет, 2005. Деп. в ВИНИТИ № 796-В2005 - С. 1-3.

89. Белаш А.Н. Теоремы о равномерном распространении потока по неориентированному графу. Ставрополь, Северо-Кавказский государственный технический университет, 2005. Деп. в ВИНИТИ № 794-В2005 - С. 1-6.

90. Белаш А.Н. Многокритериальная оптимизация в задачах размещения ациклических графов.// Сборник материалов Международной научнотехнической конференции «Информационно-вычислительные технологии и их приложения». Тез. докл. Пенза, 2005. - С. 17-20.

91. Белаш А.Н. Подход к определению изоморфизма неориентированных графов с равными степенями вершин. // Вестник Северо-Кавказского гуманитарно-технического института. Ставрополь, СевКавГТИ, 2004, Выпуск 4 - С.260-264.

92. Белаш А.Н. Равновесие потоков в неориентированных графах. // Первая международная научно-техническая конференция «Инфотелекоммуникационные технологии в науке, производстве и образовании». Тез. докл. Ставрополь: СевКавГТУ, 2004. - С.379-382.

93. Белаш А.Н. Теоретико-игровое моделирование деятельности конкурирующих компаний на рынке сбыта. // Вестник Северо-Кавказскогогосударственного технического университета. Ставрополь, СевКавГТУ, 2003, №3 (11) - С. 129-130.

94. Белаш А.Н. Теоретико-игровое моделирование получения «Графа структуры» механической системы. // Вестник Северо-Кавказского государственного технического университета. Ставрополь, СевКавГТУ, 2003, №1 (7) - С.115-117.

95. Белаш А.Н. Теоретико-игровой подход к анализу узора графа и рациональной укладки графа на плоскости. // Вестник Северо-Кавказского государственного технического университета. Ставрополь, СевКавГТУ, 2004, №8 (7) - С.85-87.

96. Белаш А.Н. Теория игр.//Материалы конференции. Тез. докл.- Ставрополь: СевКавГТУ, 2002 С.5-6.

97. Белаш А.Н. Чипига А.Ф. Программа обработки неориентированных графов GraphDrawingAB. Интеллектуальная собственность. Авторское право и смежные права Свидетельство №2005611236. Москва, 2005.

98. Белаш А.Н., Чипига А.Ф. Построение структурного графа механической системы на плоскости. // Известия высших учебных заведений. Северокавказский регион. Технические науки. Новочеркасск, 2006, №1(133) - С. 1013.

99. Белаш А.Н., Кочкаров A.M. Способ решения задачи объектно-ориентированного программирования программного комплекса. // Вестник Северо-Кавказского государственного технического университета. -Ставрополь, СевКавГТУ, 2006, №2 (7) С.73-75.126