(s / t -) ` , s () t (). :
s , t ;
` , cij.
s / t - . - s / t -, , s / t -, . s / t - ` jij ( uij)=v, :
jij £ cij, - ;
, - , , , , , , .
s / t -. ` 1 2 , :
s / t - , 1 2, ( 1, 2). , , v(X1, X2).
. -: .
4. . s/t-.
`. cij, jij. s/t- , jij=0. - - (+, e()) (-, e()), - , , + - , - - , e() ` , ( ) ( ). s (s+, ¥). , (cij-jij >0), (jij >0). (+, e()) e()=min(e(i), cik-jik), (-, e()) e()=min(e(i), jik). - , t, , , t ( ).
1- .
1- . S(s+,¥). s. 1(s+, min(¥,10-0), 1(s+,10). 2(s+,15), 3(s+,15). s . - . , 3. , : 2(3+, min(15, 10-0)=10), t(3+, min(15,8-0)=8) t 1- .
|
|
2- . , s t: t3s. e(t), . . , .
2- .
S(s+,¥) | 1(s+,10) 2(s+,15) 3(s+,7) | t(2+,15) t2s e(t)=15 |
3- .
S(s+,¥) | 1(s+,10) 3(s+,7) | 4(1+,7) t(1+,7) t1s e(t)=7 |
ϳ 2- 3- .
4- .
S(s+,¥) | 1(s+,3) 3(s+,7) | 2(3+,7) | t(2+,5) t23s e(t)=5 |
5- .
S(s+,¥) | 1(s+,3) 3(s+,2) | 4(1+,3) | t(4+,3) t41s e(t)=3 |
6- .
S(s+,¥) | 3(s+,2) | 2(3+,2) | S(2-,2) |
1- 6- s, t . , . : 1 , 6- , 2 , . 1={s, 2, 3}, X2={1, 4, t}, (X1, X2)={us1, u2t, u3t}, v(X1, X2)=cs1+c2t+c3t=10+20+8=38. : e(t): 8+15+7+5+3=38, .
, .
3.
1
G. . ( , 2, - , - , ). .
2
G=(X,U) . :
1) ;
2) ;
3) , - .
1. 2.
3. 4.
5. 6.
7. 8.
9. 10.
11. 12.
13. 14.
15. 16.
17. 18.
19. 20.
21. 22.
23. 24.
25. 26.
27. 28.
29. 30.
3
n . n . ³ ( ). , .
1. 2.
3. 4.
5. 6.
7. 8.
9. 10.
11. 12.
13. 14.
15. 16.
17. 18.
19. 20.
21. 22.
23. 24.
25. 26.
27. 28.
29. 30.
4
, . , -, (s - , t - ).
|
|
1. us1=13, us2=17, us3=1, u1t=7, u13=5, u23=2, u24=17, u34=1, u3t=2, u4t=12
2. us1=16, us2=14, u13=9, u21=10, u23=5, u24=8, u35=6, u3t=9, u45=1, u4t=6, u5t=6.
3. us1=6, us2=10, us3=3, u12=3, u14=2, u13=2, u24=1, u2t=8, u32=4, u34=5, u4t=9
4. us1=3, us2=5, us3=4, us4=1, u1t=7, u21=2, u24=1, u2t=1, u32=3, u34=2, u4t=3
5. us1=25, us2=18, u12=4, u14=10, u24=10, u2t=15, u3t=5, u43=10, u4t=10
6. us1=5, us2=4, us3=6, u1t=4, u14=1, u13=1, u23=3, u24=2, u34=2, u3t=3, u4t=7
7. us1=12, us2=20, us3=5, u1t=10, u13=8, u23=5, u24=10, u34=4, u3t=8, u4t=12
8. us1=8, us3=4, us4=6, u12=4, u24=2, u2t=10, u31=3, u32=2, u34=5, u4t=7
9. us1=10, us2=10, us3=15, u14=7, u12=4, u24=6, u32=5, u3t=20, u4t=10
10. us1=6, us2=7, us3=5, u12=3, u14=2, u13=1, u23=4, u24=2, u2t=3, u3t=7, u4t=8
11. us1=5, us2=6, us3=8, u12=2, u14=3, u13=1, u24=1, u2t=4, u3t=5, u4t=6
12. us1=10, us2=3, us3=15, u1t=5, u12=8, u23=16, u24=4, u2t=15, u34=5, u4t=20
13. us1=7, us4=15, ust=5, u1t=3, u13=5, u21=10, u34=3, u42=20, u4t=6
14. us1=20, us4=5, u12=17, u13=6, u24=10, u2t=3, u32=10, u3t=5, u4t=20
15. us1=25, us3=40, u14=20, u13=15, u2t=40, u32=20, u3t=15, u4t=7
16. us1=6, us2=14, u1t=10, u14=3, u23=3, u21=10, u24=2, u34=5, u4t=8
17. us1=5, us2=18, us5=7, u14=15, u23=25, u35=10, u3t=4, u43=10, u4t=10, u5t=2
18. us1=20, us2=10, us3=15, u12=15, u23=20, u25=15,u34=4,u35=8, u3t=1,u4t=20,u5t=4
19. us1=10, us2=5, us4=10, u12=1, u13=5, u14=8, u34=4, u3t=4, u42=5, u2t=20
20. us1=15, us2=20, us3=5, u1t=15, u12=8, u23=16, u24=4, u2t=10, u34=5, u4t=3
21. us1=10, us3=15, u14=8, u1t=13, u24=15, u31=6, u32=3, u3t=5, u4t=12
22. us3=10, us4=15, u1t=13, u2t=20, u31=8, u34=5, u41=2, u42=8, u4t=12
23. us1=15, us2=12, us3=11, u1t=9, u14=7, u13=6, u23=7, u21=10, u34=8, u3t=8, u4t=17
24. us1=13, us2=17, us3=1, u1t=7, u13=5, u23=2, u24=17, u34=1, u3t=2, u4t=12
25. us1=9, us2=7, us3=10, us4=12, u13=6, u14=8, u23=6, u24=6, u3t=14, u43=8, u4t=10
26. us1=8, us2=7, us4=16, u1t=7, u12=5, u23=10, u3t=12, u43=6, u45=10, u53=7, u5t=9
27. us1=11, us2=19, u1t=15, u14=8, u23=8, u21=15, u24=7, u34=10, u4t=13, u2t=2
28. us1=10, us2=3, us3=15, u1t=5, u12=8, u23=16, u24=4, u2t=15, u34=5, u4t=20
29. us1=5, us2=18, us5=7, u14=15, u23=25, u35=10, u3t=4, u43=10, u4t=10, u5t=2
30. us1=25, us2=18, u12=4, u14=10, u24=10, u2t=15, u3t=5, u43=10, u4t=10
31. us1=6, us2=10, us3=3, u12=3, u14=2, u13=2, u24=1, u2t=8, u32=4, u34=5, u4t=9
˲
1. .., . ., .. . . , 2002. 288 .
2. .., .., .. . : ̲, 2004. 480 .
3. .., . ., .., .., . . : ϳ. .: ˳, 2000. .2 380 .
4. .. . . , 2004. 302 .
5. .., .. .-: , 2003.-272 .
6. .. . . 2003, 960 .
6.040302 ( )
..., ..,.
. ..
³ : . . ..
ϳ. . _________. 6084 1/16. . .
. . . ____. _______ . . _______. .
39614,., . , 20