Документ взят из кэша поисковой машины. Адрес оригинального документа : http://dfgm.math.msu.su/files/ivanov-tuzhilin/Problems2012.pdf
Дата изменения: Fri Jul 6 15:01:24 2012
Дата индексирования: Sat Apr 9 22:55:14 2016
Кодировка:

. . , . .
. , G , G. , ( ). G , G -- . M -- G, , G M . . . . (1) G E , : E R+ -- . . , . H -- G , H (H ) H . , (G) G G. G -- , u v -- . , u v , d (u, v ). , d -- G ( , ). , G . (2) X -- . G V , V X . G X . G -- , -- X , uv E , u v G, (uv ) = (u, v ). (G) G (G). (3) . G -- V , X -- . : V X X G, G . 1

2

( ) (uv ) = (u), (v ) . (G) (). , , G -- . , , , G -- . (4) G ( -- , -- ) G . G X G X , G . X , , .. G, (, ). (). , , , , , . , , . , -- . , : G X , G, (3). X , .. , , , . , (3) , , , , , . , . , G , , G .

1

, . X -- M -- . Gc (M ) X , M . Gc (M ) smt(M ). G Gc (M ), (G) = smt(M ), X , M . -

3

. , G ( , , X ), G , ( -- smt, "Steiner Minimal Tree"). . X , M , Nc (M ) : V X , M (V ). Nc (M ), smt(M ). Nc (M ), smt(M ), M . . . , , 120 , , 3. , 1 , 2 180 , , . , . , , . , . . 1.1. , . . . G -- G. , G , G Gm , W . W , "" "". Gm , "" "". , 1 3, 1. [3] (.. ) , .

4

1.2. ( ), . 1.3. , . , , 1.2. [3] , . 1.4. , . [3] (, ) . (.. ), . 1.5. , . . 1.6. , . . G. f ( , , , -- ). v (v , f ) (0, 2 ). (v , f ) . : G , -- , - ? , ( ) (v , f ) = |f | - 2 , (v , f ) = 2 ,
v : v f f : f v

|f | f , f , -- v . , , , .

5

1.7. . [1] [2] , . 1.8. , , . , . ,

1.9. , . , , 1.2. , 1.2 , . 1.10. . 1.11. , . X -- . A X > 0 U (A) U (x, ) = {y X | (x, y ) < } x A. U (A) - A. A B -- X . H (A, B ) , A U (B ) B U (A). H (A, B ) A B . K(X ) X , H K(X ). 1.12. K(X ). A B -- . ( ) GH (A, B ) H f (A), f (B ) , f A B X . GH (A, B ) - A B . K . GH K. 1.13. K. X -- M -- . Sc (M ) X , M . Sc (M ) mst(M ). D Sc (M ), (D) = mst(M ),

6

M ( mst "Minimal Spanning Tree"). M X , mst(M ) = 0, . M X sr(M ) = smt(M )/ mst(M ) ( M ). sr(M ) M X sr(X ) X . -- , . [4] [3]. . 1.14. . , . , , , . , [7], Rn M Rn , f (n) . , . 1.15. , , ? ? ? 1.1. , 1, . (.. , v (x, y ) |x| + |y |) 2/3, . [8], , , , , . (.. ), , . [9]. , , ,

7

120 . , , . [3]. 1.16. , , , , . , . , , , , . [10]. , , , . , . 1.17. , , . 1.18. , ? , . , Mg g 2 4g , 2 , Mg 4 (g - 1). , k - 2 /3 (k - 6)/3, 7 k 12g - 6. , k - nk , , ,
12g -6 k=7

n

k

(k - 6) = 4 (g - 1). 3

( nk .) , g = 2 77 , "" -- 18- ( ) 12 ( ). , (n7 , . . . , n12g-6 ), , , g . . 1.19. Mg 2 /3. , , , (

8

, Mg , , 120 ? ). 1.2. (.. , ) [11].

2

M -- , G -- , M . G -- M , u v G, M , (u, v ) d (u, v ). mf (M ) (G) G M . G M , (G) = mf (M ), M . G, M , (G) , G -- M , mpf (M ), G, (G) = mpf (M ), G M . [5] [6]. 2.1. , , . , , , . . [6], M , (M ) M : M X X . , , |M | R max- · , , , 1 m x = (x , . . . , x ) x = maxi |xi |. . , M Rm , M Rm . 2.2. X , .

9

2.1. . , M X , , k . . mf (M )/ mst(M ), , mf (M )/ smt(M ), -- . 2.3. . , , . 1.15. , . 2.4. , / ?

10

[1] Jarnik V., KЁ ossler O. O minimґ ґ grafech obsahujґ ґ n danґ bodu, alnich icich ych Cas P^ vґ ґ Mat. (Essen), 1934, v. 63, pp. 223235. esto ani [2] Du D.Z., Hwang F.K., Weng J.F. Steiner minimal trees for regular polygons, Discrete and Computational Geometry, 1987, v. 2, N 1, pp. 65-84. [3] .., .. . : , 2003. [4] Cieslik D. The Steiner Ratio. A Report. University of Greifswald. [5] Ivanov A.O., Tuzhilin A.A. One-dimensional Gromov minimal fil ling. arXiv:1101.0106v2 [math.MG] (http://arxiv.org) [6] .., .. . . ., 2012, . 203, N 5, . 65 118. [7] D. Z. Du, W. D. Smith, Disproofs of generalized GilbertPol lack conjecture on the Steiner ratio in three or more dimensions, J. Combin. Theory, 74 Ser. A, pp. 115130, 1996. [8] F. K. Hwang, On Steiner Minimal Trees with Rectilinear Distance, SIAM Journal on Applied Mathematics, bf 30, No. 1, pp. 104114, 1976. [9] B. Gao, D.-Z. Du, R. L. Graham, A Tight lower bound for the Steiner ratio in Minkowski planes, Disc. Math., 142, pp. 4963, 1995. [10] Ivanov A.O., Tuzhilin A.A. Minimal Networks. The Steiner Problem and Its Generalizations, CRC. Press, Boca Raton, 1994. [11] A. L. Edmonds, J. H. Ewing and R. S. Kulkarni, Regular Tessel lations of Surfaces and (p, q , 2)-Triangle Groups, The Annals of Mathematics, Second Series, 116, No. 1 (1982), pp. 113132.