: P, T, I O. ' . I tj I(tj), . O tj O(tj), .
, , .
1. C , C =(P, T, I, O). P ={ p1, p2,.., pn } , n > 0. T ={ t1, t2, , tm } , m > 0. , P∩T = 0. I: T → P∞ . O: T → P∞ .
n, m. pi, i =1,..., n, tj, j =1,..., .
. 1-3.
pi tj , pi I (tj); pi , pt (tj). . , . , . pt tj , # (pi, I (tj)). pt tj , #( 4, (tj)). ( ), 0, 1.
, . , tj i i tj. tj i pi tj.
2. I
I: Ұ, : Ұ ,
# (tj, I(pi)) = # (Pi, 0 (tj)), # (tj, (pt)) = # (pit I (tj)).
. 1 :
I(p1) = { }, O(p1) = {t1 },
I(p2) = {t1, t4 }, O(p2) = {t2 },
I(p3) = {t1, t4 }, O(p3) = {t2,t3},
I(p4) = {t3 }, O(p4)={t4},
I(p5) = {t1, t2 }, O(p5) = {t2).
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(t3) = {p4},
I(t4) = {p4}, O(t4) = {p2, p3}.
. 1. , (), (T), I: T P (O: T P)
|
|
=(, , I, ),
P = {p1, p2, p3, p4, p5, p6},
T={t1, t2, t3, t4, t5},
I(t1) = {p1}, O(t1) = {p2, p3},
I(t2) = {p3}, O(t2) = {p3, p5, p5},
I(t3) = {p2, p3}, O(t3) = {p2, p4},
I(t4) = {p4, p5, p5, p5}, O(t4) = {p4},
I(t5) = {p2}, O(t5) = {p6}.
. 2.
=(, , I, ),
P = {p1, p2, p3, p4, p5, p6, p7, p8, p9},
T={t1, t2, t3, t4, t5, t6},
I(t1) = {p1}, O(t1) = {p2, p3},
I(t2) = {p8}, O(t2) = {p1, p7},
I(t3) = {p2, p5}, O(t3) = {p6},
I(t4) = {p3}, O(t4) = {p4},
I(t5) = {p6, p7}, O(t5) = {p9},
I(t6) = {p4, p9}, O(t6) = {p5, p8}.
. 3.
.
1. (. 2 3).
2., , ( ) . , .
, . , . - .
. ³ 䳺 . , | .
() ' , , . , pi tj, , . . . .
, . , , . , ( ) , ( ) ( ); , . .
3. G , G = (V, ), V= {1, u2, , us} , = {1, 2,..., r} , i = (vj, vk), vj, vk V. V , , V = U , = , - at , at = (vj, vk), vj vk T, vj , a vk .
, . 4 - 6, . 1 - 3.
, . , = (, , I, ) = = {p1, p2, , pn} = {t1, t2,..., tm). .
|
|
4. V = P T. , , pi P tj
# ((pi, tj), A) = # (i, I (tj)),
#((tj, pi), A) = #(pi, 0(tj)).
G = (V, ) , = (, , I, ).
( ) . : S R, , ? , , , .
. 4. , , . 1
5. , , . 2
. 6. , , . 3
. 7. , , . 4
= (, , I, ) = (, , I, ), . , (. 6). . 7 , . 4. . . , . .
1. , , . 5 6.
2. :
P = {p1, p2, p3, p4},
T={t1, t2, t3, t4, t5},
I(t1) = { }, O(t1) = {p1},
I(t2) = {p1}, O(t2) = {p2},
I(t3) = {p2, p4}, O(t3) = {p1, p3},
I(t4) = { }, O(t4) = {p3},
I(t5) = {p3}, O(t5) = {p4}.
3. :
P = {p1, p2},
T={t1, t2, t3},
I(t1) = {p1 }, O(t1) = {p1, p2},
I(t2) = {p1}, O(t2) = {p2},
I(t3) = {p2}, O(t3) = { }.
4. , .
5. , . ?
6. , = (, , I, ), = (, , I, ), P, . ? = (, , 1, ) , = (T, , I', 0') .
7. , . 8. . 9.
8. , . . ( ), . , . , .
. 10 7 11. :
P = {p1, p2, p3, p4},
T={t1, t2, t3, t4},
I(t1) = { }, O(t1) = {p1, p1, p1, p1, p2},
I(t2) = {p2}, O(t2) = {p1, p1, p1, p1, p1, p1, p3},
I(t3) = {p1, p1, p1, p1, p1, p1}, O(t3) = {p2, p2, p2, p2, p4, p4},
|
|
I(t4) = { p3, p4, p4, p2}, O(t4) = { }.
. 8. . 9.
. 10. . , ,
9. = (, T, I, 0) = (, , , I). ? ? ? , . 7.
. Գ - ( ). Գ ( , ) . ʳ . Գ .
5. = (, , I, ) , N.
: N.
n- = = ( 1, 2,...., n). = N, i = 1,..., .
. 11. . . 1 4. - (1, 2, 0, 0, 1)
. 12. . , . 11,
pi . ʳ i i, i = 1,..., n. ' (pi)= i. .
= (, ) = (, , I, ) = (, , I, , ).
, . . 11 12 .
, , , . , 䳺 n , n-, Nn. , , .
. 13. (47, 13, 7, 42)
1. (. 12) .
2. (. 2) = (1, 0, 1, 1, 0, 0).
3.ʳ 5 6. . , 10, 20 , , , , . 2.13. , = (137, 22, 2, 0, 14) . 12.
. Գ . . , .
|
|
, . , . . Գ , , ' . , p1 2 t4, t4 , p1 2 . t7 {6, 6, 6} 6 , t7 .
6. tj = {, , I, ) , , pi P
(pi) #(pi, I(tj)).
' . . t3 I(t3) = {2} O(t3) = {7, 13} , 2 . t3 2 7 p13 ( ). 2 t3 ( t3). t2, I(t2) = {p21, 23 } O(t2) = {23, 25, 25}, p21 23, 23 25 ( 25 , ).
'. , , . , . - , .
7. tj , . tj ', : '(pi) = (pi) - #(pi, I(tj)) + #(pi, O(tj)).
. 14. , , tj. . 0 1.
, . , .
1. . 11, 12?
2. t1 (. 11)? t4 (. 12)? : t4, t2 (. 12)?
3. . 13? ?