Студопедия — Ультраграфы
Студопедия Главная Случайная страница Обратная связь

Разделы: Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Ультраграфы






Определенный выше граф называется ультраграфом HU (X, U,Г1,Г2), если предикаты Г1(X, U) и Г2(U, X) обладают следующим свойством

$ uj Î U (|Г1 uj |+ |Г2 uj |) >2, (2)

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

Полным и достаточно наглядным способом формального задания ультраграфа является его представление через две матрицы инцидентности А 1 и A 2, где А 1– матрица истинности предиката Г1(X, U) и А 2 – матрица истинности предиката Г2(U, X).

Матрица инцидентности А 1, задающая связь между вершинами и ребрами, – это прямоугольная матрица размером n ´ m, где n = | X |, m = | U |. Элементы этой матрицы определяются по правилу

1 – если Г1(xi,uj)= «и»

a 1 i,j =,

0 – если Г1(xi,uj)= «л»

где i = 1, n; j = 1, m.

Матрица инцидентности А 2 задает связь между ребрами и вершинами. Ее строки соответствуют ребрам, а столбцы – вершинам (размер матрицы m´n). Элементы матрицы А 2 определяются по правилу

1 – если Г2(uj,xi)= «и»,

a 2 j,i =

0 – если Г2(uj,xi)= «л».

Аналитически ультраграф полностью задается множествами X, U и образами этих множеств относительно предикатов Г1(X, U) и Г2(U, X).

Образом множества A относительно предиката Р(A,B) является множество

РA = { Рai / ai Î A },

где Рai = { bj Î B: Рai (bj) = «и»},– характеристическое подмножество предиката-свойства Рai (B), т. е. образ элемента ai Î A относительно этого предиката.

В ультраграфе Hu (X, U, Г1 X, Г2 U):

Г1 X ={Г1 xi / xi Î X }, Г1 xi = U 1 i Í U– ребра, инцидентные вершине xi Î X;

Г2 U ={Г2 uj / uj Î U }, Г2 uj = X 2 j Í X– вершины, инцидентные ребру uj Î U.

Пример. Ультраграф данным способом будет задан, если заданы множества вершин X, ребер U и их образы.

Hu (X, U, Г1 X, Г2 U): X = { x 1, x 2, x 3, x 4, x 5}, U = { u 1, u 2, u 3},

Г1 X = {Г1 xi / i =1,5}, где: Г1 x 1 = { u 1, u 2}, Г1 x 2 = Г 1x 3 1 x 4 = Æ, Г1 x 5 = { u 1, u3},

Г2 U = { Г2 uj / j =1,3}, где: Г2 u 1= { x 2, x 3}, Г2 u 2= { x 4}, Г2 u 3= { x 5}.

Рассмотренное представление ультраграфа, является полным, однако в ряде случаев затрудняет выполнение формальных преобразований и просмотр структуры ультраграфа. Например, для того чтобы определить, каким вершинам инцидентно ребро uj Î U, необходимо проверить принадлежность этого ребра всем Г1 xi и сформировать подмножество вершин согласно выражению:

Xj ={ xi Î X: uj Î Г1 xi }.

Аналогичное замечание справедливо и для определения множества ребер, которым инцидентна вершина xi Î X.

Для задания таких множеств воспользуемся понятием «прообраз множества относительно предиката». По определению прообраз множества – это его образ относительно обратного предиката.

Элементы предикатов Г2-1(X, U) и Г1-1(U, X) определяются по правилам:

" uj Î U, " xi Î X (Г2(uj, xi) = «и» ® Г2-1(xi, uj) = «и») и

" xi Î X, " uj Î U (Г1(xi, uj) = «и» ® Г1-1(uj, xi) = «и») соответственно, т.е. таблицы истинности этих предикатов получаются транспонированием матриц истинности A1 и A2.

Отсюда множество ребер U2i, которым инцидентна вершина xi Î X – ее прообраз относительно предиката Г2(U, X), – это характеристическое множество i- го вектора строки матрицы истинности предиката Г2-1(X, U) или i -го вектора-столбца матрицы А 2, т. е. предиката-свойства Г2 xi (U):

