Домашнее задание, страница 2

δ(DD2) = 2 – 1 = 1

δ(DD4) = 1 – 1 = 0

δ(R1) = 2 – 1 = 1

δ(R2) = 2 – 1 = 1

δ(DD4) = min [δ(DD1); δ(DD2); δ(DD4); δ(R1); δ(R2)] = 0, поэтому добавляем к множеству X₁ элемент DD4.

5. X₁={X1, C1, C2, DD3, DD4}

|X₁| = 5

Условие |X₁| < K не выполняется, заканчиваем работу алгоритма.

Рис.8. Заключительный шаг алгоритма.

Схема разбита на 2 подсхемы:

X₁={ X1, C1, C2, DD3, DD4} – число внутрисхемных связей 6

X₂={DD1, R1, DD2, R2} – число внутрисхемных связей 6

Число межмодульных связей – 4.

Приведем матрицу соответствия элементов и подсхем:

Построим разрезанный мультиграф согласно полученным результатам:

Рис.9. Полученный результат работы алгоритма.

Найдем и обозначим цепи на принципиальной схеме:

Рис.10. Обозначение цепей на схеме

Покажем, какие элементы каким цепям принадлежать:

А1: {C1},{X1},{DD3}

А2: {C2},{X1},{DD3}

А3: {DD3}, {DD4}

А4: {DD1}, {R1}, {DD3}

А5: {DD2}, {R2}, {DD3}

Составим матрицу инцидентности:

Построим Кенигово представление гиперграфа рассматриваемой схемы, которое будет представлять собой двудольный граф – отображения множество вершин (элементов) в множество ребер (цепей).

Рис.11. Кенигово представление графа

Учтем связи элементов «Источник» - «Получатель» электрического сигнала и получим ориентированный гиперграф.

Рис.12. Ультиграф схемы

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

Зададим начальные условия:

Размер подсхемы - K=5

Количество подсхем - N_k=2

1. Выбираем в качестве начальной вершину, входящую в максимальное количество цепей – DD3.

X₁={DD3}

Посчитаем количество элементов множества X₁:

|X₁|=1

Условие |Y1|<K выполняется, продолжаем работу алгоритма.

Рис.13. Первый шаг алгоритма

Определяем множество цепей, инцидентных множеству X₁:

Г(X₁)={A1, A2, A3, A4, A5}

Определяем множество вершин, инцидентных множеству цепей Г(X₁) / {DD3}:

Г*(X₁)={DD1, DD2, DD4, R1, R2, C1, C2, X1}

Определяем, сколько цепей пересекутся в случае выбора того или иного элемента:

S_DD1= | Г(DD3, DD1) ∩ Г(DD2, DD4, R1, R2, C1, C2, X1) | = | {A1, A2, A3, A4, A5} ∩ { A1, A2, A3, A4, A5}| = |{ A1, A2, A3, A4, A5}| = 5

S_DD2= | Г(DD3, DD2) ∩ Г(DD1, DD4, R1, R2, C1, C2, X1) | = | {A1, A2, A3, A4, A5} ∩ { A1, A2, A3, A4, A5}| = |{ A1, A2, A3, A4, A5}| = 5

S_DD4= | Г(DD3, DD4) ∩ Г(DD1, DD2, R1, R2, C1, C2, X1) | = | {A1, A2, A3, A4, A5} ∩ { A1, A2, A4, A5}| = |{ A1, A2, A4, A5}| = 4

S_R1= | Г(DD3, R1) ∩ Г(DD1, DD2, DD4, R2, C1, C2, X1) | = | {A1, A2, A3, A4, A5} ∩ { A1, A2, A3, A4, A5}| = |{ A1, A2, A3, A4, A5}| = 5

S_R2= | Г(DD3, R2) ∩ Г(DD1, DD2, DD4, R1, C1, C2, X1) | = | {A1, A2, A3, A4, A5} ∩ { A1, A2, A3, A4, A5}| = |{ A1, A2, A3, A4, A5}| = 5

S_C1= | Г(DD3, C1) ∩ Г(DD1, DD2, DD4, R1, R2, C2, X1) | = | {A1, A2, A3, A4, A5} ∩ { A1, A2, A3, A4, A5}| = |{ A1, A2, A3, A4, A5}| = 5

