Файл: opres_2008.doc

На рис. 4.2 представлены некоторые типы графов.

Рис. 4.2. На рисунке представлены изображения некоторых типов графов

2. Элементы графа

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

Смежнымирёбрами называются два ребра, которые подходят к одной вершине, или выходят из неё. Иногда говорят, что этирёбра инцидентны вершине.

Степень r(X_i) вершиныX_i– это число инцидентных ей рёбер. Если ни одного ребра к вершинеX_iне подходит, тоr(X_i) = 0; если подходит одно ребро, тоr(X_i) = 1 и т.д..

Части графа

Различают подграфикусокграфа.

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

Кусок получается разделением исходного графа путём "перерезания" рёбер. При разделении графа на куски не происходит образования новых вершин, которые распределяются по кускам. Ребра в этом случае разделяются на внутренние ребра кусков и на соединительные ребра (которые были "разрезаны"), соединяющие куски. Их число минимизируется при выполнении задачи разбиения.

Рис. 4.3 иллюстрирует образование подграфов и кусков графа.

Рис. 4.3. Подграфы и куски графа

Структурные свойства связных графов

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

Маршрут– последовательность рёбер, заданная парами вершин, в которых каждая пара вершин – смежная (рис. 4.4).

Рис. 4.4. Маршрут в графе

Пример маршрута: (X1,X2)(X2,X3)(X3,X1)(X1,X4)…, и т. д.

Цепь– маршрут, в котором все ребра различны. Простая цепь – это цепь, в которой все вершины различны.

Цикл– цепь, в которой совпадает начальная и конечная вершины. Простой цикл – это простая цепь, с совпадающими начальной и конечной вершинами.

Пример цикла: (X1,X2)(X2,X3)(X3,X1).

Гамильтонов циклHC– такой цикл, который проходит через все вершины графа по одному разу:HC= (X1,X2)(X2,X3)(X3,X4)(X4,X1). Его наличие в графе не очевидно, хотя его полезно знать для решения ряда топологических задач. Существуют алгоритмы для выделения гамильтонова цикла.

Деревья– особый тип графов. Дерево представляет собой связный граф без циклов (рис. 4.5). Во многих задачах проектирования монтажных соединений ставится задача поиска дерева на совокупности вершин с минимальной суммарной длиной рёбер. Формула для определения числаdдеревьев, которые можно построить наNвершинах, выглядит следующим образом:

d=NN2.

Рис. 4.5. Пример дерева

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

Матрица соединений

Матрицы соединений используются для формализованного описания графов. Обозначение этой матрицы R.

Правило заполнения матрицы следующее. Столбцы и строки матрицы соответствуют вершинам графа; число строк и столбцов равно числу вершин, т. е. матрица квадратная. На пересечении строки iи столбцаjставится числоr_ij, соответствующее числу ребёр, которые соединяют эти вершины. Диагональными элементами матрицы являются нули, если в матрице отсутствуют петли. В противном случае проставляется число равное числу петель у соответствующей вершины. Ясно, что матрица симметрична относительно главной диагонали (r_ij=r_ji).

Ниже (рис. 4.6) приведена матрица соединений, в которой для наглядности строки и столбцы имеют заголовки x₁,x₂,x₃, ...,x_N, гдеNчисло вершин графа.

Рис. 4.6. Матрица соединений

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

r(x_i) = (r_i1 + r_i2 + r_i3 + ... + r_iN).

Можно привести пример анализа связности графа с использованием матрицы соединений. Для этого возьмём для наглядности очень простой несвязный граф (рис. 4.7), содержащий четыре вершины x₁,x₂,x₃,x₄; и два ребра, которые соединяют пары вершинx₁,x₄, иx₃,x₂.

Рис. 4.7. Несвязный графа

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

Построим для заданного графа матрицу соединений (рис. 4.8).

Рис. 4.8. Матрица соединений для заданного графа

Для получения результата перенумеруем вершины графа, не изменяя его структуры, как показано на рис. 4.9, и построим для последнего варианта матрицу соединений (рис. 4.10). Эта матрица может быть разбита на подматрицы A_ii (рис. 4.11).

Рис. 4.9. Перенумерованные вершины графа

Рис. 4.10. Матрица соединений заданного несвязного графа

Рис. 4.11. Подматрицы матрицы соединений

Рёбра, включенные в подматрицу A_ii, относятся квнутреннимчастям графа, а рёбра, которые включены в подматрицыU_ij, естьсоединительныерёбра между подматрицами (частями) графаiиj. Таким образом, процедура разбиения графа при использовании матрицы соединений сводится к разбиению матрицы на отдельные подматрицы. Результат разбиения оценивается по одному из критериев разбиения, например – по отношениюU_ii/U_ijчисла внутренних рёберU_iiк числу соединительных рёберU_ij. Чем больше это отношение, тем выше качество разбиения, если граф описывает узлы электронной аппаратуры.

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

Матрица инциденций

Отличие матрицы инциденций(I) (рис. 4.12) от матрицы соединений (смежности) состоит в том, что строки матрицы соответствуют вершинам графа, а столбцы – рёбрам. Элементамиi_ijматрицы являются либо нули, либо единицы. В случае, если ребро не инцидентно вершине, то элемент равен 0, если ребро инцидентно вершине – элемент равен 1.

Рис. 4.12. Матрица инциденций

Получим матрицу инциденций для простейшего графа (рис. 4.13), содержащего четыре вершины (N= 4) и шесть рёбер (m= 6) (полный граф).

Рис. 4.13. Простейший граф

Для этого графа матрица инциденций выглядит, как показана на рис. 4.14.

Рис. 4.14. Матрица инциденций для заданного графа

3. Содержание задач топологического проектирования

Здесь можно выделить три взаимоувязанных задачи:

• разбиение;

• размещение;

• трассировка.

Эти задачи тесно переплетены, и, в ряде случаев, критерии решения одной задачи являются критериями решения другой задачи. Как, например, критерий задачи размещения является одновременно и критерием задачи трассировки.

Математической основой решения этих задач является теория графов. Именно развитый математический аппарат позволил успешно продвинуть решение этих задач в САПР.

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

• содержание задач топологического проектирования,

• алгоритмы решения топологических задач.

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

Задача разбиения

Исходными данными в данной задаче являются принципиальные электрические схемы электронных блоков или приборов. При этом в схеме имеются элементы с определённым количеством выводов, и схема обладает связностью элементов.