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




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

5.Выделение подмножеств соединений с заданными свойствами



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

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

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

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




Рис. 2.


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

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

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

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

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

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

  2. Удалить из графа вместе с ребрами вершины ядра и смежные с ядром вершины: .

  3. Если получен несвязный граф , то включить все его вершины в ядро: , перейти к п. 4. Иначе все повторить с п. 1.

  4. Конец.

Рассмотрим примеры определения ядер для графа пересечений, заданного в разделе 3 в алгоритме анализа подмножеств смежностей.

а) Включаем в ядро вершину для которой : .

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











3

6

8

9









3

0

1







1

А

=

6

1

0

1

1

3







8




1




1

2







9




1

1

0

2


в) Включаем в ядро вершину с максимальной локальной степенью : .

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

Ядро построено.

Реализация данного алгоритма при первоначальном выборе вершины дает ядро .

Алгоритм определения ядер с анализом подмножеств смежностей включает 3 основных этапа.

  1. Вершину с включить в ядро: .

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

  3. Включить в ядро вершину , для которой : . Если , то конец. Иначе повторять с п. 1.

Для рассмотренного выше графа пересечений результат определения ядра представлен таблицей 4.

Таблица 4



























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
обратиться к администрации
Библиотека
Главная страница