S_C2= | Г(DD3, C2) ∩ Г(DD1, DD2, DD4, R1, R2, C1, X1) | = | {A1, A2, A3, A4, A5} ∩ { A1, A2, A3, A4, A5}| = |{ A1, A2, A3, A4, A5}| = 5

S_X1= | Г(DD3, X1) ∩ Г(DD1, DD2, DD4, R1, R2, C1, C2) | = | {A1, A2, A3, A4, A5} ∩ { A1, A2, A3, A4, A5}| = |{ A1, A2, A3, A4, A5}| = 5

S_DD4= min [S_DD1, S_DD2, S_DD4, S_R1, S_R2, S_C1, S_C2, S_X1] = 4, выбираем элемент DD4 и добавляем его в множество X₁

2. X₁={DD3, DD4}

Посчитаем количество элементов множества X₁:

|X₁|=2

Условие |Y1|<K выполняется, продолжаем работу алгоритма.

Рис.14. Второй шаг алгоритма

Определяем множество цепей, инцидентных множеству X₁:

Г(X₁)={A1, A2, A3, A4, A5}

Определяем множество вершин, инцидентных множеству цепей Г(X₁) / {DD3, DD4}:

Г*(X₁)={DD1, DD2, R1, R2, C1, C2, X1}

Определяем, сколько цепей пересекутся в случае выбора того или иного элемента:

S_DD1= | Г(DD3, DD1, DD4) ∩ Г(DD2, R1, R2, C1, C2, X1) | = | {A1, A2, A3, A4, A5} ∩ { A1, A2, A4, A5}| = |{ A1, A2, A4, A5}| = 4

S_DD2= | Г(DD3, DD2, DD4) ∩ Г(DD1, R1, R2, C1, C2, X1) | = | {A1, A2, A3, A4, A5} ∩ { A1, A2, A4, A5}| = |{ A1, A2, A4, A5}| = 4

S_R1= | Г(DD3, R1, DD4) ∩ Г(DD1, DD2 , R2, C1, C2, X1) | = | {A1, A2, A3, A4, A5} ∩ { A1, A2, A4, A5}| = |{ A1, A2, A4, A5}| = 4

S_R2= | Г(DD3, R2, DD4) ∩ Г(DD1, DD2, R1, C1, C2, X1) | = | {A1, A2, A3, A4, A5} ∩ { A1, A2, A4, A5}| = |{ A1, A2, A4, A5}| = 4

S_C1= | Г(DD3, C1, DD4) ∩ Г(DD1, DD2, R1, R2, C2, X1) | = | {A1, A2, A3, A4, A5} ∩ { A1, A2, A4, A5}| = |{ A1, A2, A4, A5}| = 4

S_C2= | Г(DD3, C2, DD4) ∩ Г(DD1, DD2, R1, R2, C1, X1) | = | {A1, A2, A3, A4, A5} ∩ { A1, A2, A4, A5}| = |{ A1, A2, A4, A5}| = 4

S_X1= | Г(DD3, X1, DD4) ∩ Г(DD1, DD2, R1, R2, C1, C2) | = | {A1, A2, A3, A4, A5} ∩ { A1, A2, A4, A5}| = |{ A1, A2, A4, A5}| = 4

S_X1= min [S_DD1, S_DD2, S_R1, S_R2, S_C1, S_C2, S_X1] = 4, выбираем элемент X1 и добавляем его в множество X₁

3. X₁={DD3, DD4, X1}

Посчитаем количество элементов множества X₁:

|X₁|=3

Условие |Y1|<K выполняется, продолжаем работу алгоритма.

Рис.15. Третий шаг алгоритма

Определяем множество цепей, инцидентных множеству X₁:

Г(X₁)={A1, A2, A3, A4, A5}

Определяем множество вершин, инцидентных множеству цепей Г(X₁) / {DD3, DD4, X1}:

Г*(X₁)={DD1, DD2, R1, R2, C1, C2}

Определяем, сколько цепей пересекутся в случае выбора того или иного элемента:

