2. Разновидности графовых моделей сложных объектов



Скачать 275.56 Kb.
страница1/3
Дата02.01.2013
Размер275.56 Kb.
ТипДокументы
  1   2   3

Введение



При изучении взаимосвязей между объектами или отдельными частями сложных объектов проектирования (взаимосвязей людей в коллективах связей в электронно-вычислительной аппаратуре, взаимодействий молекул биологических объектов, соединений микросхем и т.п.) исследуемый объект обозначается точками и соединявшими их линиями. Такое изображение объектов ввиду наглядности позволяет определить наиболее существенные связи, находить оптимальное решение задачи, определять ошибки в рассуждениях и т.д. Объект, состоящий из точек и соединяющих их линий, оказывается удобной моделью схем электронно-вычислительной аппаратуры (ЭВА) различного назначения, программного обеспечения и структуры различных предметных областей.

Теория графов оперирует формальными моделями объектов, имеет дело со свойствами самих графов независимо от того, какова природа объектов, описываемых графами. Использование аппарата теории графов для разработки алгоритмов проектирования схем ЭВА, для анализа вычислительных систем, при проектировании программного обеспечения и при исследовании различных предметных областей в экспертных системах приводит к повышению эффективности и качества создаваемых объектов.

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



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

2.Разновидности графовых моделей сложных объектов




2.1.Графовые модели схем соединений конструктивных элементов



При решении задач автоматизированного проектирования сложных изделий ЭВА и БИС возникает необходимость построения математических моделей схем соединений (структурных, функциональных, принципиальных) конструктивных элементов.

Использование графотеоретических моделей схем соединений сохраняет наглядность и содержательность описываемых объектов и позволяет строить формальные алгоритмы обработки этих моделей, которые легко обрабатывается на ЭВМ.

Любую функциональную или принципиальную схему объекта можно представить состоящей из:

  • множества элементов;

  • множества выводов (контактов) каждого элемента ;

  • множества цепей, соединяющих элементы схемы. (Цепь - множество эквипотенциальных контактов).

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

Так, при задании схемы в виде мультиграфа , множеству Х вершин графа ставится в соответствие множество Е элементов схемы, а ребра U указывают на наличие соединений между элементами [1]. Данная модель использует минимальные данные о схеме, но имеет большое практическое значение: мультиграфы коммутационных схем применяются при решении задач декомпозиции и оптимального размещения элементов в пространстве.

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

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

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



Рис. 1. Фрагмент коммутационной схемы


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

Для целей автоматизированной обработки используют матричные эквивалент мультиграфа [2]: матрицу смежности и матрицу инцидентности , где ,.

Элементы матрицы смежности образуются по правилу:

Для фрагмента коммутационной схемы (см. рис.1) матрица смежности имеет вид:











1

2

3

4

5







1

0

2

2

0

2

А

=

2

2

0

1

1

1







3

2

1

0

1

3







4

0

1

1

0

1







5

2

1

3

1

0


Если матрица смежности графа задает отношения между элементами одного множества X, то матрица инцидентности задает соотношение между множеством вершин Х и множеством ребер U, а ее элементы образуются по правилу:
.
Тогда для мультиграфа (см. рис.2) матрица S запишется в виде:











1

2

3

4

5

6

7

8

9

10

11

12

13

14







1

1

1

1

1

1

1































2







1

1
















1

1

1







S

=

3

1

1













1

1

1




1




1










4


































1

1

1







5













1

1

1

1

1

1










1


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

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

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

Более наглядной графической интерпретацией гиперграфа является двудольный граф Кенига [3], у которого для каждой пары (, ) задается отрезком прямой отношение инцидентности (рис.4).




Рис. 3. Гиперграф коммутационной схемы



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

При матричном представлении модели схемы в виде гиперграфа принадлежность i-го элемента схемы j-й цепи можно задать по правилу:
.
Тогда гиперграф схемы представляется матрицей элементных комплексов, где , а .

