. , .
: , :
L1 + L2 > 2 ri , j max. (16.2)
. , L1 xi xk, L2 xk xj.
1. R xk, xh, max.
2. k h i Î I = {1, 2,..., n}, i ¹ k, i ¹ h. n - 2. :
kih = r (k, i) + r (i, h) + r (k, h) (16.3)
3. max = klh. xk, xl, xh L1 (k h), L2 (k l), (l h). n 3 L1, L2.
4. i ¹ l, i ¹ k, i ¹ h
DR(k, h) = r (k, i) + r (I, h) r (k, h).
DR(k, l) = r (k, i) + r (I, l) r (k, l).
DR(l, h) = r (k, i) + r (I, h) r (l, h).
DR xi xi k l.
5. a b 4 a c c b. , 7.
6. xa, xb k h k a, a h k b a a b h.
7. .
, 6 , . :
1 | 2 | 3 | 4 | 5 | 6 | ||
1 | ¥ | 30 | 65 | 40 | 62 | 28 | |
30 | ¥ | 40 | 20 | 40 | 60 | ||
R = 3 | 65 | 40 | ¥ | 30 | 55 | 60 | . |
4 | 40 | 20 | 30 | ¥ | 30 | 32 | |
5 | 62 | 40 | 55 | 30 | ¥ | 36 | |
6 | 28 | 60 | 60 | 32 | 36 | ¥ |
1 , ( R).
ri , j max = max(r (i, j)) = r 1,3 = 65.
x 1, x 3 1 3 2, 4, 5 6.
2. (. 162.22) (16.3). r 1,3 , .
123 = 30 + 40 = 70,
143 = 40 + 30 = 70,
153= 62 + 55 = 117,
163 = 28 + 60 = 88.
3. 153 x 1, x 5, x 3. : L1 (x 1 x 3) L2 - (x 1 x 5 x 5 x 3) (. . 16.22).
. 16.22.
4. x 2, x 4, x 6 1 3, 1 5, 5 3. , ,
|
|
r (i, j) + r (j, k) > r (i, k), r (i, k) + r (k, j) > r (i, j), r (k, i) + r (i, j) > r (k, j),
:
DR(l, h) = r (l, i) + r (i, h) - r (l, h) (16.4)
x 2. , k = 1, h = 3, l = 5, i = 2. :
DR1,3 = r 1,2 + r 2,3 r 1,3 = 30 + 40 - 65 = 5,
DR1,5 = r 1,2 + r 2,5 r 1,5 = 30 + 40 - 28 = 42,
DR3,5 = r 3,2 + r 2,5 r 3,5 = 40 + 40 - 55 = 25.
DR1,3 = 5 , x 2 1 3.
x 4 x 6. , x 4: k = 1, h = 3, l = 5, i = 4.
DR1,3 = r 1,4 + r 4,3 r 1,3 = 40 + 30 - 65 = 5,
DR1,5 = r 1,4 + r 4,5 r 1,5 = 40 + 30 - 28 = 42,
DR3,5 = r 3,4 + r 4,5 r 3,5 = 30 + 30 - 55 = 5.
x 4 1 3, 3 5. 3 5, 1 3 x 2.
x 6: k = 1, h = 3, l = 5, i = 6.
DR1,3 = r 1,6 + r 6,3 r 1,3 = 28 + 60 ─ 65 = 23,
DR1,5 = r 1,6 + r 6,5 r 1,5 = 28 + 36 ─ 62 = 2,
DR3,5 = r 3,6 + r 6,5 r 3,5 = 60 + 36 ─ 55 = 41.
, x 6 1 5. .
5. 1 3 1 2 2 3. 3 5 3 4 4 5, 1 5 1 6 6 5.
, , 7. . 6.
, , , DR(k, h) .
6. k l, k h l h. , , k h xi xj. xj k i i h.
DR ki = r (k, j) + r (j, i) r (k, i), DR ih = r (i, j) + r (j, h) - r (i, h).
xj k i i h. . 5.
7. : x 1 x 2 x 3 x 4 x 5 x 6 x 1. 194.
. 16.23 , .
. 16.23.
, .
1. G, . 16.24. , ─.
. 16.24.
: :
.
1. x 1 xj, j = (2, 3, 4): d 12 = 3; d 13 = 1; d 14 = 4.
2. x 1 xj :
|
|
d 312 = d 13 + d 32 = 1 + 5 = 6; d 314 = d 13 + d 34 = 1 + 4 = 5; d 213 = d 12 + d 23 = 3 + 5 = 8;
d 214 = d 12 + d 24 = 3 + 6 = 9; d 412 = d 14 + d 42 = 2 + 6 = 8; d 413 = d 14 + d 43 = 2 + 4 = 6.
3. x 1 xj :
d 3,412 = d 314 + d 42 = d 13 + d 34 + d 42 = 1 + 4 + 6 = 11; d 2,413 = d 214 + d 43 = d 12 + d 24 + d 43 = 3 + 6 + 4 = 13; d 2,314 = d 213 + d 34 = d 12 + d 23 + d 34 = 3 + 5 + 4 = 12;
d 4,312 = d 413 + d 32 = d 14 + d 43 + d 32 = 2 + 4 + 5 = 11; d 4,213 = d 412 + d 23 = d 14 + d 42 + d 23
= 2 + 6 + 5 = 13; d 3,214 = d 312 + d 24 = d 13 + d 32 + d 24 = 1 + 5 + 6 = 12.
4. :
d 12 = d 3,412 ( d 4312) + d 21 = 11 + 3 = 14; d 13 = d 2413 ( d 4213) + d 31 = 13 + 1 = =14; d 14 = d 2314 ( d 3214) + d 41 = 12 + 2 = 14.
, , 14.
2. G = (X, U). .
: G = (X, U) , ,
1 | 2 | 3 | 4 | 5 | 6 | |||
R = | 1 | ¥ | 40 | 29 | 66 | 52 | 36 | . |
2 | ¥ | 41 | 63 | 37 | 50 | |||
3 | ¥ | 38 | 48 | 42 | ||||
4 | ¥ | 28 | 56 | |||||
5 | ¥ | 32 | ||||||
6 | ¥ |
1. R . r 14 = 66. x 1 x 4 .
2. x 1 x 3 (. 16.25,).
:
124 = 40 + 63 = 103;
134 = 29 + 38 = 67;
154 = 52 + 28 = 80;
164 = 36 + 56 = 92.
3. 124, . x 1, x 2, x 4. L1 = (x 1 x 4) L2 = (x 1 x 2 x 2 x 4) (. 16.25, ).
. 16.25. 1; 2
4. DR x 3, x 5, x 6.
) x 3:
DR12 = r 13 + r 32 - r 12 = 29 + 41 - 40 = 30;
D R 14 = r 13 + r 34 - r 14 = 29 + 38 - 66 = 1;
DR24 = r 23 + r 34 - r 24 = 41 + 38 - 63 = 16.
) x 5:
DR12 = r 15 + r 52 - r 12 = 52 + 37 - 40 = 49;
DR14 = r 15 + r 54 - r 14 = 52 + 28 - 66 = 24;
D R24 = r 25 + r 54 - r 24 = 37 + 28 - 63 = 2.
) x 6:
DR12 = r 16 + r 62 - r 12 = 36 + 50 - 40 = 46;
D R 14 = r 16 + r 64 - r 14 = 36 + 56 - 66 = 26;
DR24 = r 26 + r 64 - r 24 = 50 + 56 - 63 = 43.
5. , x 5 x 2 x 4, x 3 x 6 x 1 x 4. , x 2 x 4 x 2 x 5 x 5 x 4. DR14 x 3 (DR14 = 1) x 6 (DR14 = 26). (x 3), DR14, , x 6 x 1 x 6 x 6 x 4 (. 16.25, ). 6.
6. x 3 DR16 DR64, (. 16.25,).
x 3:
DR16 = r 13 + r 36 r 16 = 29 + 42 36 = 35;
D R 64 = r 63 + r 34 r 64 = 42 + 38 56 = 24.
x 3 x 4 x 6. .
. 16.25. 3; 4
7. (. 16.25, ).
|
|
:
r 12 + r 25 + r 54 + r 43 + r 36 + r 61 = 40 + 37 + 28 + 38 + 42 + 36 = 221.
. 16.25.
1. ?
2. ?
3. ?
4. ?
5. ?
6. ?
7. ? .
8. ?
9. ?
10. ?