Однотипными называются ТЭК, имеющие одинаковый состав элементов и одинаковую КС.

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

Два графа G = (Х,U) и G' = (Х',U') называются изоморфными, если можно установить взаимно однозначное соответствие Х↔X', U↔U', такое, что если (Xi,Xj) є X ↔ (X_i',X_j') є X' то ребро UR = (X_i,X_j) є U ↔ U_r'=(X_i', X_j' ) є U₁'.

Изоморфные графы могут быть получены один из другого путем перенумерации их вершин.

Задана функциональная схема, состоящая из элементов разных типов.

Задача выделения в графе G изоморфных подграфов формулируется следующим образом: найти разбиение φ(G) є 0 графа G на множество групп Г={Г₁,.....,Г_f} изоморфных подграфов Г_i, удовлетворяющих следующим требованиям:

- любые два подграфа, принадлежащие произвольной группе разбиения, не должны пересекаться;

- множество вершин любых двух подграфов разбиения недолжны пересекаться;

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

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

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

ПРИМЕР:

Схема коммутационная

По исходной схеме строим взвешенный граф G*=(X.U)

Строится матрица смежности

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

1. Объединяются равно вариантные вершины графа G=(X,U) в группы Г_i^k k - шаг выделения изоморфных подграфов. k=0 - начальный шаг.

Равно инвариантные вершины (инвариантные вершины - вершины, у которых степень и вес одинаковы) объединяются в группы.

Г₁⁰ = {X1, Х4, Х7} степень р(Хi) = 2 и вес β = 2;

Г₂⁰ ={Х2, Х5, Х8} степень p(Xi)=3 и вес β = 4;

Гз⁰ ={ХЗ, Х6, Х9} степень p(Xi)=5 и вес β = 6;

(локальной степенью вершины q называется число ребер, инцидентных одной вершине)

2. Определяются группы Г с мощностью множества, равного 1(t=1) и производиться исключение их из дальнейшего рассмотрения. Мощность t - количество вершин в группе. В нашем примере таких групп нет.

3. Рассматриваются все возможные объединения Г_i⁰ и Г_j⁰ пар групп равно вариантных вершин, и находится максимальное число изоморфных подграфов, состоящее из двух вершин.

L=1(1-1)/2

L=3(3-1)/2=3

1 - число групп.

L - число возможных объединений групп.

Процесс выделения изоморфных подграфов заключается в выборе максимального числа одинаковых (но не нулевых) элементов подматрицы R[Г_i^k/Г_j^k] расположенных в разных строках и столбцах рассматриваемой подматрицы, где R[Г_i^k/Г_j^k] - подматриц матрицы R исходного графа, расположенная на пересечении строк, соответствующих вершинам X_i є Г_i, и столбцов, соответствующих вершинам X_j є U_j.

4. Объединение групп Г_i^k и Г_j^k

Определение изоморфных подграфов, имеющих мощность t=k+2, k=0.

В результате объединения на первом шаге образуются три группы изоморфных подграфов:

Г₁¹ = {Х1-Х2, Х5-Х4, Х7-Х8} t=2

Г₂¹ = {Х1-ХЗ, Х4-Х6, Х7-Х9} t=2

Г₃¹ = {Х2-ХЗ, Х5-Х6, Х8-Х9} t=2

5. k=ki+1 - переход к следующему шагу наращивания изоморфных подграфов.

k = 1

6. Для каждой группы Г_i¹ находится исходный массив вершин M_i⁰ для дальнейшего рассмотрения изоморфных подграфов данной группы. Такой массив составляется из вершин, не вошедших в рассматриваемую группу изоморфных подграфов, причем мощность исходного массива (число вершин, входящих в массив, входящих в массив) должно быть не менее двух.

Имеем:

M_i^R = X*/Г_i^R

М₁⁰ = (ХЗ, X6, X9) для Г₁¹

М₂⁰ = (Х2, Х5, Х8) для Г₂¹

М₃⁰ = (Х1, Х4, Х7) для Г₃¹

7. Исходный массив M_i⁰ разбивается на группы равно вариантных вершин Г_ij⁰, аналогично пункту 1.

Г₁₁⁰ = {ХЗ, Х6, Х9} для Г₁¹

Г₂₁⁰ = {Х2, Х5, Х8} для Г₂¹

Г₃₁⁰ = {Х1, Х4, Х7} для Г₃¹

8. Определяются группы Г_Mi^R с мощностью t=1 и исключаются из дальнейшего рассмотрения.

9. Для каждого массива M*^R_i проверяется условие M*^R_i≠0. Если условие для всех массивов не выполняется, то дальнейшее наращивание изоморфных подграфов невозможно, т.к. отсутствуют равно вариантные вершины. В этом случае переход к 11. Если хотя бы для одного массива условие выполняется - переход к 10.

10. Каждая группа изоморфных подграфов Г_i¹ поочередно объединяются со всеми группами Г_ij⁰ своего исходного массива.

k = 1- второй шаг массива.

На основе подматриц каждого объединения Г_i¹ U Г_ij⁰ определяются группы изоморфных подграфов, имеющих мощность t=k+2 аналогично пункту 4.

