stringtranslate.com

Conjetura de Gilbert-Pollack

En matemáticas, la conjetura de Gilbert-Pollak es una conjetura no demostrada sobre la relación de las longitudes de los árboles de Steiner y los árboles de expansión mínima euclidianos para los mismos conjuntos de puntos en el plano euclidiano . Fue propuesta por Edgar Gilbert y Henry O. Pollak en 1968. [1]

Declaración

Problema sin resolver en informática :
¿El coeficiente de Steiner del plano euclidiano es igual a ?

Para un conjunto de puntos en el plano, la red más corta de segmentos de línea que conecta los puntos, teniendo solo los puntos dados como puntos finales, es el árbol de expansión mínimo euclidiano del conjunto. Puede ser posible construir una red más corta utilizando puntos finales adicionales, no presentes en el conjunto de puntos dado. Estos puntos adicionales se denominan puntos de Steiner y la red más corta que se puede construir utilizándolos se denomina árbol mínimo de Steiner . El coeficiente de Steiner es el supremo , sobre todos los conjuntos de puntos, del cociente de las longitudes del árbol de expansión mínimo euclidiano con el árbol mínimo de Steiner. Debido a que el árbol mínimo de Steiner es más corto, este cociente siempre es mayor que uno. [2]

Un límite inferior del coeficiente de Steiner lo proporcionan tres puntos en los vértices de un triángulo equilátero de longitud de lado unidad. Para estos tres puntos, el árbol de expansión mínima euclidiana utiliza dos aristas del triángulo, con una longitud total de dos. El árbol mínimo de Steiner conecta los tres puntos con un punto de Steiner en el centroide del triángulo, con la longitud total más pequeña . Debido a este ejemplo, el coeficiente de Steiner debe ser al menos . [2]

La conjetura de Gilbert-Pollak establece que este ejemplo es el peor caso para el coeficiente de Steiner, y que este coeficiente es igual a . Es decir, para cada punto finito establecido en el plano euclidiano, el árbol de expansión mínimo euclidiano no puede ser más largo que 10 veces la longitud del árbol mínimo de Steiner. [2]

Intento de prueba

La conjetura es famosa por su prueba por Ding-Zhu Du y Frank Kwang-Ming Hwang, [3] [2] que más tarde resultó tener una grave laguna. [4] [5]

Basándose en el resultado erróneo de Du y Hwang, J. Hyam Rubinstein y Jia F. Weng concluyeron que el coeficiente de Steiner también es para una esfera bidimensional de curvatura constante , [6] pero debido a la brecha en el resultado base de Du y Hwang, el resultado de Rubinstein y Weng ahora también se considera como no probado todavía. [7]

Referencias

  1. ^ Gilbert, EN; Pollak, HO (enero de 1968). "Árboles mínimos de Steiner". Revista SIAM de Matemáticas Aplicadas . 16 (1): 1–29. doi :10.1137/0116001. ISSN  0036-1399. S2CID  123196263.
  2. ^ abcd Du, DZ; Hwang, FK (1992-06-01). "Una prueba de la conjetura de Gilbert-Pollak sobre el cociente de Steiner". Algorithmica . 7 (1): 121–135. doi :10.1007/BF01758755. ISSN  0178-4617. S2CID  36038781.
  3. ^ Du, DZ; Hwang, FK (1990-12-01). "La conjetura de la razón de Steiner de Gilbert y Pollak es verdadera". Actas de la Academia Nacional de Ciencias . 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, AO; Tuzhilin, AA (26 de marzo de 2011). "La conjetura de Gilbert–Pollak sobre la relación de Steiner aún está abierta". Algorithmica . 62 (1–2): 630–632. doi :10.1007/s00453-011-9508-3. S2CID  7486839.
  5. ^ Tuzhilin A., A.; Ivanov O., A (25 de febrero de 2014). "Área característica de Du-Hwang: Catch-22". arXiv : 1402.6079 [math.MG].
  6. ^ Rubinstein, J.; Weng, J. (1997-03-01). "Teoremas de compresión y razones de Steiner en esferas". Journal of Combinatorial Optimization . 1 : 67–78. doi :10.1023/A:1009711003807. ISSN  1382-6905. S2CID  35145869.
  7. ^ Innami, N.; Kim, BH; Mashiko, Y.; Shiohama, K. (15 de noviembre de 1990). "La conjetura del ratio Steiner de Gilbert-Pollak aún puede estar abierta". Algorítmica . 57 (4): 869–872. doi :10.1007/s00453-008-9254-3. ISSN  0178-4617. S2CID  30809157.