U 2 i = Г2 xi ={ uj Î U: Г2 xi (uj) = «и» }, U 2 i Í U.

Прообразом множества X относительно предиката Г2(U, X)будетмножество характеристических подмножеств предикатов-свойств Г2 xi (U):

Г2 X = {Г2 xi / xi Î X }.

Аналогично множество вершин, которым инцидентно ребро uj Î U – его прообраз Г1 uj относительно предиката Г1(X, U) –это характеристическое множество X 1 j предиката-свойства Г1 -1 uj (X), соответствующего j -у вектору-строке матрицы истинности предиката Г1-1(U, X), или предиката-свойства Г1 uj (X), задаваемого j -м вектором-столбцом матрицы А 1:

X 1 j = Г1 uj = { xi Î X: Г1 uj (xi) = «и» }, X 1 j Í X.

Прообразом множества U относительно предиката Г1(X, U) является множество характеристических подмножеств предикатов-свойств Г1 uj (X):

Г1 U = {Г1 uj / uj Î U }.

Предикат смежности вершин F 1(X, X). Вершина xt смежна вершине xi, если существует ребро uj инцидентное вершине xi, такое, что вершина xt инцидентна ему. Отсюда элементы матрицы смежности R 1 определяются по правилу:

1 – если $ a 1 i,j =1 & a 2 j,t =1,

r 1 i,t =

0 – в противном случае,

где i, t =1, n; n = | X |, j =1, m; m = | U |.

Предикат смежности ребер F 2(U, U). Ребро uk смежно ребру uj, если существует вершина xi инцидентная ребру uj, такое, что ребро uk инцидентно ей. Отсюда элементы матрицы смежности R 2 определяются по правилу:

1 – если $ a 2 j,i =1 & a 1 i,k =1,

r 2 j,k =

0 – в противном случае,

где j, k =1, m; m = | U |, i =1, n; n = | X |.

Совокупность предикатов F 1(X, X) и F 2(U, U) задает ультраграф не полностью

Образ и пробраз вершины xi– это х арактеристические множества предикатов-свойств F 1 xi (X), и F 1-1 xi (X):

F 1 xi = X 1 i ={ xj Î X: F 1 xi (xj) = «и» }, X 1 i Í X – вершины,смежные вершине xi Î X;

• F1-1 xi = X 1 i -1={ xj Î X: F1 xi (xj) = «и» }, X 1 i Í X –вершины, которым смежна вершина xi Î U. Они задаются i-ми вектором-строкой и вектором-столбцом матрицы R1 соответственно:

Образ и прообраз ребра ui – это х арактеристические множества предикатов-свойств F 2 uj (U) и F 2-1 uj (U):

F 2 uj = U 2 j ={ ui Î U: F 2 uj (ui) = «и» }, U 2 j Í U –ребра, смежные ребру uj Î U;

F 2-1 uj = U 2 j -1={ ui Î U: F 2 uj (ui) = «и» }, U 2 j Í U –ребра, которым смежно ребро uj Î U; Они задаются i-ми вектором-строкой и вектором-столбцом матрицы R2 соответственно:

 

 


1. Задачи структурного синтеза: понятие, формальная постановка, пример. 1

2. Исходные данные для решения задач структурного синтеза. 2

4. Содержательная постановка и анализ задачи структурного синтеза. Результат анализа (рассмотреть пример).Пример постановки и формализации задачи структурного синтеза. 2

3. Этапы решения прикладной задачи структурного синтеза. 3

5. Выбор аппарата формализации задач структурного синтеза. Разработка моделей объекта и результата проектирования, доказательство их адекватности (приведите пример перехода от объекта к модели). 4

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

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

8. Представление схемы неориентированным графом и гиперграфом. Неориентированный граф. 8

8.1.Представление схемы ориентированным графом. (аналогично ультраграфу) 9

15. Основные способы ветвления при построении дерева решений в методе ветвей и границ. 10

9. Стратегии декомпозиции пространства решений. 11

10. Отсечение и выбор перспективной вершины дерева решений. Верхняя и нижняя границы целевой функции. Пример. 13

Некоторые особенности оценочных функций. 13

11. Метод поиска в глубину. Пример точного алгоритма, основанного на этом методе. 14

