На рис. 1.5 наведений зважений граф схеми (ЗГС). Він складається з: вершин, відповідних елементам D₀ , D₁ ,... …, D₉ , і ребер, що з'єднають ці вершини. Ребро, що з'єднує вершини графа D_i і D_j з приписаною йому вагою, показує наявність і кількість зв'язків між елементами схеми E_i і E_j .

Рисунок. 1.5 - - Зважений граф схеми

ЗГС можна уявити в вигляді матриці сполучень R (рис 1.6):

R=¦¦ r ¦¦ _{m ´ m} , r_ij - число зв'язків D_i і D_j .

Матриця R симетрична відносно головної діагоналі. Крім Того rii=0, i=0, …, m-1.

0	1	2	3	4	5	6	7
0	0	4	0	4	2	7	7	7
1	4	0	1	0	0	2	0	0
2	0	1	0	1	0	2	0	2
3	4	0	1	0	0	0	0	2
4	2	0	0	0	0	2	3	0
5	7	2	2	0	2	0	1	0
6	7	0	0	0	3	1	0	0
7	7	0	2	2	0	0	0	0

Рис. 1.6 - Матриця сполучень

2 КОМПОНОВКА ЕЛЕМЕНТІВ СХЕМИ В ВУЗЛИ

2.1 Послідовний алгоритм компоновки

Компоновка елементів може здійснюватися різноманітними методами. В курсовій роботі застосований послідовний алгоритм компоновки.

Сутність задачі полягає в розподілі комутаційної схеми на частини (вузли) з наступними обмеженнями: кількість елементів (КЕ) вузла не повинна перевищувати 6, кількість зовнішніх виводів (В) вузла повинно бути менш або рівно 17. В алгоритмі закладений принцип мінімізації зовнішніх виводів вузла при максимізації внутрішньо вузлових зв'язків.

Послідовність рішення.

1. Перед початком компоновки безліч нерозподілених елементів включає D0 (фіктивний елемент, що об'єднує всі зовнішні виводи схеми), D1, D2, D3, D4, D5, D6, D7.

2. Фіктивний елемент D0 назначаємо в фіктивний вузол T0 (r=0). Після цієї безлічі нерозподілених елементів Ir= (D1, D2, D3, D4, D5, D6, D7).

3. Починаємо компоновку вузла Т1 (r=1) (табл. 2.1):

А) для кожного з нерозподілених елементів (безліч Ir при r=1) обчислюємо функціонал L1 - кількість електричних ланцюгів (комплексів), якими даний елемент Xr зв'язаний з безліччю ще нерозподілених.

де

Ir - безліч нерозподілених елементів.

В якості базового елементу вузла Tr (при r=1) вибираємо перший по порядку елемент з максимальним значенням L1. Це D2. Елемент D2 виключаємо з безлічі нерозподілених елементів Ir (r=1).

Б) для кожного з нерозподілених елементів розраховуємо значення функціонала L2, що показує число зовнішніх зв'язків вузла (отриманого доданням до вже розподіленого елементу D2 чергового кандидата) з безліччю інших елементів схеми, включаючи D0.

Кількість зовнішніх висновків вузла рівно числу ланцюгів, що зв'язують елементи вузла з елементами, що не входять до вузла. Ті елементи, для яких здійсненна умова L2 В, (де В=17), виключаються на даному кроку з числа кандидатів в вузол, що формується; ці елементи позначені зірочкою.

де - вузол з l елементами;

Ts - вузли ,що сформувалися;

.

Для кандидатів ,що залишилися розраховуємо функціонал L3. Функціонал L3 - це число ланцюгів, що з'єднують розглядуваний елемент-кандидат з безліччю елементів даного вузла. Для призначення в вузол вибираємо той елемент, що має максимальне значення L3. Якщо таких елементів декілька, то слід вибирати перший по порядку, що має найменшу величину L2. На даному кроку це D5.

Елемент D5 виключаємо з безлічі нерозподілених. Отже, в перший вузол тепер розподілені елементи D2 і D5. Формування вузла буде завершене, коли число елементів в ньому досягне даного (КЕ=5), або не знайдеться жодного кандидата, додавання якого не порушить умови L2£ В (B=17).

В) Для елементів ,що залишилися нерозподіленими, розраховуємо функціонали - L2, L3. По вище наведеним правилам визначаємо черговий елемент вузла D4.

Г) В результаті аналогічних розрахунків визначаємо наступний елемент вузла Т1-D1. На цьому компоновка першого вузла завершена, тому що додавання наступного кандидату порушить умову L2£ В (B=17).

Виконуємо компоновку вузла Т2 (табл. 2.1, r=2.). Закінчення формування