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




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

6.Определение замкнутых областей коммутационного пространства



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

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

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

Р

ис. 3.


Таким образом, замкнутые области пространства, образуемые отрезками соединений, являются потенциально неблагоприятными для трассировки.

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

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

  1. В качестве корня дерева выбирается произвольная вершина и становится источником движения.

  2. От моделируется движение по графу с отметкой пройденных ребер и удалением ребер, ведущих к циклам, и производиться построение простой цепи.

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

  4. После подсоединения в дерево всех вершин, непросмотренные ребра удаляются из графа.

Ниже представлен пример построения ациклического графа D пересечений. В матрице смежности исходного графа удаленные ребра отмечены символом , а включенные в дерево символом .

Таблица 5 иллюстрирует ход построения дерева. Второй и третий столбцы указывают на включенные в дерево D и удаленные из исходного графа ребра. Число удаленных ребер соответствует цикломатическому числу исходного графа, наименование ребер позволяет легко локализовать замкнутые области пространства в структуре соединений.











1

2

3

4

5

6

7

8

9







1

0

1




1






















2

1







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


Таблица 5

Источник движения





D























































































Продолжение таблицы 5

Источник движения





D




















Шаг назад и попытка пройти по новому пути










Непройденное ребро удаляется














7.Порядок выполнения работы



Задание 1 (2 часа)

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

    2. Изучить алгоритмы хроматической раскраски графа пересечений и определить по ним минимальное число слоев топологии.

    3. Изучить алгоритм поэлементной дизъюнкции и определить максимальную емкость слоя топологии и множество ядер для заданного графа пересечений.

Задание 2 (2 часа)

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

    2. Построить ациклический граф пересечений и определить цикломатическое число.

    3. Получить на ЭВМ значения L(G), B(G), (G), минимальные ядра и ациклический граф. Сопоставить машинные результаты с ручными расчетами в п. п. 7.2 – 7.5.



8.Содержание отчета





    1. Цель работы.

    2. Исходный вариант расположения соединений в пространстве.

    3. Графовая модель соединений в виде матрицы смежности.

    4. Результаты хроматической раскраски по алгоритмам разд. 3.

    5. Результаты генерации НВУП по алгоритму поэлементной дизъюнкции.

    6. Разработанный алгоритм определения минимального ядра и результаты его применения к исходному графу.

    7. Машинные результаты и сравнительный анализ.

9.Контрольные вопросы





  1. Дать характеристику задач анализа топологии соединений.

  2. Пояснить принцип построения математической модели взаимного расположения соединений.

  3. Что такое хроматическое число и каково его прикладное значение?

  4. Каковы этапы алгоритма хроматической раскраски, основанные на упорядочивании вершин?

  5. Каков порядок хроматической раскраски при учете подмножеств смежностей?

  6. Что такое число внутренней устойчивости и каково его прикладное значение?

  7. Опишите алгоритм поэлементной дизъюнкции.

  8. Как вынести в отдельный слой подмножество наиболее конфликтных соединений?

  9. Сформулируйте алгоритмы определения минимальных ядер.

  10. Определить понятие цикломатического числа и определить его прикладное значение.

  11. Сформулировать алгоритм построения ациклическогографа.



Библиографический список





  1. Мелихов А. Н. и др. Применение графов для проектирования дискретных устройств. – М.: Наука, 1984. –276 с.

  2. Кристофидес Н. Теория графов. Алгоритмический подход. –М.: Мир, 1978. –345 с.

  3. Деньдобренко Б. Н., Малика А. С. Автоматизация конструирования РЭА. –М.: Высш. шк., 1990. –384 с.

  4. Алипов Н. В. Задачник по автоматизации конструкторского проектирования РЭА и ЭВА: Учеб. пособие для ВУЗов. –М.: Высш. шк., 1986. –160 с.


Содержание


1. Цель работы 1

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

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

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

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

6. Определение замкнутых областей коммутационного пространства 11

7. Порядок выполнения работы 13

8. Содержание отчета 13

9. Контрольные вопросы 13

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