12. Метод поиска в глубину с возвращением. Привести пример применения. 15

13. Метод поиска в ширину. Привести пример применения. 16

14. Идея метода ветвей и границ. Основные способы отсечения ветвей. 17

16. Конструирование оценочной функции для верхней и нижней границ целевой функции. (Рассмотрите на примере задачи поиска простой цепи графа). 18

17. Метод итерационного улучшения. 20

18. Метод параллельно-последовательной свертки. Алгоритм сортировки слиянием. Оценка его вычислительной сложности. 22

19. Точность алгоритма. Докажите, что алгоритм Прима является точным. 24

20. Оценка точности алгоритма. Определение оценок в лучшем и в худшем для алгоритма решения задачи коммивояжора по методу поиска в глубину. 26

21. Вычислительная и емкостная сложность алгоритма. 28

22. Основные этапы построения алгоритма. Сущ-ть алг. решения задачи на графах. 30

23. Разработка алгоритмической модели процесса решения задачи. Пример модели для решения задачи декомпозиции схемы по методу неуравновешенной двоичной свёртки. 31

Пример модели для решения задачи декомпозиции схемы по методу неуравновешенной двоичной свёртки. 31

24. Определение операций преобразования исходного графа в граф результата. Выбор способа представления графов и его реализация в памяти ЭВМ. 33

25. Детальная проработка алгоритма. Способы снижения вычислительной сложности алгоритмов. (Проиллюстрировать примерами). 35

26. Последовательный алгоритм разрезания гиперграфа схемы. 37

27. Итерационный алгоритм улучшения начального разрезания гиперграфа схемы. 39

28. Методика оценки вычислительной сложности алгоритма. Рассмотрите пример. 41

Асимптотическая оценка вычислительной сложности алгоритма. 41

29. Управляющий граф алгоритма. 43

30. Граф «оператор - данные». 44

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

32.Математическая модель алгоритма. 47

33.Генетический метод. 49

34.Метод динамического программирования. 50

35.Метод параллельного поиска. 52

36.Дополнительные отсечения при использовании метода ветвей и границ. Идея алгоритма Дейкстры.. 53

37.Модификация метода на примере задачи построения гамильтонова цикла с минимальной суммой весов ребер. 54

38.Модели структур данных. 55







Дата добавления: 2015-04-19; просмотров: 1071. Нарушение авторских прав; Мы поможем в написании вашей работы!



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

ТЕОРЕТИЧЕСКАЯ МЕХАНИКА Статика является частью теоретической механики, изучающей условия, при ко­торых тело находится под действием заданной системы сил...

Теория усилителей. Схема Основная масса современных аналоговых и аналого-цифровых электронных устройств выполняется на специализированных микросхемах...

Логические цифровые микросхемы Более сложные элементы цифровой схемотехники (триггеры, мультиплексоры, декодеры и т.д.) не имеют...

ФАКТОРЫ, ВЛИЯЮЩИЕ НА ИЗНОС ДЕТАЛЕЙ, И МЕТОДЫ СНИЖЕНИИ СКОРОСТИ ИЗНАШИВАНИЯ Кроме названных причин разрушений и износов, знание которых можно использовать в системе технического обслуживания и ремонта машин для повышения их долговечности, немаловажное значение имеют знания о причинах разрушения деталей в результате старения...

Различие эмпиризма и рационализма Родоначальником эмпиризма стал английский философ Ф. Бэкон. Основной тезис эмпиризма гласит: в разуме нет ничего такого...

Индекс гингивита (PMA) (Schour, Massler, 1948) Для оценки тяжести гингивита (а в последующем и ре­гистрации динамики процесса) используют папиллярно-маргинально-альвеолярный индекс (РМА)...

Шрифт зодчего Шрифт зодчего состоит из прописных (заглавных), строчных букв и цифр...

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

РЕВМАТИЧЕСКИЕ БОЛЕЗНИ Ревматические болезни(или диффузные болезни соединительно ткани(ДБСТ))— это группа заболеваний, характеризующихся первичным системным поражением соединительной ткани в связи с нарушением иммунного гомеостаза...

Studopedia.info - Студопедия - 2014-2024 год . (0.009 сек.) русская версия | украинская версия