Получаем три группы изоморфных подграфов с числом вершин в каждом графе, равном 3.

Г¹₂={Х1Х2ХЗ, Х4Х5Х6, Х7Х8Х9}

Г²₂= {Х1ХЗХ2, Х4Х6Х5, Х7Х9Х8}

Г²₃= {Х2ХЗХ1, Х5Х6Х4, Х8Х9Х7}

Так как ни для какой Г_i² нет исходного массива, то процесс наращивания мощности изоморфных подграфов прекращается.

11. Конец работы алгоритма.

В результате работы алгоритма из исходного графа выделено три группы изоморфных подграфов Г²₁, Г²₂, Г²₃. Анализ этих групп показывает, что они полностью совпадают, то есть по существу, выделяется одна группа, состоящая из трех изоморфных подграфов.

1.2. Итерационный алгоритм разбиения графа G с использованием чисел связности.

Сформулируем задачу компоновки КС как задачу разбиения графа G=(X,U) на подграфы G_i и G_j.

Подмножество ребер, попадающих в сечение (разрез графа) называется числом реберного соединения частей G_i и G_j графа G и обозначается K_ij.

Задачей разбиения графа G=(X,U) является нахождение такой совокупности чисел, чтобы число реберного соединения графа G удовлетворяло заданному критерию оптимальности, а именно

- стремится к минимуму

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

Алгоритмы классифицируют по критериям, по ограничениям на формирование частей или по структуре вычислительной процедуры. С этой точки зрения их делят на последовательные (1), параллельно-последовательные (2) и итерационные (3).

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

2) Сначала выделяется некоторое исходное множество групп элементов, которое затем распределяется по частям с учетом критериев и ограничений на компоновку.

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

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

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

Назовем α_K - числом связности вершины Х_K

α_к= { r_K(G_i) - r_K(G_j), если Хк є X_j [ Ф. 1.]

{ r_K(G_j) - r_K(G_i), если Хк є X_i

(Σ внешних ребер — Σ внутр. ребер)

r_K(G_i) - число ребер, соединяющих вершины Х_K с вершинами G_i=(X_i,U_i) r_K(G_j) - число ребер, соединяющих вершину Х_K с вершинами G_j=(X_j,U_j).

ФИЗИЧЕСКИЙ СМЫСЛ:

если α(X_i) = -1 означает, что при перестановке вершины X_i , лежащей в G₁, в G₂ число внешних ребер увеличится на 1.

α(X_j) = 0 означает, что перестановка вершин X_j из G₁ в G₂ оставит без изменения число соединительных ребер.

α(Х_K) = 3 означает, что при переносе число соединительных ребер уменьшится на 3.

Для разбиения графа на два подграфа с минимизацией числа соединительных ребер с использованием чисел связности известна теорема.

ТЕОРЕМА:

Перестановка двух произвольных вершин Х_K є X_i и X₁ є X_j(X_i∩X_j)≠0 - приводим к уменьшению числа соединительных ребер между G_i и G_j, если:

а) вершина Х_K не смежная с вершиной X₁ и выполняется

неравенство α_K + α₁ > 0;

б) вершина Х_K смежная с вершиной Xi и справедливо

неравенство α_K + α₁ > 2r_1,K.

ЦЕЛЕВАЯ ФУНКЦИЯ:

Минимизация суммарного числа соединительных ребер.

Для более удобного определения подстановки строят матрицу:

в которой строки определяются вершинами из множества I , а столбцы - из множества V_i є N= {1,2,...,l-1}

На пересечении строки k строки (k є I) и q столбца (q є V) находится элемент:

[Ф.2.]

Элемент матрицы W ω_k,q характеризует изменение числа соединительных ребер между G_i и G_j при перестановке вершин X_q є X_i и Х_k є X_j.

Пример 1.

2 2

G=(X,U)

Исходный граф разбить на два подграфа: G₁ (X₁, U₁) и G₂ (X₂, U₂)

|X1| = 4

|X2| = 3

1) Строим матрицу смежности R₀

R₁

R₂

2) Разбиваем R₀ на подматрицы R₁ и R₂ и определяем числа связности по формуле [Ф.1.].

Например: для вершины X₁, находящейся в R₁

α = 4 - 1= + 3.

3) Строим матрицу W₀, определяя элементы матрицы по [Ф.2.] Например: для вершин X1 и Х5 (+3+4-2×2=+3)

Из матрицы W₀ получается, что для минимизации числа соединительных ребер между G₁ и G₂ графа G в матрице R₀ необходимо переставить строки и столбцы X1 и Х7, поскольку ω_1,7 = +6 матрицы W₀ наибольший.

4) После выполнения указанной процедуры матрица R₀ примет следующий вид:

Аналогично п.2 и п.3 определяем α и W₀.

Меняем местами Х3 и Х6.

5)

Теперь когда все числа α_k,q≤0, строить матрицу W₀ - не будем, т.к. в ней не найдется ни одного элемента ω_k,q>0 и, следовательно, в графе G на данном шаге нет пары вершин, перестановка которых уменьшит K_i,j.

В результате получим: в матрицах R₁ |X1| = 4

R₂ |X2| = 3

2

R1

2

R2