Розподіл сполучень по шарам полягає в виділенні на кожному кроку сполучення з максимальним числом пересічень і вилучення його на другий шар. Сполучення переносяться з першого шару на другий до тих пір, доки не будуть усунені всі пересічення.
При виконанні розшарування необхідно отримати граф пересічень, вершини якого відповідають окремим провідникам, а ребра - їхнім пересіченням. Побудуємо граф пересічень схеми сполучень, наведеної на рис. 5.1.
Граф пересічень (рис. 5.2) можна уявити в вигляді матриці пересічень П=|| n || k´k (рис. 5.3), де
Якщо провідник i перетинається з провідником j;
В противному випадку.
Рисунок. 5.1 - Комутаційна схема сполучень вузла Т1
Рисунок. 5.2 - Граф пересічень
| V1 | V6 | V7 | V8 | V9 | V10 | V11 | V13 | V14 | V15 | V16 | V17 | V18 | V19 | V20 | V21 | V22 | V23 | V24 | ||
V1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| ||
V6 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| ||
V7 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| ||
V8 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| ||
V9 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| ||
V10 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| ||
V11 |
|
|
|
|
|
|
| 1 |
|
|
|
|
|
|
|
| 1 |
|
| ||
V13 |
|
|
|
|
|
| 1 |
|
|
|
|
|
|
|
|
| 1 |
|
| ||
V14 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| ||
V15 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| 1 | 1 |
| ||
V16 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| ||
V17 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| ||
V18 |
|
|
|
|
|
|
|
|
|
|
|
|
|
| 1 | 1 |
|
|
| ||
V19 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| ||
V20 |
|
|
|
|
|
|
|
|
|
|
|
| 1 |
|
|
|
|
|
| ||
V21 |
|
|
|
|
|
|
|
|
|
|
|
| 1 |
|
|
|
|
|
| ||
V22 |
|
|
|
|
|
| 1 | 1 |
| 1 |
|
|
|
|
|
|
|
|
| ||
V23 |
|
|
|
|
|
|
|
|
| 1 |
|
|
|
|
|
|
|
| 1 | ||
V24 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| 1 |
|
Рисунок. 5.3 - Матриця пересічень
По матриці П будуємо вектор-стовпчик Е1, з нього вибираємо максимальний елемент; якщо їх декілька, то береться будь-який. Отже, беремо елемент V22 і на його місце записуємо нуль, що відповідає переносу провідника V22 на другий шар. По матриці П визначаються ребра, і в векторі-стовпчикові Е1 значення елементів, відповідних цим провідникам, зменшуються на 1, т.т. в матриці П викреслюється стовпчик, відповідний провіднику 16. Одержуємо стовпчик Е2 після першого кроку алгоритму. З стовпчика Е2 вибираємо елемент V18 і процедура повторюється, доки не дістанемося стовпчика Е5, всі елементи якого дорівнюють нулю.
|
|
| V11 | 2 |
| V11 | 1 |
| V11 | 1 |
| V11 | 1 |
| V11 | 0 |
| V13 | 2 |
| V13 | 1 |
| V13 | 1 |
| V13 | 1 |
| V13 | 0 |
| V15 | 2 |
| V15 | 1 |
| V15 | 1 |
| V15 | 0 |
| V15 | 0 |
| V18 | 2 |
| V18 | 2 |
| V18 | 0 |
| V18 | 0 |
| V18 | 0 |
E1= | V20 | 1 | E2= | V20 | 1 | E3= | V20 | 0 | E4= | V20 | 0 | E5= | V20 | 0 |
| V21 | 1 |
| V21 | 1 |
| V21 | 0 |
| V21 | 0 |
| V21 | 0 |
| V22 | 3 |
| V22 | 0 |
| V22 | 0 |
| V22 | 0 |
| V22 | 0 |
| V23 | 2 |
| V23 | 2 |
| V23 | 2 |
| V23 | 0 |
| V23 | 0 |
| V24 | 1 |
| V24 | 1 |
| V24 | 1 |
| V24 | 0 |
| V24 | 0 |
Рисунок. 5.4 - Вектори - стовпчики Е для 2-го шару
Після перенесення провідників V11, V18, V22, V23 на другий шар отримаємо двошаровий розподіл сполучень схеми.
Далі проводиться розподіл по другому шару аналогічно
Рисунок. 5.5 Граф пересічень шара 2
| V11 | V18 | V22 | V23 |
V11 |
|
| 1 |
|
V18 |
|
|
|
|
V22 | 1 |
|
|
|
V23 |
|
|
|
|
Рисунок. 5.6 - Матриця пересічень шара 2
Не будуючи вектори Е, можна зразу перенести V11 в 3-ій шар.
РОЗРОБКА БІБЛІОТЕКИ ЕЛЕМЕНТІВ В САПР PCAD