10) Плоскиe графы и их свойства. Теоремы и леммы планарности.

Граф G(X, U) называют плоским (планар­ным), если его можно изобразить на плоскости без пересечения ребер.

Лемма. Связный плоский граф с п вершинами, r ребрами и k гранями (включая внешнюю или бесконечную грань) удовлетворяет фор­муле Эйлера n--r+k=2.

Условия планарности:

- планарность не определяется.

Теорема Понтрягина — Куратовского: Граф является плоским тогда и только тогда, когда он не содержит подграфа, изоморфного с точностью до вершин степени два одному из графов Понтрягина — Куратовского.

Теорема о двойственности графа: Необходимым и достаточ­ным условием планарности графа является наличие у него двойствен­ного графа.

Граф G_a(Y_t V) называют двойственным для плоского графа G(X_t U)_t если он получен из G(X, 0) в результате следующего построения. Каждой грани графа G(X, U) ставим в соответ­ствие вершину двойственного графа. Если две грани смежны, то соединяем Уi ^и Уj ребром пересекающим один раз общую границу граней и не проходящим через другие границы графа G(X, U). При этом, если некоторое ребро не является границей G(X, U), т. е. находится внутри какой-либо грани, то ребру соответствует петля.

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

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

Для реализации алгоритма задаётся матрица соединений и матрица расстояний для коммутационного поля. Далее ранжируются вершины по возрастанию их степени:

(X₁) < (X₂) < (X₃) < ... < (X_N).

В данном случае индексы 1, 2, 3, ... , N обозначают не номера вершин в графе, а их порядок в соответствии с возрастанием степени вершины.

На следующем шаге ранжируются позиции коммутационного поля в порядке убывания их характеристик:

d₁ > d₂ > d₃ > ... >d_N, где d_N - центральная позиция.

В данной записи смысл нижних индексов аналогичен отмеченному выше.

В большинстве случаев число вершин задаётся равным числу позиций коммутационного поля (в любом случае не больше).

Само размещение проводится следующим образом: вершина X₁ ставится в позицию d₁, вершина X₂ в позицию d₂ и так далее. Таким образом осуществляется одновременное размещение вершин графа на позициях коммутационного поля.

Примеры задач: трассировка, компоновка.

12) Основные положения и понятия теории алгоритмов. Геометрическая и алгебраическая теория алгоритмов. Основные положения Гост 19.002-80. 10.003-80.

Алгоритм есть информация об организа­ции некоторого процесса. Обычно процесс осуществляется с помощью какой-то системы, именуемой реализующей системой. Конкретное выполнение процесса в соответствии с заданным алгоритмом называют реализацией алгоритма.

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

Свойства:

• Массовость- свойство алгоритма отображать широкий класс процессов. Чем шире класс, тем больше массовость, выше ка­чество, ценность алгоритма.

• Результативность — свойство алгоритма, обеспечивающее получение результата через конечное число шагов.

• Областью применимости алгоритма называют мно­жество процессов, для которых алгоритм результативен.

• Под эквивалент­ностью алгоритмов понимают следующее: два алгоритма эквивалентны, если совпадают их области применимости и результаты переработки любого процесса из этой области.

Алгебраическая теория алгоритмов основывается на некоторой конкретной символике, при которой алгоритмы рас­сматривают в виде линейных текстов.

Геометрическая теория алгоритмов – алгоритмы строят в виде мно­жеств, между которыми вводят связи, носящие характер отображе­ний.

13) Применение методов математического программирования при оптимизации конструкции и технологических процессов и изготовления РЭС. Математическая формулировка задач математического программирования, примеры технических задач, приводящих к задачам математического программирования. Классификация методов математического программирования.

Под математическим программированием понимается совокупность методов решения задач оптимизации, связанных с нахождением наи­лучшего (с точки зрения выбранных критериев качества) значения некоторой целевой функции F(X) многих переменных X = {Х₁, .... X_n} на заданном множестве точек L(Х) евклидова пространства Еⁿ, а также плана X^* = {х*₁ х*₂.....х*_п}, X* € L(Х), при котором достигается соответствующее оптимальное значение F(X*).

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

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

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

Численные методы программирования определяются видом целе­вой функции и ограничений математической модели, используемой в задаче. В зависимости от аналитических свойств исследуемой модели различают методы линейного (целевая функция и ограниче­ния — линейные функции) и нелинейного программи­рования.

Применяются для решения задач оптимизации.