() , - , - . -. , : , , , , , .
, , , . , , , . , .
. : = (, , I, ). З {p1, 2,..., n} , n³ 0. = (t 1, t 2,..., t m} , m ³ 0. , ∩ = Ø. I: T → ∞ .
: → ∞ .
i tj , piÎ I(tj); pi , iÎ O(tj). . , . , . pi tj , #(pi, I(tj)). pi tj , #(pi, (tj)). ( ), 0, 1.
. I , I: P T N0; O , O: T P N0, N0 .
|
|
. C = (P, T, I, O), P = {p1, p2, p3, p4, p5}, T = {t1, t2, t3, t4},
I (t1) = {p1}, O(t1) = {p2, p3, p5},
I (t2) = {p2, p3, p5}, O(t2) = {p5},
I(t3) = {p3}, O(t 3) = {p4},
I(t4) = {p4}, O(t 4) = {p2, p3},
. . . , | - .
() , , . , pi tj, , . . . .
G , G = (V, ), V= {v1, v2,..., vs} , = {a1, a2,..., ar} , i = (vj, vk), vj, vkÎ V. V , , V = U , I = Æ, aiÎ , ai= (vj, vk), vjÎ vkÎ T, vjÎ , vkÎ P.
. 1.1.
. (, , I, ) D- D+, . m ( ) n ( ). D- [j, i]= # (pi, I(tj)), a D+ [j, i] = #(pi, 0 (tj)). D - , D+ . (, , D-, D+) , .
. μ . ( ). ( , ) . . .
μ = (, , I, ) , N μ: → N. μ μ = (μ 1, μ2, , μ n), n = || μiÎ N, i = 1,..... n. μ pi . pi μi, i = 1,..., n.
. 1.2.
μ(pi) = μi.
= (, μ) = (, , I, ) μ = (, , I, , μ). , . . 1.2 .
|
|
. . , . , . , , , .
tjÎ (, , I, ) μ , piÎ μ(pi) ³ #(pi, I(tj)).
. . μ μ'. - , .
tj μ, , . tj μ', : μ'(pi) = μ(i) - #(pi, I(tj)) + #(i, O(tj)).
, . 6.3. : t1, t3 t4. t2 , 2, 3, t2, . t1,t3 t4, . t4, . 5, 3, 4 . , t4, . 1.4.
, . 1.4, t1 t3. t1 1 2, 3 4 ( p4 , t1). , . 1.5.
. 1.3. . t1, t3 t4 .
. 1.4. , t4 . 1.3.
. 1.5. , t1 . 1.4.
, . , .
. . . , n, , . . Nn. , , d, . μ () tj ( ), (), tj μ.
d: Nnx → Nn = (, , I, ) μ tjÎ , μ(pi) ³ #(pi, I(tj)) piÎ . d (μ, tj) , d (μ, tj) = μ, μ (pi) = μ(pi) - #(pi, I(tj)) + #(pi, O(tj)) iÎ P.
= (, , I, ) μ. . tj μ1 = d (μ, tj). , tk, μ2 = d (μ1, tk). , . , , , , .
|
|
: (μ, μ1, μ2,...) , (tj0, tj1, tj2,...). : d (μk, tjk) = μk+1 k = 0,1,2,.... μ, , , , . , .
= (, , I, ) μ μ' μ, tjÎ , , d (μ, tj) = μ'.
. μ' μ, μ" μ', , μ" μ. R(C, μ) μ , μ. μ' R(, μ), - , μ μ'.
R(C, μ) = (, , I, ) μ , :
1. μ Î R(, μ);
2. μ' Î R(, μ) μ" = d (μ', tj) tjÎ , μ" Î R (, μ).
. (tj1, tj2,..., tjk) μ μ = d (μ, tjl, tj2,..., tjk) : tjl, tj2 . . tjk. ( , , , .)
. , , , , . . , .
: . , . . . . , .
, . , . . , .
|
|
-. - , , . : ) - ; ) ; ) - ; ) . : 1. . 2. - . 3. - . 4. . 2 (- ) : () - ; () . 2: () - . :
, | ||
, | ||
. , . ; . . , . , , .
. 1.6 -.
. 1.6. -
, , , . . , . , ; , , , . , . 1.7.
. 1.7.
. , . , . . , , . , , . , , .
. . , , , , . , . , . , . 1.7 . , , .
( ) . , . , - , . , . . . , , , ; . .
|
|
. 1.8. " .
. ( ) , , . ; . , . , , . , . . : , . , . 1.8.
. . 1.9. , , , , . .
, , . 1.10. .
. 1.9. . . 1.10. . tj,tk
, . .
. pi
.
, .
.