1. .
2. .
3. .
4. .
5. .
6. .
7. .
8. .
9. .
10. .
. .
. . d (xi, xj), xi, xj Î X G = (X, U) , . . d (xi, xj), G, .
G D = || di , j || n × n . :
di , j = . (16.5)
, G (. 16.26)
. 16.26. G
1 | 2 | 3 | 4 | 5 | |||
D= | 1 | 0 | 1 | 1 | 2 | 1 | . |
2 | 1 | 0 | 2 | 1 | 1 | ||
3 | 1 | 2 | 0 | 1 | 1 | ||
4 | 2 | 1 | 1 | 0 | 1 | ||
5 | 1 | 1 | 1 | 1 | 0 |
, :
LD = {<1, 2, 1>, <1, 3, 1>, <1, 4, 2>, <1, 5, 1>, <2, 3, 2>, <2, 4, 1>, <2, 5, 1>, <3, 4, 1>, <3, 5, 1>, <4, 5, 1>}.
xi , xj, di , j.
, d (G) :
d (G) = max di , j , i, j Î I = {1, 2,..., n}. (16.6)
, i, j Î X , .
v G = (X, U). G v :
r (v) = max dv,x, v, x Î X. (16.7)
. v G max dv , x, v, x Î X x.
r (G) . v x .
|
|
R(G) = min r (x), x Î X. (16.8)
v , , .
. , Kn, 1 .
G G = (X, U), |U| = m. m!. , . g (v , v ) v , v Î X , .
, v Î X, g (v, v) = 0. .
L(v , v ) , v v . L*(v , v ) , v v . (v , v 4) L.
v4 2 L, L. L v v , L , v v , L. g (v , v ) + g (v , v ) L, g (v , v ) ( 16.27).
G . l 0 . v . g (v) = max g (v, v ), v Î v v.
. 16.27.
G r , . G r = (X r, U r) X r (), U r , . G r, .. , . 16.28. G r, , .
. 16.28. G r
di , j G r
di , j = | si sj | + | ti tj |, (16.9)
si, sj ti, tj xi, xj Î X. p × q, p s, q t.
, G r (. 16.28)
d 6,10 = | s 6 s 10| + | t 6 t 10| = |0 2| + |1 3| = 4,
.. x 6 G r, x 10.
G G r , G , G . di , j , xi, xj,
di , j = (16.10)
, di , j , di , j . G G r. L(G) G = (X, U), G r, D(g).
|
|
D(g) D, di , j, xi, xj Î X G. D(g) G D R: D(g) = || ri , j, di , j || n × n.
, G G r 3×2 (. 16.29).
16.29. ,
R D G :
1 | 2 | 3 | 4 | 5 | 6 | 1 | 2 | 3 | 4 | 5 | 6 | |||
1 | 0 | 1 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 2 | 3 | 2 | 1 | |
2 | 1 | 0 | 0 | 1 | 1 | 0 | 2 | 1 | 0 | 1 | 2 | 1 | 2 | |
R = 3 | 1 | 0 | 0 | 1 | 0 | 0 | , D = 3 | 2 | 1 | 0 | 1 | 2 | 3 | . |
4 | 0 | 1 | 1 | 0 | 1 | 1 | 4 | 3 | 2 | 1 | 0 | 1 | 2 | |
5 | 1 | 1 | 0 | 1 | 0 | 1 | 5 | 2 | 1 | 2 | 1 | 0 | 1 | |
6 | 0 | 0 | 0 | 1 | 1 | 0 | 6 | 1 | 2 | 3 | 2 | 1 | 0 |
D(g) = R × D:
1 | 2 | 3 | 4 | 5 | 6 | r (xi) | ||
1 | 0 | 1 | 2 | 0 | 2 | 0 | 5 | . |
2 | 1 | 0 | 0 | 2 | 1 | 0 | 4 | |
D(g) = 3 | 2 | 0 | 0 | 1 | 0 | 0 | 3 | |
4 | 0 | 2 | 1 | 0 | 1 | 2 | 6 | |
5 | 2 | 1 | 0 | 1 | 0 | 1 | 5 | |
6 | 0 | 0 | 0 | 2 | 1 | 0 | 3 |
D(g) G G r. L(G) 13 . L(G) , .
1. G = (X, U), . 16.30, .
. 16.30. G
: .
:
.
, . . :
D = {<1,2,1>;<1,3,1>;<1,4,2>;<2,3,2>;<2,4,1>;<3,4,1>}.
2. G = (X,U), . 16.31, . L(G), .
. 16.31. G
: G G r, . 16.32.
. 16.32. G
G r . , D :
.
Dg. 24. , L(G) G r 12.
1. ?
2. ?
3. ?
4. ?
5. ?
6. ?
7. ?
8. ?
9. ?
10. ?