ВУЗ:
Составители:
53
В задаче требуется найти значения всех величин A, B, C, D, E, F, G,
H, J, K, L, P, Q, R и S.
Для её решения вначале обозначим через E
j
число, показывающее,
сколько раз в процессе выполнения алгоритма проходится стрелка e
j
. То-
гда, согласно закону Кирхгофа:
(сумма величин Е, входящих в блок) =
= (величина, находящаяся в блоке) = (40)
= (сумма величин Е, выходящих из блока).
Например, для блока K имеем:
E
19
+ E
20
= K = E
18
+ E
21
.
(41)
Далее кроме величин А, В, …, S будем считать неизвестными и величины
Е
1
, Е
2
, …, Е
27.
Затем абстрагируем блок-схему так, что она примет вид ориентиро-
ванного графа, изображённого на рис. 26. При этом дуга e
13
разделена на
дуги
13
e
′
и
13
e
′
′
для того, чтобы контур состоял не менее чем из трёх дуг.
Таким же образом разделена дуга e
19
. Аналогично нужно было бы посту-
пить и с петлями, если бы они имели место в графе. Для того чтобы закон
Кирхгофа был одинаково применим ко всем частям данного графа, вве-
дена дуга e
0
, направленная из блока «Конец» в блок «Начало».
Рис. 26. Абстрактная блок-схема алгоритма
На этом рисунке более жирными линиями выделен остов графа. До-
бавив к остову любую хорду (дугу графа, не вошедшую в остов), полу-
e
1
e
2
e
3
e
4
e
5
e
6
e
7
e
8
e
9
e
10
e
11
e
12
e
14
e
15
e
16
e
17
e
18
19
e
′
′
e
20
e
21
e
22
e
23
e
24
e
25
e
26
e
27
13
e
′
′
13
e
′
19
e
′
e
0
Страницы
- « первая
- ‹ предыдущая
- …
- 51
- 52
- 53
- 54
- 55
- …
- следующая ›
- последняя »
