2. Характеристика задач и математических моделей топологического проектирования объектов




Скачать 313.8 Kb.
Название2. Характеристика задач и математических моделей топологического проектирования объектов
страница2/5
Дата18.05.2013
Размер313.8 Kb.
ТипДокументы
1   2   3   4   5

3.Алгоритмы определения оптимального числа слоев топологии




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

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



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

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

К числу точных методов раскраски относятся метод целочисленного линейного программирования [4], алгоритмы, использующие метод Магу [3].

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

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

  1. Составить список L вершин графа в порядке убывания локальных степеней . Выбрать цвет .

  2. Раскрасить первую слева в строке L вершину в цвет j и удалить ее из L.

3. Просматривая список L слева направо от , раскрашивать в цвет j и удалять из L любую вершину, несмежную с уже раскрашенными в цвет j.

4. Если и перейти к п.2. При процесс раскраски завершается.

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

.

Результаты раскраски сведены в таблицу 1, где множество вершин соответствует множеству вершин несмежных с окрашенным множеством .

Для упорядоченное множество неокрашенных вершин . Первой в цвет j окрашивается вершина . Подмножество вершин, несмежных с , будет равно . Очередной вершиной для раскраски, выбираемой из L, будет . После раскраски вершин в цвет в L не остается ни одной вершины, не смежной с , и осуществляется выбор нового цвета.








1

2

3

4

5

6

7

8






1

0

1

0

0

0

0

1

0

2




2

1

0

1

0

0

0

1

1

4




3

0

1

0

0

0

0

1

0

2

А =

4

0

0

0

0

1

0

1

1

3




5

0

0

0

1

0

1

1

1

4




6

0

0

0

0

1

0

1

0

2




7

1

1

1

1

1

1

0

0

6




8

0

1

0

1

1

0

0

0

3


Таблица 1

Результаты раскраски графа


Цвет

j

Окрашенные вершины

Несмежные

Упорядоченное множество вершин L











1







1








2







2








3







3







3







3










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





Если в графе нет двух таких вершин, то необходимо объединить в один цвет две несмежных вершины, для которых выполняются условия:



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

  1. В графе G(X,U) найти пары несмежных вершин , , для которых выполняются соотношения (1) или (2), объединить их, перейти к пункту 2.

Если таких вершин нет, найти две другие несмежные вершины , , для которых выполняется соотношение (3) и перейти к пункту 2.

  1. Построить подмножество смежностей объединения вершин:

или

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

  1. Если после объединения вершин получен полный граф (в полном графе все вершины смежны) – конец, иначе и все повторить с п.1.

Рассмотрим этапы раскраски графа по данному алгоритму. В модифицированном графе объединенная пара вершин нумеруется двойным индексом, например .

Исходная матрица смежности имеет вид:









1

2

3

4

5

6

7

8

9




1

0

1




1



















2

1

0




1

1
















3







0




1

1













4

1

1




0

1




1







А =

5




1

1

1

0







1







6







1







0




1

1




7










1







0

1







8













1

1

1

0

1




9
















1




1

0

Шаг 1. Соотношение (1) выполняется для множеств вершин : , и : . Объединяем найденные множества вершин и получаем матрицу смежности А1 модифицированного графа:








1,5,7

2

3,8

4

6

9




1,5,7

0

1

1

1










2

1

0




1







А =

3,8

1




0




1

1




4

1

1




0










6







1




0

1




9







1




1

0


Шаг 2. Соотношения (1), (2) не выполняются для пар несмежных вершин графа А1.

Результаты проверки соотношения (3) сведены в таблицу 2.

Таблица 2

Варианты объединения несмежных вершин




d

Результаты выбора



3





3






3





4






4






3






4






4




После объединения найденных по соотношению (3) пар (, ) вершин получим полный граф:









1,5,7,6

2,3,8

4,9




1,5,7,6

0

1

1

А2 =

2,3,8

1

0

1




4,9

1

1

0


и вариант хроматической раскраски в три цвета: , , .
1   2   3   4   5

Похожие:

2. Характеристика задач и математических моделей топологического проектирования объектов icon3 (41) 2011 применение математических моделей электроэнергетических объектов
Рассмотрена возможность применения матричных моделей установившихся режимов работы электроэнергетических объектов на основе эквивалентных...
2. Характеристика задач и математических моделей топологического проектирования объектов iconВоронежская государственная технологическая академия
Целью изучения дисциплины является приобретение студентами знаний о принципах и методах построения математических моделей объектов...
2. Характеристика задач и математических моделей топологического проектирования объектов iconПрограмма учебной дисциплины «математические методы в организации автотранспортного производства»
Целью изучения дисциплины является ознакомление студентов с математическими методами и моделями определения оптимальных или близких...
2. Характеристика задач и математических моделей топологического проектирования объектов iconИсследование операций это раздел прикладной математики, который занимается построением математических моделей реальных задач и процессов (экономических, социальных, технических, военных и др.
Большинство этих моделей связано с выработкой рекомендаций по принятию «оптимальных» решений
2. Характеристика задач и математических моделей топологического проектирования объектов iconРабочая программа дисциплины методы построения и анализа сложных математических моделей
Основные цели курса – совершенствование у магистрантов навыков использования математического моделирования при изучении различных...
2. Характеристика задач и математических моделей топологического проектирования объектов iconПроект направлен на решение фундаментальной проблемы – разработку математических моделей переходных процессов в сложных физических системах, на создание вычислительных методов и комплексов программ для их численного исследования, а также на численное исследование этих моделей
Ми результатами с целью проверки применимости математических моделей, их уточнения и развития, а также построения методов численного...
2. Характеристика задач и математических моделей топологического проектирования объектов iconСтавропольский институт экономики и управления
Целью изучения дисциплины является формирование комплекса знаний по теоретическим и методологическим основам математических моделей...
2. Характеристика задач и математических моделей топологического проектирования объектов iconКомплекс математических моделей для проектирования и управления гидросистемами поддержания пластового давления
Строение и функционирование систем ппд характеризуется развитой уникальной для каждого месторождения сетью трубопроводных элементов,...
2. Характеристика задач и математических моделей топологического проектирования объектов iconКалендарный план
Математика и математическое моделирование. Прямые и обратные задачи математического моделирования. Универсальность математических...
2. Характеристика задач и математических моделей топологического проектирования объектов iconУтверждаю Заведующий кафедрой высшей математики и физики Профессор доктор физико-математических наук Соловьёв И. А
Численные методы анализа математических моделей, описываемых уравнениями с одним неизвестным
Разместите кнопку на своём сайте:
Библиотека


База данных защищена авторским правом ©lib.znate.ru 2014
обратиться к администрации
Библиотека
Главная страница