Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.intsys.msu.ru/magazine/archive/v8(1-4)/shayeb-335-348.pdf Дата изменения: Thu Feb 24 00:18:32 2005 Дата индексирования: Mon Oct 1 23:40:28 2012 Кодировка: IBM-866 Поисковые слова: m 2

. H [6], . A. , A- . , , .


, , . . : , , н. .


336



XX , , , , . . , , , ( ) ( ). , , . . , , , . . , , . . . з1 . з2 H . з3 A, , , , . , .

1.
, :




337

п п E = {0, 1}; D = {-1, 1}; D = [-1, 1]; E n , Dn , Dn -- n; n- R ~~ п (, ) -- , |x| п x п (x, =
n i=1

п xi , x

=

(x1 ,... ,xn ) Rn ; п -- x Rn ; п пп y ) -- x y Rn .

|M | -- M . . , , , ~ ~ E n , E n , M, M1 ,M2 E n . ~~ d(M ) = max (, )
~~ , M

M . min (M1 ,M2 ) =

~ ~ M1 , M

~~ (, )
2

M1 M2 . ~~ , E n . ~~ ~~ (, ) = n - (, ). ~~ ~~ , (, ) , , . ~~ ~ (, i ) (, M ) =
~ i M

~ M . ~ (, M ) ~ (, M ) = |M | ~ M .


338



~ (, M ) =
~ i M

~~ (, i )

~ M . ~ (, M ) ~ P (, M ) = |M | ~ M . ~ , E n M E n ~ ~ (, M ) = n -P (, M ).

2.
- [1], [2].

2.1.
K1 K2 -- (x1 ,... ,xn ), xi E , i = 1,... ,n. i xi . ~ (1) ~ (1) ~ (2) ~ (2) L1 = {1 ,... m1 } K1 , L2 = {1 ,... m2 } K2 . L1 L2 . , L1 L2 , ~ , , K1 K2 ~ K1 , K2 , ~ K1 ; ~ K2 .

. ~ ~ ~ ~ K1 , K1 K2 , K2 , , .




339

2.2. H -
H , : ~ ~ (, L1 ) > (, L2 ) K1 , ~ ~ ~ () (, L1 ) < (, L2 ) K2 , , (, L ) = (, L ) ~2 ~1 , , P P P ~ ~ (, L1 ) < P (, L2 ); ~ ~ (, L1 ) > P (, L2 ); ~ ~ L1 ) = P (, L2 ). (,

K1 K2 H - ( L1 L2 ), L1 K1 L2 K2 H L1 L2 L1 L2 . K1 K2 H -, L1 K1 , L2 K2 K1 K2 H - ( L1 L2 ). . 1 ([6]). M1 ,M2 E n , |Mi | = mi , a) M1 M2 H -, mi d(Mi ) < , (M1 ,M2 ) mi - 1 ) M1 M2 H -, d(Mi ) < 1, (M1 ,M2 ) i = 1, 2. i = 1, 2;

2.3.
~ ~ ~~ E n G (, x+ )= 0, , Rn . ~ E n , ~~ ~ ~~ , (, + ) > 0; , (, +


340



~ ~~ ~ ) < 0. , (, + ) = 0, , ~ . , M1 ,M2 E n , G, M1 M2 G, . . , , ~ (, x) = 0. . 2 ([6]). M1 ,M2 E n (*), M1 M2 .

2.4.
n- E n n- Dn = {-1, 1}n . M1 ,M2 Dn M = M1 (-M2 ). (-1,1)-, M . , . ~~ ~ ~~ ~ ~~ п M1 = {1 , 2 ,... , m1 }, M2 = { 1 , 2 ,... , m2 }; i , j Dn . 1 ~ p(M ) = i |M |
~ i M

M . p(M1 ) - p(M2 ) q (M1 ,M2 ) = 2 M1 M2 . , M1 M2 H -, G ~ ~ ~ ~ (q, x) = 0, M1 M2 (q, ) > 0 (q, ) < 0.




341

~ , ~ M (q, ) > 0. , , qi q , i = 1, 2,... ,n. , |M1 | = |M2 | ( q ~ i ). d =
~ i M

B = min

~ M

~ (, d)

( , ). , ~ ~~ M = {1 , 2 ,... , m } M ~ ~~ { 1 , 2 ,... , m }, . , M M . . M B > 0 c R, 0 c B , ( ) , M ( M ) , c. . 3 ([7], [8]). NP- [10].

M . = {1, 2,... ,n} -- . = {i1 ,i2 ,... ,ik } ( ~ ~ ~ ) , = {1 ,... , n } Dn k , i ,... ,i ~ D 1 k ~ . ~ ~ , -


342



3. A
A. , , , . A.

3.1.
M1 M2 (|M1 | = |M2 | = m) (-1, 1)- m Ѕ n, M = M1 (-M2 ) 2m Ѕ n п(M ) = (q1 ,... ,qn ) ( q M1 M2 ). qi = 0 M ( Masst (n)) i, Mzap (n). i qi < 0, i Mzap (n), M i [7]. п(M ), q . п(M ) . q M , п(M ) . q

3.2. () A-
M п(M ) q q SV (I ) = min (п(M ),ai ),
1im

S N (J ) =

m+1 j 2m

min

(п(M ),aj ), q




343

ai ,aj -- M , I, J -- M , . min(SV (I ),S N (J )) > 0, M1 M2 A-; M I J ( ), , A-. M , M . , [4].

3.3. () A-
() Mraz (n) m2 Ѕ n ( M = {a - b|a M1 , b M2 }. M T Mraz 3.2 Mimssv (I ), Mimssv (J ). min(Mimssv (I ),Mimssv (J )) > 0, M1 M2 A- [7]. M I J (, ) , A- ( M MAS K A ).

3.4. I ( 1- )
. , , . l-, l , . . , l- .


344



3.4 3.5 () M . M , , q(i) п(M ) i- q . : D -- M ; (I ) -- I - M п(M ). q SB (I ) -- (I ) I - ; M (I ) = (I ) - SB (I ). S {1, 2,... ,m} M , i S ~ ~ d (i ) = B , (i ) = B , B -- , d ~ . d= I S , D - M (I ) SB (I ) < D - M (I )+ q(i) .
~ M

IGRAN -- , S . i- , S -1. L -- i- ( , (i +1)- ). M L. , , D. Masst (L) = 1 ( Masst ) SB (I ) SB (I ) - sign(M (I, L))q(i) . M ( ) , - . 1- M .




345

3.5. I I ( 2- )
2- M , . 3.4 : ) D - M (I ) SB (I ) < D - M (I )+2q(i) ; ) i- , , . ) SB (I ) = SB (I )+ q(i) , 2 -2, , . , 3.5 2- M . , M1 M2 . - ( , ) , , .

4.
- [3], [4] [5]. , A, , . , .


346



, .


[1] .., .., .. - // . . 31. .: , 1976. . 5н33. [2] .. // . . 33. .: , 1978. . 5н68.




347

[3] .. // - . : - , 1982. . 89н121. [4] .. - // - . .: , 1975. . 5н82. [5] .., .. // . .: - , 1985. [6] . // . .: - , 1985. [7] . .. // VI . , 1983. [8] . // . .: - , 1985. [9] . .. // . 1987. . 292. 3. [10] ., . . .: , 1982. . 416.