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

• Автор: Белаш, Александр Николаевич
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2006
• Место защиты: Ставрополь
• Количество страниц: 160 с. : ил.

Оглавление
Оглавление.
Введение.

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

ациклических графов на плоскости.

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

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

плоскости
Глава 2. Алгоритмы с оценками решения многокритериальной задачи размещения ациклического графа на плоскости
2.1. Алгоритм а получения оптимального разбиения но критерию симметричного размещения графа
2.2. Алгоритм а2 получения оптимального разбиения по критерию совпадающего направления ребер
2.3. Алгоритм а3 получения оптимального разбиения по критерию прямолинейности ребер.
2.4. Алгоритмы размещения предфрактального графа, порожденного
ациклической затравкой.
Глава 3. Алгоритмы перемещения графических объектов графа на
плоскости
Заключение.
Список литературы


В качестве ограничений, которые могут быть удовлетворены при таком подходе, можно назвать требование разместить две выделенные вершины с одного уровня иерархии как можно ближе друг к другу, а также выравнивание вертикальных координат вершин с разных уровней иерархии []. Иерархический подход размещает граф по уровням, образуя монотонное изображение. Направление следования уровней может быть как горизонтальным, так и вертикальным. В реальных системах это должно определяться семантикой изображаемой информации. Так, например, для иерархий классов более привычной является вертикальная укладка, для графов вызовов - горизонтальная. Иногда в данном вопросе решающее значение имеет визуализирующая компонента или какие-либо ограничения системы. При горизонтальной укладке преимущественным направлением дуг является горизонтальное, что позволяет размещать на них длинные надписи []. Задачей распределения вершин по уровням является присваивание каждой вершине ее конечной горизонтальной координаты. Для этого исходный ациклический граф G = (Г,Д) должен быть приведен к поуровневому ациклическому графу. Поуровневое разбиение есть разделение V на подмножества Ll%L2t. J*k9 так, что Лля каждого ребра (и,г)е ? А,и V a LJ9 верно то, что / > j. Высотой разбиения будем называть количество уровней /;, а шириной и - число вершин на самом большом уровне. Зазором ребра (w,v), где uait и veLJ9 называется разность /-у. Разбиение называется сжатым, если не существует ребра с зазором, большим единицы. После разбиения вершин по уровням всем вершинам одного уровня присваивается одна горизонтальная координата, то есть Vx -i для всех вершин с уровня Л, []. Существование поуровиевого распределения для ациклических графов очевидно. Однако не для всякого ациклического графа существует его сжатое разбиение - это может быть продемонстрировано уже для графа, состоящего всего из трех вершин (рис. I). Необходимость же построения сжатого разбиения диктуется следующими двумя причинами. Во-первых, сжатое разбиение минимизирует горизонтальную длину ребер и количество их изломов. При сжатом разбиении ребра связывают вершины только соседних уровней и могут быть изображены прямолинейными отрезками. Во-вторых, сжатое разбиение существенно упрощает задачу минимизации пересечений ребер графа, которая решается па втором шаге алгоритма. Сжатое разбиение сводит эту глобальную задачу к задаче минимизации пересечений для двух соседних уровней []. Для построения сжатого разбиения произвольного ациклического графа применяется техника вставки фиктивных вершин (рис. Фиктивные вершины добавляются в граф вдоль длинных ребер, то есть ребер с зазором, большим единицы. Для каждого такого ребра (//,у), не/,, и ге/,; с зазором к-і- і> 1 добавляется к-1 вершин и,,лы,таких,что иЛе/,,_т []. Такое построение приводит к тому, что в графе остаются только ребра, соединяющие вершины соседних уровней, и задача минимизации пересечения ребер сводится к соответствующей задаче для двухуровневого случая. Ребро изображается в виде ломаной, концами которой являются сами вершины, а точками излома - вставленные на первом этапе фиктивные вершины. Таким образом, исчезает возможность пересечения ребер с вершинами [,]. Заметим также, что существуют варианты поуровневого размещения ациклических орграфов, которые не используют технику фиктивных вершин, но вынужденно уделяют дополнительное внимание вопросу проведения ребер графа. Можно сформулировать набор критериев, которые стоит принимать во внимание при построении поуровневого разбиения []. Во-первых, искомое размещение графа должно быть компактным. Поскольку площадь фактически зависит только от количества уровней и максимального количества вершин на одном уровне, то компактизации можно добиться уменьшением одной из этих величин. При этом высота графа оказывается ограниченной снизу длиной максимального пути в графе. Существуют простые методы, позволяющие достичь нижней оценки на высоту разбиения, однако минимизация ширины есть ЫР-трудиая задача, которая в реальных системах может быть решена только приближенно. В связи с этим различием необходимо учесть, что предпочтение выбора величины для минимизации зачастую определяется на уровне визуализирующей системы.