S_DD1= | Г(DD3, DD1, DD4, X1) ∩ Г(DD2, R1, R2, C1, C2) | = | {A1, A2, A3, A4, A5} ∩ { A1, A2, A4, A5}| = |{ A1, A2, A4, A5}| = 4

S_DD2= | Г(DD3, DD2, DD4, X1) ∩ Г(DD1, R1, R2, C1, C2) | = | {A1, A2, A3, A4, A5} ∩ { A1, A2, A4, A5}| = |{ A1, A2, A4, A5}| = 4

S_R1= | Г(DD3, R1, DD4, X1) ∩ Г(DD1, DD2 , R2, C1, C2) | = | {A1, A2, A3, A4, A5} ∩ { A1, A2, A4, A5}| = |{ A1, A2, A4, A5}| = 4

S_R2= | Г(DD3, R2, DD4, X1) ∩ Г(DD1, DD2, R1, C1, C2) | = | {A1, A2, A3, A4, A5} ∩ { A1, A2, A4, A5}| = |{ A1, A2, A4, A5}| = 4

S_C1= | Г(DD3, C1, DD4, X1) ∩ Г(DD1, DD2, R1, R2, C2) | = | {A1, A2, A3, A4, A5} ∩ { A2, A4, A5}| = |{ A2, A4, A5}| = 3

S_C2= | Г(DD3, C2, DD4, X1) ∩ Г(DD1, DD2, R1, R2, C1) | = | {A1, A2, A3, A4, A5} ∩ { A1, A4, A5}| = |{ A1, A4, A5}| = 3

S_C2= min [S_DD1, S_DD2, S_R1, S_R2, S_C1, S_C2] = 3, выбираем элемент C2 и добавляем его в множество X₁

4. X₁={DD3, DD4, X1, C2}

Посчитаем количество элементов множества X₁:

|X₁|=4

Условие |Y1|<K выполняется, продолжаем работу алгоритма.

Рис.16. Четвертый шаг алгоритма

Определяем множество цепей, инцидентных множеству X₁:

Г(X₁)={A1, A2, A3, A4, A5}

Определяем множество вершин, инцидентных множеству цепей Г(X₁) / {DD3, DD4, X1, C2}:

Г*(X₁)={DD1, DD2, R1, R2, C1}

Определяем, сколько цепей пересекутся в случае выбора того или иного элемента:

S_DD1= | Г(DD3, DD1, DD4, X1, C2) ∩ Г(DD2, R1, R2, C1) | = | {A1, A2, A3, A4, A5} ∩ { A1, A4, A5}| = |{ A1, A4, A5}| = 3

S_DD2= | Г(DD3, DD2, DD4, X1, C2) ∩ Г(DD1, R1, R2, C1) | = | {A1, A2, A3, A4, A5} ∩ { A1, A4, A5}| = |{ A1, A4, A5}| = 3

S_R1= | Г(DD3, R1, DD4, X1, C2) ∩ Г(DD1, DD2 , R2, C1) | = | {A1, A2, A3, A4, A5} ∩ { A1, A4, A5}| = |{ A1, A4, A5}| = 3

S_R2= | Г(DD3, R2, DD4, X1, C2) ∩ Г(DD1, DD2, R1, C1) | = | {A1, A2, A3, A4, A5} ∩ { A1, A4, A5}| = |{ A1, A4, A5}| = 3

S_C1= | Г(DD3, C1, DD4, X1, C2) ∩ Г(DD1, DD2, R1, R2) | = | {A1, A2, A3, A4, A5} ∩ { A4, A5}|

=|{ A4, A5}| = 2

S_C1= min [S_DD1, S_DD2, S_R1, S_R2, S_C1] = 2, выбираем элемент C1 и добавляем его в множество X₁

Рис.17. Пятый шаг алгоритма

Получили результат, аналогичный полученному ранее в случае разбиения мультиграфа:

Схема разбита на 2 подсхемы:

X₁={ X1, C1, C2, DD3, DD4} – число внутрисхемных связей 6

X₂={DD1, R1, DD2, R2} – число внутрисхемных связей 6

Число межмодульных связей – 4.

Размещение.

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

Рис.18. Поле размещения

Матрица расстояний графа имеет вид: