, 2.1. (. 2.1).
2.1
, | |||
A | |||
B | |||
C | |||
D | C | ||
E | C | ||
F | A | ||
G | A | ||
H | B, F | ||
I | E, H | ||
K | D, E, H, G |
. 2.1
, . 1. ³ 䳿 2, 3, 4. A F G, 䳿 2. B F H, 䳿 3. E D A C. 䳿 2. A' 䳿 2 䳿 4. .
F , B, H, 3. 5 E H, 6 D G. I 䳿 5, K 䳿 6. K E H, 䳿 5 䳿 6 .
K I . , 䳺, 7.
. 2.1.
. , 䳿. i = 1 tp (i) = 0. i = 2 tp (2) = 3, , 䳿 2. tp (3) ອ (1.5) t (2; 3) = 9 t (1; 3) = 8:
tp (3) = max{ tp (l) + t (1; 3); tp (2) + t (2;4)} = max{0 + 8; 3 + 9} = 12.
, t (3) = 12.
tp (4), tp (5), tp (6), tp (7):
tp (4) = max{ tp (1) + t (1; 4); tp (2) + t (2; 4)} = max{0 + 4; 3 + 0} = 4.
tp (5) = max{ tp (3)+ t (3; 5); tp (4) + t (4;5)}= max{4 + 6; 12 + 7} = 19.
tp (6) = max{ tp (2) + t (2; 6); tp (5) + t (5; 6); tp (3) + t (3; 6)} = max{3 + 5; 19 + 0; 4 + 10} = 19.
tp (7) = max{ tp (5) + t (5;7); tp (6) + t (6; 7)} = max{19 + 8; 19 + 6} = 27.
, 27 .
(. 2.2).
t (i) . 䳿 , tn (7) = 37. ϳ , (1.7):
|
|
tn (6) = tn (7) t (6;7) = 27 6 = 21, 䳿 6 (6; 7).
tn (5) = min{ tn (7) t (5; 7); tn (6) t (5; 6)} = min{27 8; 21 0} = 19.
tn (4) = min{ tn (5) t (4; 5); tn (6) t (4; 6)} = mn{19 6; 21 10} = 11.
tn (3) = tn (5) t (3; 5) = 19 7 = 12, 䳿 3 , (4; 5).
tn (2) = mn{ tn (3) t (2; 3); tn (6) t (2;6)} = mn{12 9; 21 5} = 3.
tn (1) = 0.
. (1.8) 䳿:
R (1) = 0 0 = 0; R (3) = 12 12 = 0; R (6) = 21 19 = 2;
R (2)=3 3 = 0; R (4) = 11 4 = 7; R (7) = 27 27 = 0.
R (5) = 19 19 = 0;
, 䳿, . AFHI. . 2.2 .
. 2.2
. , 䳿 䳿 , .
2.2
(i, j) | tij | ϳ | |||||
. tpn (i, j) | . tp (i, j) | . tn (i, j) | . tn (i, j) | Rn (i, j) | R 2(i, j) | ||
A (1, 2) | |||||||
B (1, 3) | |||||||
C (1, 4) | |||||||
F (2, 3) | |||||||
A' (2, 4) | |||||||
G (2, 6) | |||||||
H (3, 5) | |||||||
D (4, 5) | |||||||
E (4, 6) | |||||||
H' (5, 6) | |||||||
I (5, 7) | |||||||
K (6, 7) |
ϳ , (1.10) (1.12).
(1.14). ³ (1.17). 2.2. , .
2.3.
2.3
Rn, (1.14) | R 1, (1.15) | R 2, (1.17) | R, (1.19) | ||
(1; 2) | 3 0 3 = 0 | 3 0 3 = 0 | 3 0 3 = 0 | 3 0 3 = 0 | |
(1; 3) | 12 0 8 = 4 | 12 0 8 = 4 | 12 0 8 = 4 | 12 0 8 = 4 | |
(1; 4) | 11 0 4 = 7 | 11 0 4 = 7 | 4 0 4 = 0 | 4 0 4 = 0 | |
(2; 3) | 12 3 9 = 0 | 12 3 9 = 0 | 12 3 9 = 0 | 12 3 9 = 0 | |
(2; 4) | 11 3 0 = 8 | 11 3 0 = 8 | 4 3 0 = 1 | 4 3 0 = 1 | |
(2; 6) | 21 3 5 = 13 | 21 3 5 = 13 | 19 3 5 = 11 | 19 3 5 = 11 | |
(3; 5) | 19 12 7 = 0 | 19 12 7 = 0 | 19 12 7 = 0 | 19 12 7 = 0 | |
(4; 5) | 19 4 6 = 9 | 19 11 6 = 2 | 19 4 6 = 9 | 19 11 6 = 2 | |
(4; 6) | 21 10 = 7 | 21 11 10 = 0 | 19 4 10 = 5 | 19 11 10 = 2 | |
(5; 6) | 21 19 0 = 2 | 21 19 0 = 2 | 19 19 0 = 0 | 19 19 0 = 0 | |
(5; 7) | 27 19 8 = 0 | 27 19 8 = 0 | 27 19 8 = 0 | 27 19 8 = 0 | |
(6; 7) | 27 19 6 = 2 | 27 21 6 = 0 | 27 19 6 = 2 | 27 21 6 = 0 |
. . () . .
|
|
. :
;
() ;
.
. , . . 2.3. Գ .
. 2.3
(. 2.1).
, - . . , . ³ , .
. A, B, C. 4 + 1 + 3 = 8 . A . 4 . F () G, 4 7 . , 8 4 + 4 + 7 = 15 .
t = 4 , . E D. 15 3 + 4 + 2 = 18 . t = 7, B G. 18 1 7 = 10. , (. 2.4). , , , .
.
(. 2.5).
. 2.4
, , t = 0 A (). 4 . t = 3 F. , . F 4- , . t = 4 B, , . t = 7 C, 8 . , .
|
|
, 18 , 16 . .
. 2.5 ϳ
. G t = 14, t = 3 t = 8 7 , t = 14 t = 19 7 . 11 . (. 2.6).
E t = 8, 10 . (. 2.7).
. .
. 2.6
. 2.7
ί
3.1.
.
. , , , . ; ; ; .
.
( . 207.01:2004).
ϳ , .