Контрольная
.doc
Московский Технический Университет
Связи и Информатики
_____________________________________________
Факультет информационных технологий
Кафедра защиты информации и техники почтовой связи
Контрольная работа
по дисциплине
«СУДО»
Студент Дмитриев В. Ю.
Группа УИ0301
Принял Князютенков В. А.
Москва, 2006
I. Задание
1. Расчет по операциям алгоритма Дейкстра [1] ДКП, кратчайшего по расстояниям прохождения почты в сети МПП (рис.1).
2. Представление полученного ДКП в маршрутной структуре.
3. Нагружение полученного по п.2 N-гo ДКП струями N-й строки матрицы обменов : проставление возле каждого узла дерева двух характеристик его пометки - струи обмена ( количества почты, исходящей из корня дерева и направленной в данный узел) и номера последнего узла перегружения почты с маршрута на маршрут в пути от корня дерева до данного узла - получателя .
4. Расчеты узловых и маршрутных суммарных потоков для корня дерева - исходящего суммарного потока, для каждого из узлов дерева, где перегружается почта - суммы его транзита, а по задействованным в дереве маршрутам - суммарного количества почты на каждом участке каждого такого маршрута .
II. Исходные данные для расчетов
1. Расчет N - го дерева путей, кратчайшего по расстояниям перевозки выполняется по фрагменту сети МПП ( Л.1, рис 13, с. 41 )
2. Представление полученного ДКП в маршрутной структуре (п.2 задания) выполняется заменой связей в дереве по дугам на связи по маршрутам из рис. 1 фрагмента сети МПП, наилучшим образом покрывающих дуговые связи дерева (минимальным количеством покрывающих маршрутов)
3. Данные по значениям струй обмена (для нагружения ими N-го ДКП)
матрицы обменов для фрагмента сети МПП представлены в табл. 1.
Табл. 1. Значения струй обмена по строкам матрицы обменов
|
№ стр. |
№ узла получат. |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
сумма |
|
Наим. корня ДКП |
|||||||||||||||||
|
13 |
Оренбургск. |
14 |
13 |
8 |
8 |
15 |
9 |
12 |
9 |
14 |
15 |
16 |
10 |
17 |
14 |
6 |
180 |
III. Расчетная часть
1. Расчет по операциям алгоритма Дейкстра ДКП, кратчайшего по расстояниям прохождения почты в сети МПП
Расчет производим по графу сети на рис. 2.
Шаг 0. Узел 13 является корнем дерева.
Шаг 1. L’13-11=min(77.6,41.8,60.0)=41.8=(L13-11,13)
Шаг 2. Дуга 13-11 переводится в дерево.
Шаг 3. Дерево состоит из одной дуги 13-11.
Шаг 4. L’13-5:=min(L’13-5,L13-11+l11-5)=min(77.6,∞)=77.6
L’13-12:=min(L’13-12,L13-11+l11-12)=min(∞,41.8+13.6)=55.4
L’13-12:=min(L’13-12,L13-5+l5-12)=min(∞,77.6+30.1)=107.7
L’13-10:=min(L’13-10,L13-11+l11-10)=min(41.8+52.3,41.8+52.3)=94.1
L’13-15:=min(L’13-15,L13-11+l11-15=min(60.0,∞)=60.0
Шаг 1. L’13-12=min(77.6,55.4, 107.7,94.1,60.0)=55.4=(L13-12,13)
Шаг 2. Дуга 11-12 переводится в дерево.
Шаг 3. Дерево составляют две дуги: 13-11 и 11-12.
Шаг 4. L’13-5:=min(L’13-5,L13-12+l12-5)=min(77.6,55.4+30.1)=77.6
L’13-6:=min(L’13-6,L13-12+l12-6)=min(∞,55.4+30.7)=86.1
L’13-6:=min(L’13-6,L13-7+l7-6)=min(∞,80.7+14.2)=94.9
L’13-6:=min(L’13-6,L13-9+l9-6)=min(∞,70.7+27.2)=97.9
L’13-7:=min(L’13-7,L13-12+l12-7)=min(∞,55.4+25.3)=80.7
L’13-7:=min(L’13-7,L13-6+l6-7)=min(∞,86.1+14.2)=100.3
L’13-9:=min(L’13-9,L13-10+l10-9)=min(∞,100.4+63.0)=163.4
L’13-9:=min(L’13-9,L13-6+l6-9)=min(∞,55.4+27.2)=82.6
L’13-9:=min(L’13-9,L13-12+l12-9)=min(∞,55.4+15.3)=70.7
L’13-10:=min(L’13-10,L13-11+l11-10)=min(∞,41.8+52.3)=94.1
L’13-10:=min(L’13-10,L13-9+l9-10)=min(∞,70.7+63)=133.7
L’13-15:=min(L’13-15,L13-12+l12-15)=min(60.0,55.4+115.4)=60.0
Шаг 1. L’13-15=min(77.6,86.1,94.9,97.9,80.7,100.3,163.4,82.6,70.7,94.1,133.7,60.0)=60.0=(L13-15,13)
Шаг 2. Дуга 13-15 переводится в дерево.
Шаг 3. Дерево составляют три дуги: 13-11, 11-12 и 13-15.
Шаг 4. L’13-5:=min(L’13-5,L13-15+l15-5)=min(77.6,60.0+137.6)=77.6
L’13-5:=min(L’13-5,L13-12+l12-5)=min(77.6,55.4+30.1)=85.5
L’13-6:=min(L’13-6,L13-12+l12-6)=min(∞,55.4+30.7)=86.1
L’13-6:=min(L’13-6,L13-7+l7-6)=min(∞,80.7+14.2)=94.9
L’13-6:=min(L’13-6,L13-9+l9-6)=min(∞,70.7+27.2)=97.9
L’13-6:=min(L’13-6, L13-15+l15-6)=min(∞,60.0+146.1)=206.1
L’13-7:=min(L’13-7,L13-12+l12-7)=min(∞,55.4+25.3)=80.7
L’13-7:=min(L’13-7,L13-6+l6-7)=min(∞,86.1+14.2)=100.3
L’13-7:=min(L’13-7,L13-15+l15-7)=min(∞,60+140.7)=200.7
L’13-9:=min(L’13-9,L13-10+l10-9)=min(∞,100.4+63.0)=163.4
L’13-9:=min(L’13-9,L13-6+l6-9)=min(∞,55.4+27.2)=82.6
L’13-9:=min(L’13-9,L13-12+l12-9)=min(∞,55.4+15.3)=70.7
L’13-9:=min(L’13-9,L13-15+l15-9)=min(∞,60.0+130.7)=190.7
L’13-10:=min(L’13-10,L13-15+l15-10=min(∞,60+75.6)=135.6
L’13-10:=min(L’13-10,L13-11+l11-10)=min(∞,41.8+52.3)=94.1
L’13-10:=min(L’13-10,L13-9+l9-10)=min(∞,70.7+63)=133.7
L’13-14:=min(L’13-14,L13-15+l15-14)=min(∞,60.0+27.5)=87.5
L’13-14:=min(L’13-14,L13-10+l10-14)=min(∞,94.1+48.1)=142.2
Шаг 1. L’13-9=
=min(77.6,85.5,86.1,94.9,206.1,80.7,100.3,200.7,163.4,82.6,70.7,190.7,135.6,94.1,133.7,87.5,142.2)==70.7=(L13-9,13)
Шаг 2. Дуга 12-9 переводится в дерево.
Шаг 3. Дерево составляют 4 дуги: 13-11, 11-12, 13-15 и 12-9.
Шаг 4. L’13-5:=min(L’13-5,L13-9+l9-5)=min(77.6,70.7+45.4)=77.6
L’13-6:=min(L’13-6,L13-9+l9-6)=min(∞,70.7+27.2)=97.9
L’13-6:=min(L’13-6,L13-12+l12-6)=min(∞,55.4+30.7)=86.1
L’13-6:=min(L’13-6,L13-7+l7-6)=min(∞,80.7+14.2)=94.9
L’13-7:=min(L’13-7,L13-9+l9-7)=min(∞,70.7+41.4)=112.1
L’13-7:=min(L’13-7,L13-12+l12-7)=min(∞,55.4+25.3)=80.7
L’13-7:=min(L’13-7,L13-6+l6-7)=min(∞,86.1+14.2)=100.3
L’13-10:=min(L’13-10,L13-9+l9-10)=min(∞,70.7+63.0)=133.7
L’13-10:=min(L’13-10,L13-15+l15-10=min(∞,60+75.6)=135.6
L’13-10:=min(L’13-10,L13-11+l11-10)=min(∞,41.8+52.3)=94.1
L’13-14:=min(L’13-14,L13-9+l9-14)=min(∞,70.7+111.1)=181.8
L’13-14:=min(L’13-14,L13-15+l15-14)=min(∞,60.0+27.5)=87.5
L’13-14:=min(L’13-14,L13-10+l10-14)=min(∞,94.1+48.1)=142.2
Шаг 1. L’13-5=
=min(77.6,97.9,86.1,94.9,112.1,80.7,100.3,133.7,135.6,94.1,181.8,87.5,142.2)=77.6=(L13-5,13)
Шаг 2. Дуга 13-5 переводится в дерево.
Шаг 3. Дерево составляют 5 дуг: 13-11, 11-12, 13-15, 12-9 и 13-5.
Шаг 4. L’13-8:=min(L’13-8,L13-5+l5-8)=min(∞,77.6+19.2)=96.8
L’13-8:=min(L’13-8,L13-7+l7-8)=min(∞,80.7+15.9)=96.6
L’13-8:=min(L’13-8,L13-12+l12-8)=min(∞,55.4+49.2)=104.6
L’13-6:=min(L’13-6,L13-5+l5-6)=min(∞,77.6+60.8)=138.4
L’13-6:=min(L’13-6,L13-9+l9-6)=min(∞,70.7+27.2)=97.9
L’13-6:=min(L’13-6,L13-12+l12-6)=min(∞,55.4+30.7)=86.1
L’13-6:=min(L’13-6,L13-7+l7-6)=min(∞,80.7+14.2)=94.9
L’13-7:=min(L’13-7,L13-5+l5-8-7)=min(∞,77.6+35.1)=112.7
L’13-7:=min(L’13-7,L13-5+l5-12-7)=min(∞,77.6+55.4)=133
L’13-7:=min(L’13-7,L13-9+l9-7)=min(∞,70.7+41.4)=112.1
L’13-7:=min(L’13-7,L13-12+l12-7)=min(∞,55.4+25.3)=80.7
L’13-7:=min(L’13-7,L13-6+l6-7)=min(∞,86.1+14.2)=100.3
L’13-10:=min(L’13-10,L13-5+l5-10)=min(∞,77.6+171.7)=249.3
L’13-10:=min(L’13-10,L13-9+l9-10)=min(∞,70.7+63.0)=133.7
L’13-10:=min(L’13-10,L13-15+l15-10=min(∞,60+75.6)=135.6
L’13-10:=min(L’13-10,L13-11+l11-10)=min(∞,41.8+52.3)=94.1
L’13-14:=min(L’13-14,L13-5+l5-14)=min(∞,77.6+65.1)=142.7
L’13-14:=min(L’13-14,L13-9+l9-14)=min(∞,70.7+111.1)=181.8
L’13-14:=min(L’13-14,L13-15+l15-14)=min(∞,60.0+27.5)=87.5
L’13-14:=min(L’13-14,L13-10+l10-14)=min(∞,94.1+48.1)=142.2
Шаг 1. L’13-7=
=min(96.8,96.6,104.6,138.4,97.9,86.1,94.9,112.7,133,112.1,80.7,100.3,249.3,133.7,135.6,94.1,
142.7,181.8,87.5,142.2)=80.7=(L13-7,13)
Шаг 2. Дуга 12-7 переводится в дерево.
Шаг 3. Дерево составляют 6 дуг: 13-11, 11-12, 13-15, 12-9, 13-5 и 12-7.
Шаг 4. L’13-8:=min(L’13-8,L13-7+l7-8)=min(∞,80.7+15.9)=96.6
L’13-8:=min(L’13-8,L13-5+l5-8)=min(∞,77.6+19.2)=96.8
L’13-8:=min(L’13-8,L13-12+l12-8)=min(∞,55.4+49.2)=104.6
L’13-4:=min(L’13-4,L13-7+l7-4)=min(∞,80.7+39.7)=120.4
L’13-6:=min(L’13-6,L13-7+l7-6)=min(∞,80.7+14.2)=94.9
L’13-6:=min(L’13-6,L13-5+l5-6)=min(∞,77.6+60.8)=138.4
L’13-6:=min(L’13-6,L13-9+l9-6)=min(∞,70.7+27.2)=97.9
L’13-6:=min(L’13-6,L13-12+l12-6)=min(∞,55.4+30.7)=86.1
L’13-10:=min(L’13-10,L13-7+l7-10)=min(∞,80.7+91.2)=171.9
L’13-10:=min(L’13-10,L13-9+l9-10)=min(∞,70.7+63.0)=133.7
L’13-10:=min(L’13-10,L13-15+l15-10=min(∞,60+75.6)=135.6
L’13-10:=min(L’13-10,L13-11+l11-10)=min(∞,41.8+52.3)=94.1
L’13-14:=min(L’13-14,L13-7+l7-14)=min(∞,80.7+139.3)=220
L’13-14:=min(L’13-14,L13-9+l9-14)=min(∞,70.7+111.1)=181.8
L’13-14:=min(L’13-14,L13-15+l15-14)=min(∞,60.0+27.5)=87.5
L’13-14:=min(L’13-14,L13-10+l10-14)=min(∞,94.1+48.1)=142.2
Шаг 1. L’13-6=
=min(96.6,96.8,104.6,120.4,94.9,138.4,97.9,86.1,171.9,133.7,135.6,94.1,220,181.8,87.5,142.2)=86.1=(L13-6,13)
Шаг 2. Дуга 12-6 переводится в дерево.
Шаг 3. Дерево составляют 7 дуг: 13-11, 11-12, 13-15, 12-9, 13-5, 12-7 и 12-6.
Шаг 4. L’13-8:=min(L’13-8,L13-6+l6-8)=min(∞,86.1+30.1)=116.2
L’13-8:=min(L’13-8,L13-7+l7-8)=min(∞,80.7+15.9)=96.6
L’13-8:=min(L’13-8,L13-5+l5-8)=min(∞,77.6+19.2)=96.8
L’13-8:=min(L’13-8,L13-12+l12-8)=min(∞,55.4+49.2)=104.6
L’13-4:=min(L’13-4,L13-7+l7-4)=min(∞,80.7+39.7)=120.4
L’13-4:=min(L’13-4,L13-6+l6-4)=min(∞,86.1+52.6)=138.7
L’13-1:=min(L’13-1,L13-6+l6-1)=min(∞,86.1+41.1)=127.2
L’13-1:=min(L’13-1,L13-7+l7-1)=min(∞,80.7+41.1)=121.8
L’13-10:=min(L’13-10,L13-6+l6-10)=min(∞,86.1+90.2)=176.3
L’13-10:=min(L’13-10,L13-9+l9-10)=min(∞,70.7+63.0)=133.7
L’13-10:=min(L’13-10,L13-15+l15-10=min(∞,60+75.6)=135.6
L’13-10:=min(L’13-10,L13-11+l11-10)=min(∞,41.8+52.3)=94.1
L’13-14:=min(L’13-14,L13-6+l6-14)=min(∞,86.1+144.7)=230.8
L’13-14:=min(L’13-14,L13-9+l9-14)=min(∞,70.7+111.1)=181.8
L’13-14:=min(L’13-14,L13-15+l15-14)=min(∞,60.0+27.5)=87.5
L’13-14:=min(L’13-14,L13-10+l10-14)=min(∞,94.1+48.1)=142.2
Шаг 1. L’13-14=
=min(96.6,96.8,104.6,120.4,138.7,127.2,121.8,176.3,133.7,135.6,94.1,230.8,181.8,87.5,142.2)=87.5=
=(L13-14,13)
Шаг 2. Дуга 15-14 переводится в дерево.
Шаг 3. Дерево составляют 8 дуг: 13-11, 11-12, 13-15, 12-9, 13-5, 12-7, 12-6 и 15-14.
Шаг 4. L’13-8:=min(L’13-8,L13-14+l14-8)=min(∞,87.5+184.3)=271.8
L’13-8:=min(L’13-8,L13-7+l7-8)=min(∞,80.7+15.9)=96.6
L’13-8:=min(L’13-8,L13-5+l5-8)=min(∞,77.6+19.2)=96.8
L’13-8:=min(L’13-8,L13-12+l12-8)=min(∞,55.4+49.2)=104.6
L’13-4:=min(L’13-4,L13-14+l14-4)=min(∞,87.5+179)=266.5
L’13-4:=min(L’13-4,L13-7+l7-4)=min(∞,80.7+39.7)=120.4
L’13-4:=min(L’13-4,L13-6+l6-4)=min(∞,86.1+52.6)=138.7
L’13-1:=min(L’13-1,L13-14+l14-1)=min(∞,87.5+179.4)=266.9
L’13-1:=min(L’13-1,L13-6+l6-1)=min(∞,86.1+41.1)=127.2
L’13-1:=min(L’13-1,L13-7+l7-1)=min(∞,80.7+41.1)=121.8
L’13-10:=min(L’13-10,L13-14+l14-10)=min(∞,87.5+48.1)=135.6
L’13-10:=min(L’13-10,L13-9+l9-10)=min(∞,70.7+63.0)=133.7
L’13-10:=min(L’13-10,L13-11+l11-10)=min(∞,41.8+52.3)=94.1
Шаг 1. L’13-10=
=min(96.6,96.8,104.6,266.5,120.4,138.7,266.9,127.2,121.8,135.6,133.7,94.1)=94.1=(L13-10,13)
Шаг 2. Дуга 11-10 переводится в дерево.
Шаг 3. Дерево составляют 9 дуг: 13-11, 11-12, 13-15, 12-9, 13-5, 12-7, 12-6, 15-14 и 11-10.
Шаг 4. L’13-8:=min(L’13-8,L13-10+l10-8)=min(∞,94.1+107.1)=201.2
L’13-8:=min(L’13-8,L13-7+l7-8)=min(∞,80.7+15.9)=96.6
L’13-8:=min(L’13-8,L13-5+l5-8)=min(∞,77.6+19.2)=96.8
L’13-8:=min(L’13-8,L13-12+l12-8)=min(∞,55.4+49.2)=104.6
L’13-4:=min(L’13-4,L13-10+l10-4)=min(∞,94.1+130.9)=225
L’13-4:=min(L’13-4,L13-7+l7-4)=min(∞,80.7+39.7)=120.4
L’13-4:=min(L’13-4,L13-6+l6-4)=min(∞,86.1+52.6)=138.7
L’13-1:=min(L’13-1,L13-10+l10-1)=min(∞,94.1+137.7)=231.8
L’13-1:=min(L’13-1,L13-6+l6-1)=min(∞,86.1+41.1)=127.2
L’13-1:=min(L’13-1,L13-7+l7-1)=min(∞,80.7+41.1)=121.8
Шаг 1. L’13-8=min(96.6,96.8,104.6,225,120.4,138.7,231.8,266.9,127.2,121.8)=96.6=(L13-8,13)
Шаг 2. Дуга 5-8 переводится в дерево.
Шаг 3. Дерево составляют 10 дуг: 13-11, 11-12, 13-15, 12-9, 13-5, 12-7, 12-6, 15-14, 11-10 и 5-8.
Шаг 4. L’13-2:=min(L’13-2,L13-8+l8-2)=min(∞,96.8+18.8)=115.6
L’13-2:=min(L’13-2,L13-4+l4-2)=min(∞,120.4+17)=137.4
L’13-2:=min(L’13-2,L13-7+l7-2)=min(∞,80.7+34.7)=115.4
L’13-4:=min(L’13-4,L13-8+l8-4)=min(∞,96.8+55.6)=152.4
L’13-4:=min(L’13-4,L13-7+l7-4)=min(∞,80.7+39.7)=120.4
L’13-4:=min(L’13-4,L13-6+l6-4)=min(∞,86.1+52.6)=138.7
L’13-1:=min(L’13-1,L13-8+l8-1)=min(∞,96.8+71.2)=168
L’13-1:=min(L’13-1,L13-6+l6-1)=min(∞,86.1+41.1)=127.2
L’13-1:=min(L’13-1,L13-7+l7-1)=min(∞,80.7+41.1)=121.8
Шаг 1. L’13-2=min(115.6,137.4,115.4,152.4,120.4,138.7,168,266.9,127.2,121.8)=115.4=(L13-2,13)
Шаг 2. Дуга 8-2 переводится в дерево.
Шаг 3. Дерево составляют 11 дуг: 13-11, 11-12, 13-15, 12-9, 13-5, 12-7, 12-6, 15-14, 11-10, 5-8 и 8-2.
Шаг 4. L’13-3:=min(L’13-3,L13-2+l2-3)=min(∞,115.6+7.5)=123.1
L’13-3:=min(L’13-3,L13-1+l1-3)=min(∞,127.2+21)=148.2
L’13-3:=min(L’13-3,L13-7+l7-3)=min(∞,80.7+49.2)=129.9
L’13-4:=min(L’13-4,L13-2+l2-4)=min(∞,115.6+17)=132.6
L’13-4:=min(L’13-4,L13-7+l7-4)=min(∞,80.7+39.7)=120.4
L’13-4:=min(L’13-4,L13-6+l6-4)=min(∞,86.1+52.6)=138.7
L’13-1:=min(L’13-1,L13-2+l2-1)=min(∞,115.6+28.5)=144.1
L’13-1:=min(L’13-1,L13-6+l6-1)=min(∞,86.1+41.1)=127.2
L’13-1:=min(L’13-1,L13-7+l7-1)=min(∞,80.7+41.1)=121.8
Шаг 1. L’13-4=min(123.1,148.2,129.9,132.6,120.4,138.7,144.1,127.2,121.8)=120.4=(L13-4,13)
Шаг 2. Дуга 7-4 переводится в дерево.
Шаг 3. Дерево составляют 12 дуг: 13-11, 11-12, 13-15, 12-9, 13-5, 12-7,12-6, 15-14, 11-10, 5-8, 8-2 и 7-4.
Шаг 4. L’13-3:=min(L’13-3,L13-4+l4-3)=min(∞,120.4+9.5)=129.9
L’13-3:=min(L’13-3,L13-1+l1-3)=min(∞,127.2+21)=148.2
L’13-3:=min(L’13-3,L13-2+l2-3)=min(∞,115.6+7.5)=123.1
L’13-1:=min(L’13-1,L13-4+l4-1)=min(∞,120.4+11.5)=131.9
L’13-1:=min(L’13-1,L13-2+l2-1)=min(∞,115.6+28.5)=144.1
L’13-1:=min(L’13-1,L13-6+l6-1)=min(∞,86.1+41.1)=127.2
Шаг 1. L’13-3=min(129.9,148.2,123.1,131.9,144.1,127.2)=123.1=(L13-3,13)
Шаг 2. Дуга 2-3 переводится в дерево.
Шаг 3. Дерево составляют 13 дуг: 13-11, 11-12, 13-15, 12-9, 13-5, 12-7, 12-6, 15-14, 11-10, 5-8, 8-2, 7-4 и 2-3.
Шаг 4. L’13-1:=min(L’13-1,L13-3+l3-1)=min(∞,123.1+17)=140.1
L’13-1:=min(L’13-1,L13-4+l4-1)=min(∞,120.4+11.5)=131.9
L’13-1:=min(L’13-1,L13-6+l6-1)=min(∞,86.1+41.1)=127.2
Шаг 1. L’13-1=min(140.1,131.9,127.2)=127.2=(L13-1,13)
Шаг 2. Дуга 6-1 переводится в дерево.
Шаг 3. Дерево составляют 14 дуг: 13-11, 11-12, 13-15, 12-9, 13-5, 12-7, 12-6, 15-14, 11-10, 5-8, 8-2, 7-4, 2-3 и 6-1.
2. Представление полученного ДКП в маршрутной структуре.
Выполняется заменой связей в дереве по дугам на связи по маршрутам из рис. 1 фрагмента сети МПП, наилучшим образом покрывающих дуговые связи дерева (минимальным количеством покрывающих маршрутов). Показано на рис. 3.
Рис. 3. Дерево в маршрутной структуре нагруженных потоками путей для узла 13.
3. Нагружение полученного по п.2 13-ro ДКП струями 13-й строки матрицы обменов - проставление возле каждого узла дерева двух характеристик его пометки - струи обмена (количества почты, исходящей из корня дерева и направленной в данный узел) и номера последнего узла перегружения почты с маршрута на маршрут в пути от корня дерева до данного узла - получателя . Также показано на рис. 3.
4. Расчеты узловых и маршрутных суммарных потоков.
а) расчет исходящего суммарного потока для корня дерева. Он образуется суммой первых цифр пометок всех адресных предприятий включая и собственную пометку. По ДКП (рис. 3) имеем исходящий поток для узла 13, т.е.
Q13=14+13+8+8+15+9+12+9+14+15+16+10+17+14+6=180
б) расчет для каждого из узлов дерева, где перегружается почта, суммы его транзита. Имеем по рис. 3 стыковки маршрутов в следующих узлах: 11, 12, 8. Транзитные составляющие потока по этим узлам вручную определяются непосредственно по рис. 3, и они равны
для узла 11: С11=15
для узла 12: С12=14+9+14=37
для узла 8: С8=13+8=21
в) расчет суммарного количества почты на каждом участке каждого задействованного маршрута. Производится суммированием потоков узлов, находящихся на данной ветви (рис. 3).
для маршрута 10:
для участка 13-11: S13-12=16+15+10+14+9+14+12+8=98
для участка 11-12: S11-12=10+14+9+14+12+8=67
для участка 12-7: S12-7=12+8=20
для участка 7-4: S7-4=8
для маршрута 16:
для участка 12-6: S12-6=9+14=23
для участка 6-1: S6-1=14
для маршрута 8:
для участка 12-9: S12-9=14
для маршрута 25:
для участка 11-10: S11-10=15
для маршрута 22:
для участка 13-5: S13-5=15+9+13+8=45
для участка 5-18: S5-8=9+13+8=30
для маршрута 6:
для участка 8-2: S8-2=13+8=21
для участка 2-3: S2-3=8
для маршрута 21:
для участка 13-15: S13-15=6+14=20
для участка 5-14: S5-14=14
IV. Литература
1. Князютенков В.А, Птицын Г.А.
Оптимизация сетей почтовой связи (учебное пособие) М.МТУСИ ,
1997 стр. 37- 68