길버트-폴라크 추측

Gilbert–Pollack conjecture

수학에서 길버트-폴라크 추측()은 유클리드 평면에서 같은 점 집합에 대한 슈타이너 트리와 유클리드 최소 신장 트리의 길이 비율에 대한 검증되지 않은 추측입니다.그것은 [1]1968년 에드거 길버트와 헨리 O. 폴락에 의해 제안되었습니다.

진술

평면에서 점 집합의 경우, 주어진 점만 끝점으로 갖는 점을 연결하는 선 세그먼트의 최단 네트워크는 집합의 유클리드 최소 신장 트리입니다.지정된 점 집합에 없는 추가 끝점을 사용하여 더 짧은 네트워크를 구성할 수 있습니다.이러한 추가 점을 스타이너 점이라고 하며 이를 사용하여 구성할 수 있는 최단 네트워크를 스타이너 최소 트리라고 합니다.슈타이너 비율은 유클리드 최소 신장 트리와 슈타이너 최소 신장 트리의 길이 비율의 최고점입니다.Steiner 최소 트리가 짧기 때문에 이 비율은 항상 [2]1보다 큽니다.

슈타이너 비율의 하한은 단위 측면 길이의 등변 삼각형의 정점에서 3개의 점으로 제공됩니다.이 세 점의 경우, 유클리드 최소 신장 트리는 총 길이가 2인 삼각형의 두 모서리를 사용합니다.Steiner 최소 트리는 세 점을 모두 삼각형의 중심에 있는 Steiner 점에 연결하고 총 는보다 작습니다. 이 예에서 Steiner 비율은 2≈ 2[2]이어야 합니다.

길버트-폴랙 추측에 따르면 이 예는 슈타이너 비율에 대한 최악의 경우이며, 이 비율은 2/ (\ 2와 같습니다. 즉, 유클리드 평면에 설정된 모든 유한 점에 대해,유클리드 최소 스패닝 트리는 스타이너 최소 [2]트리 길이의 2 {3)를 초과할 수 없습니다.

증명 시도

이 추측은 딩주두와 [3][2]황광밍의 증명으로 유명한데, 나중에 심각한 [4][5]차이가 있는 것으로 밝혀졌습니다.

결함이 있는 두와 황의 결과를 바탕으로 J. Hyam Rubinstein과 Jia F.웡은 일정한 [6]곡률의 2차원 구에 대해서도 이 2 /결론지었지만, 듀와 기저 결과의 격차로 인해 루빈스타인과 웡의도 현재 [7]증명되지 않은 것으로 간주됩니다.

레퍼런스

  1. ^ Gilbert, E. N.; Pollak, H. O. (January 1968). "Steiner Minimal Trees". SIAM Journal on Applied Mathematics. 16 (1): 1–29. doi:10.1137/0116001. ISSN 0036-1399. S2CID 123196263.
  2. ^ a b c d Du, D. Z.; Hwang, F. K. (1992-06-01). "A proof of the Gilbert-Pollak conjecture on the Steiner ratio". Algorithmica. 7 (1): 121–135. doi:10.1007/BF01758755. ISSN 0178-4617. S2CID 36038781.
  3. ^ Du, D. Z.; Hwang, F. K. (1990-12-01). "The Steiner ratio conjecture of Gilbert and Pollak is true". Proceedings of the National Academy of Sciences. 87 (23): 9464–9466. Bibcode:1990PNAS...87.9464D. doi:10.1073/PNAS.87.23.9464. ISSN 0027-8424. PMC 55186. PMID 11607122. S2CID 9811160.
  4. ^ Ivanov, A. O.; Tuzhilin, A. A. (2011-03-26). "The Steiner Ratio Gilbert–Pollak Conjecture Is Still Open". Algorithmica. 62 (1–2): 630–632. doi:10.1007/s00453-011-9508-3. S2CID 7486839.
  5. ^ Tuzhilin A., A.; Ivanov O., A (2014-02-25). "Du-Hwang Characteristic Area: Catch-22". arXiv:1402.6079 [math.MG].
  6. ^ Rubinstein, J.; Weng, J. (1997-03-01). "Compression Theorems and Steiner Ratios on Spheres". Journal of Combinatorial Optimization. 1: 67–78. doi:10.1023/A:1009711003807. ISSN 1382-6905. S2CID 35145869.
  7. ^ Innami, N.; Kim, B.H.; Mashiko, Y.; Shiohama, K. (1990-11-15). "The Steiner Ratio Conjecture of Gilbert-Pollak May Still Be Open". Algorithmica. 57 (4): 869–872. doi:10.1007/s00453-008-9254-3. ISSN 0178-4617. S2CID 30809157.