Методические указания по проведению лабораторных работ «Задачи декомпозиции графов» по курсу (стр. 1 из 3)
Нижегородский государственный университет им. Н.И. Лобачевского
Факультет вычислительной математики и кибернетики
Кафедра информатики и автоматизации
научных исследований
Методические указания по проведению лабораторных работ
«Задачи декомпозиции графов»
по курсу «Эволюционно-генетические
алгоритмы решения оптимизационных задач»
специальность «Прикладная информатика»
Н.Новгород, 2001
УДК. 681.3.015
Методические указания по проведению лабораторных работ «задачи декомпозиции графов» по курсу «Эволюционно-генетические алгоритмы решения оптимизационных задач» для студентов факультета ВМК специальности «Прикладная информатика».
/Нижегородский государственный университет, 2001, 13 c.
Методические указания содержат основные понятия из области подходов к решению экстремальных задач переборного типа на графовых структурах. Дается содержательное описание объекта исследования, строится общая математическая модель, ставятся оптимизационные задачи на графах, предлагаются алгоритмы решения поставленных оптимизационных задач. Приводится описание диалогового программного комплекса “Задачи декомпозиции графов”.
Считаю, что данное методическое пособие необходимо опубликовать по желанию авторов либо в электронном варианте, либо через типографию.
Методическое пособие подготовлено профессором Д.И. Батищевым и аспирантом Н.В. Старостиным.
Рецензент профессор, д.т.н. Гергель В.П.
Содержание
1. Содержательная постановка задачи. 4
2. Задача разбиения графа на фиксированное число подграфов заданных порядков. 5
3. Задачи оптимальной правильной раскраски графов. 6
4. Постановка бикритериальной задачи разбиения. 8
5. Подход к решению задач декомпозиции графа. 8
6. Программный комплекс по разработке графов и решению задач декомпозиции графов 10
8. Задания по лабораторной работе. 13
1. Содержательная постановка задачи
К теории графов проявляется всевозрастающий интерес, поскольку она признана эффективным аппаратом формализации научных и технических задач в различных отраслях знаний и деятельности человека, например, в вычислительной технике, автоматизации проектирования, микроэлектронике, радиоэлектронике, приборостроении, автоматике, кибернетике, медицине, биологии, генетике. Для многих задач доказано, что они являются NP-полными. Это означает, что не найдено эффективных алгоритмов, позволяющих находить точные решения. Однако такие задачи не исчезают, и по-прежнему остается проблема их решения.
Задачи подобного рода возникают при адаптивном управлении сложными системами с дискретной эволюционирующей структурой, задача структурной адаптации подобных систем, которые часто сводится к агрегации системы на заданное число подсистем таким образом, чтобы связи между подсистемами были минимальными.
Так, например, при производстве современного электронного оборудования особое место занимает разработка печатных плат и микросхем. Одной из задач, которая требует решения при их конструировании, является задача разбиения принципиальных схем устройств на составные части (подсхемы, функциональные блоки). Типовые элементы принципиальной схемы должны таким образом быть распределены по отдельным подсхемам, чтобы число внешних соединений было как можно меньше. Это необходимо с целью повышения надежности схемы, уменьшения влияния наводок, повышения технологичности и простоты конструктивного оформления.
При разработке топологии многослойных схем возникает задача распределения “конфликтующих” соединений по отдельным слоям (задача расслоения цепей). Расслоение до трассировки основано на анализе схемы соединений для выявления тех соединений или их групп, которые не могут быть расположены на одной плоскости из-за неизбежности “сложных” ситуаций трассировки. В частности, усложняется форма соединений, увеличивается их длина, растет время поиска трасс при реализации алгоритма трассировки на ЭВМ.
Поскольку эти объекты, рассматриваемых структур, представляются, как правило, графовыми моделями. Вершины, моделируют элементы систем, а ребра моделируют связи между элементами. Так, например, при компоновки микромодульных схем (или печатных плат) в качестве вершин рассматриваются типовые модули (элементы схемы), а множеству ребер графа ставится в соответствие множество соединений (проводников) схемы.
Таким образом, задачи агрегации системы формально сводится к задачам декомпозиции графа. На самом деле это не отдельная задача, а целый класс задач, объединенных общей структурой получаемых решений – это разбиения множества элементов графа на классы. Постановка задачи может варьироваться в зависимости от свойств графа, которые задаются моделируемыми объектами.
Исходным объектом для задач декомпозиции служит неориентированный граф G=(X,V). Пространством решений служит множество всевозможных разбиений графа на непересекающиеся подграфы. На разбиения графа могут накладываться ограничения D. Для различных задач, естественно, возможны различные ограничения.
Задачи декомпозиции имеют следующий набор основных критериев:
1. Число внешних соединений между подграфами
2. Число подграфов
3. Число типов подграфов
Первый критерий определяется функционалом внешних связей. Смысл второго критерия очевиден: он просто равен числу подграфов разбиения. Третий критерий зависит от характера оптимизационной задачи. Чтобы описать этот критерий, нужно задать понятие подграфа или, точнее, понятие однотипности графов. При определении однотипности графов исходят из того, что каждой вершине графа присваивается один тип из конечного набора. Математически это означает, что исходный граф хроматический, то есть его вершины раскрашены, при этом цвет вершины соответствует типу.
Постановки задач могут варьироваться в зависимости от свойств графа, которые задаются моделируемым объектом.
2. Задача разбиения графа на фиксированное число подграфов заданных порядков
Пусть задан неориентированный взвешенный граф G(X,V,w) порядка n, где X={x1,…,xn} – множество вершин; VÍX´X – множество ребер; w:V®R+ – отображение, определяющее вес каждого ребра, где R+ – множество действительных неотрицательных чисел.
Требуется определить разбиение множества вершин X графа G(X,V,w) на k – подмножеств (X1,…,Xk) таким образом, чтобы для кусков графа G1(X1,V1,w1),…, Gk(Xk,Vk,wk) выполнялись следующие требования:
| XiÇXj=Æ, для " i¹j, где i,j =  ;  ; |X1|=n1,…, |Xk|=nk, n1+…+nk=n, | (1) |
Сечением разбиения C(X1,…,Xk) будем называть совокупность ребер, соединяющих вершины, которые принадлежат разным подграфам.
В качестве критерия оптимальности Q, определяющего эффективность би-разбиения (X1,…,Xk) будем рассматривать вес сечения - сумма весов всех ребер сечения:
(2)
 | (3) |
где t – общее число подграфов, имеющих одинаковые размерности.
3. Задачи оптимальной правильной раскраски графов
Пусть задан неориентированный граф без петель G(X,V) порядка n, X={x1,… …,xn} – множество вершин; VÍX´X – множество ребер.
Под раскраской вершин графа понимается процедура приписывания цветов (меток) вершинам графа G(X,V). Правильной раскраской графа в k цветов (k-раскраской графа) считается такая раскраска вершин графа G(X,V), при которой никакие две смежные вершины xi, xjÎX, xi¹xj не получают одинакового цвета.
Наименьшее число k, такое, что граф G(X,V) является k-раскрашиваемым, называется хроматическим числом графа G(X,V).
Задача нахождения хроматического числа графа называется задачей о раскраске (правильной раскраске) графа. Соответствующая этому числу раскраска вершин разбивает множество вершин на k подмножеств, каждое из которых содержит вершины одного цвета. Эти множества вершин одного цвета называется одноцветным классом и являются независимыми, так как в пределах одного множества нет двух смежных вершин.