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




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

4.Определение емкости слоя топологии соединений



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

Если в графе G(X,U) имеется подмножество , принадлежащее Х, несмежных между собой вершин, таких, что



то такое подмножество называется внутренне устойчивым (ВУП).

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

ВУП считается непополнимым (НВУП), если его нельзя дополнить ни одной другой вершиной. Если в графе выделить семейство всех НВУП, то величину L(G), равную мощности максимального НВУП, называют числом внутренней устойчивости:



Количественная оценка L(G) позволяет определить максимальное число соединений, которые могут выполняться бесконфликтно и отражает верхнюю границу емкости одного слоя соединений. Среди методов определения L(G) известны аналитические методы, основанные на алгоритме Магу [3]; метод поэлементной дизъюнкции; алгоритм систематического перебора Брона и Кэрбоша [4].

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

  1. В матрице смежности элементы главной диагонали заменить на единицы: .

  2. Из i-ой строки выбрать первый слева нулевой элемент , причем , и перейти к пункту 3.

Если все , то перейти к обработке следующей строки.

  1. Выполнить поэлементную дизъюнкцию строк i и j и определить строку

.

  1. Из строки выбрать первый слева нулевой элемент и перейти к пункту 5.

Если все , где , то перейти к пункту 6.

  1. Выполнить поэлементную дизъюнкцию строк и k-ой:

.

Заменить на на j и все повторить с пункта 4.

  1. Определить и продолжить поиск нулевых элементов в i-ой строке.

Процесс заканчивается построением всех НВУП для каждой строки матрицы А. Пусть матрица смежности имеет вид:








1

2

3

4

5

6




1

0

1







1







2

1

0

1




1




А =

3




1

0













4










0

1







5

1

1




1

0

1




6













1

0


В таблице 3 представлен фрагмент генерации НВУП с помощью алгоритма поэлементной дизъюнкции.

Таблица 3

Пример генерации НВУП




строки







НВУП

1

2

3

4

5

6

1







1

1

1

1

1

1

1

1

1

0

1

1

1

1

1

0

0

1





2





1

1

1

1

1

1

1

1

1

1

0

1





Для приведенного фрагмента вычислений НВУП .
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
обратиться к администрации
Библиотека
Главная страница