Методы программирования. Громов Ю.Ю - 54 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

54
чим точно один цикл. Например, добавив дугу e
2
к заданному остову,
получаем цикл (e
2
, e
4
, e
3
), который алгебраически можно записать в виде
«e
2
– e
3
– e
4
», где знаки плюс и минус показывают, идёт ли цикл по на-
правлению соответствующей дуги или против него.
Выполнив такую процедуру для каждой хорды относительно задан-
ного остова, получим все базисные циклы:
C
0
: e
0
+ e
1
+ e
3
+ e
4
+ e
6
+ e
7
+ e
9
+ e
10
+ e
11
+ e
12
+ e
14
;
C
2
: e
2
– e
3
– e
4
;
C
5
: e
5
– e
7
– e
6
;
C
8
: e
8
+ e
3
+ e
4
+ e
6
+ e
7
;
13
С
′
′
:
13
e
′
′
+ e
12
+
13
e
′
;
(42)
C
17
: e
17
+ e
22
+ e
24
+ e
27
+ e
11
+ e
15
+ e
16
;
19
С
′
′
:
19
e
′
′
+ e
18
+
19
e
′
;
C
20
: e
20
+ e
18
+ e
22
+ e
23
;
C
21
: e
21
– e
16
– e
15
– e
11
– e
27
– e
24
– e
22
– e
18
;
C
25
: e
25
+ e
26
– e
27
.
Величины E
0
, E
2
, E
5
, E
8
,
13
Е
′
′
, E
17
,
19
Е
′
′
, E
20
, E
21
и E
25
, соответствую-
щие представленным циклам, следует считать независимыми неизвест-
ными величинами, поскольку для любого набора значений этих величин
имеется решение уравнений Кирхгофа вида (40), причём единственное:
E
1
= E
0
, E
11
= E
0
+ E
17
– E
21
,
19
Е
′
=
19
Е
′
′
,
E
3
= E
0
– E
2
+ E
8
,
E
12
= E
0
+
13
Е
′
′
,
E
22
= E
17
+ E
20
– E
21
,
E
4
= E
0
– E
2
+ E
8
,
13
Е
′
=
13
Е
′
′
,
E
23
= E
20
,
E
6
= E
0
– E
5
+ E
8
, E
14
= E
0
, E
24
= E
17
– E
21
, (43)
E
7
= E
0
– E
5
+ E
8
, E
15
= E
17
– E
21
, E
26
= E
25
,
E
9
= E
0
, E
16
= E
17
– E
21
, E
27
= E
17
– E
21
– E
25
.
E
10
= E
0
,
E
18
=
19
Е
′
′
+ E
20
,
Отметим, что при получении соотношений (43) для каждой дуги e
j
заданного остова записываем все взятые с соответствующим знаком ве-
личины E
k
,
для которых дуга e
j
входит в цикл C
k
. Таким образом, матрица
коэффициентов системы (43) является просто транспонированной по от-
ношению к матрице коэффициентов системы (42).
Задав значения независимых неизвестных величин E
0
, E
2
, E
5
, E
8
,
13
Е
′
′
, E
17
,
19
Е
′
′
, E
20
, E
21
и E
25
, можно вычислить по соотношениям (43)
величины E
1
, E
3
, E
4
, E
6
, E
7
, E
9
, E
10
, E
11
, E
12
,
13
Е
′
, E
14
, E
15
, E
16
, E
18
,
19
Е
′
,
E
22
, E
23
, E
24
, E
26
и E
27
. Отметим, что блоки «Начало» и «Конец» алгорит-

Страницы