На первичной сети, структура которой определена графом (рис 5.1), зада- Матрица требований Ф = ||

На первичной сети, структура которой определена графом (рис 5.1), зада- Матрица требований Ф = || φij || , где φij - требуемое число каналов в пу- тях передачи от УКi к УКj . Ненулевые элементы матрицы Ф: φ24 = 30;φ16 = 30; φ35 = 20; Емкости ребер ukl в числе каналов первичной сети, заданные весами ре- бер на графе. Рис 5.1 Требуется найти план распределения каналов (ПРК), удовлетворяющий матрице требований Ф, при условии использования только кратчайших путей

Из рис 5.1 определяем кратчайшие пути. Для φ24 = 30 их 2 (k=2): μ12,6,4; μ22,3,4;
Для φ16 = 30 их 2 (k=2): μ11.2,6; μ21.5,6;
Для φ35 = 20 их 1 (k=1): μ1345
Определим число каналов, необходимое для обслуживания данного пото- ка, распределяя общее число каналов равномерно на k путей, обозначая их через Х.
Х12,6,4= Х22,34,= φ24 / k = 30 / 2 =15
Х112,6= Х2156 ,= =φ16 / k = 30 / 2 =15
Х1345=φ35 / k = 20.
Составляем матрицу C емкостей кратчайших путей и ребер для сделанного
идеального ПРК, представленную в таблице 5.1.
Подсчитываем для каждого ребра bij его емкость, полученную в результате загрузки в соответствии с идеальным ПРК, и в графе Xij ставим со знаком "+" то число каналов, которое осталось незагруженным (ненасыщенные ребра) и со знаком "-" число каналов, на которое загрузки ребра в соответствии с идеальным ПРК превышают заданное число каналов в ребре.
Таблица 5.1
ij
Ёмкость
пути
1-2 1-5 1-6 2-3 2-6 3-4 4-6 4-5 5-6
24
Х1264
15
15
Х2234
15
15
16 Х1126 15
15
Х2156
15
15
35 Х1345
20
20
1ij
+2 +2 +2 +20 -12 -12 +20 +2 +2 ПКР не допустим
2ij
+20 +20 +2 +2 -12 +2 +2 +2 +20 ПКР не допустим
3ij
+1 +1 +1 +1 +1 -16 +1 +24 +1 ПКР не допустим
По матрице идеального ПРК определяем, что перенасыщенные(желтым) ветви соответствуют пути:
Выписываем, какой паре УК соответствует первый из найденных в п.7 путей(1-3), и определяем, есть ли кратчайший путь, соответствующий данной паре, состоящий из ненасыщенных ребер.
Если такой путь найден, то переходим к п