УльтраграфыОпределенный выше граф называется ультраграфом 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
|