Матрица элементных комплексов гиперграфа на рис.4 будет иметь вид:











u1

u2

u3

u4

u5

u6







x1

1

1

1
















x2




1

1

1

1




Q

=

x3

1




1




1

1







x4










1

1










x5

1

1










1


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

Отображение схемы с точностью до выводов с указанием направления передачи сигнала в электрической цепи обеспечивается заданием математической модели схемы в виде ультраграфа [3]. При представлении схемы ориентированным ультраграфом множеству Х вершин ставятся во взаимно однозначное соответствие множества Е элементов схемы и V – электрических цепей, а дуги, помеченные номерами контактов элементов, задают бинарное отношение инцидентности для пар (, ). На рис.5 приведено Кенигово представление ультраграфа для коммутационной схемы, показанной на рис.1.



Рис. 5. Кенигово представление ультраграфа
При матричном представлении ультраграфа используют матрицу электрических цепей, элементы которой определяются по правилу:
.
Размерность по числу столбцов матрицы Т определяется максимальным числом выводов элемента схемы. Такая матрица для исследуемой коммутационной схемы (см. рис.1) имеет следующий вид:











c1

c2

c3

c4







x1

1

2

-3

-







x2

2

3

-4

-

T

=

x3

1

3

5

-6







x4

4

-5

-

-







x5

-1

-2

-6

-5


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

  1   2   3

Похожие:

2. Разновидности графовых моделей сложных объектов iconОтчет по лабораторной работе №1 Анализ операционных графовых моделей последовательных программ методом эквивалентных преобразований
Анализ операционных графовых моделей последовательных программ методом эквивалентных преобразований
2. Разновидности графовых моделей сложных объектов iconПрограмма дисциплины методы построения и анализа сложных математических моделей
Основные цели курса – совершенствование у магистрантов навыков использования математического моделирования при изучении различных...
2. Разновидности графовых моделей сложных объектов iconПрименение Ruleml для представления и вывода знаний о семантической структуре фольклорных текстов, полученных на основе их теоретико-графовых моделей

2. Разновидности графовых моделей сложных объектов iconИсследование моделей сложных систем в рамках квантово-полевы х и молекулярно-динамических уравнений
Модификация пакетов dl poly и chimera и проведение расчетов для моделей кхд и взаимодействия металлических кластеров
2. Разновидности графовых моделей сложных объектов iconЛекция 15 Модели и алгоритмы обработки информации в автоматизированных системах Существуют различные классификации моделей реальных объектов экономики
Существуют различные классификации моделей реальных объектов экономики. Используемые при изучении реальных объектов модели при всем...
2. Разновидности графовых моделей сложных объектов iconМетоды и методики анализа математических моделей в сложных системах (экономических, экологических, биологических) 05. 13. 18 математическое моделирование, численные методы и комплексы программ
Методы и методики анализа математических моделей в сложных системах экономических, экологических
2. Разновидности графовых моделей сложных объектов iconЛекция 1 Виды математических моделей сложных систем
Одной из проблем современной науки является разработка и внедрение в практику математических методов исследования динамики (во времени)функционирования...
2. Разновидности графовых моделей сложных объектов iconПрограммные средства для построения и исследования моделей структурной сложности и сходства
Данные методы реализованы в виде подсистемы асни «Graph Model Workshop» и нашли применение при исследовании отношений эквивалентности...
2. Разновидности графовых моделей сложных объектов iconГраф-модели для анализа сходства структур систем на основе их сложности
Предложенные модели позволили развить подструктурный подход к анализу сходства графов и выделить новые виды отношений сходства графовых...
2. Разновидности графовых моделей сложных объектов iconЛабораторная работа №1 исследование математических моделей линейных импульсных систем (лис)
Исследовать математические модели лис и способы построения этих моделей для линейных непрерывных объектов
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org