El problema del vendedor ambulante del analista es análogo al problema del vendedor ambulante en la optimización combinatoria . En su forma más simple y original, pregunta en qué condiciones puede un conjunto E en un espacio euclidiano bidimensional estar contenido dentro de una curva rectificable de longitud finita. Entonces, mientras que en el problema original del viajante de comercio, uno pregunta por la forma más corta de visitar cada vértice en un gráfico con una ruta discreta, esta versión analítica requiere que la curva visite quizás una cantidad infinita de puntos.
números β
A posteriori, para que E esté contenida en una curva rectificable Γ, dado que Γ tiene tangentes en H 1 -casi todos los puntos en Γ (donde H 1 denota una medida de Hausdorff unidimensional ), E debe verse plana cuando se amplían los puntos en E . Esto sugiere que una condición que nos diga si un conjunto podría estar contenido en una curva debe incorporar de alguna manera información sobre qué tan plano es E cuando hacemos zoom en puntos de E a diferentes escalas.
Esta discusión motiva la definición de la siguiente cantidad:
Donde Q es cualquier cuadrado,es la longitud lateral de Q , y dist ( x , L ) mide la distancia desde x a la línea L . Intuitivamente,es el ancho del rectángulo más pequeño que contiene la porción de E dentro de Q , y por lo tantonos da una noción invariante de escala de planitud .
Teorema del viajante de comercio de Jones en R 2
Sea Δ la colección de cuadrados diádicos, es decir,
dónde denota el conjunto de números enteros. Para un juego, definir
donde diámetro E es el diámetro de E . Entonces Peter Jones 's [1] viajante de analista teorema puede enunciarse como sigue:
- Hay un número C > 0 tal que siempre que E es un conjunto tal que β ( E ) <∞, E puede estar contenido en una curva con una longitud no mayor que Cβ ( E ).
- Por el contrario (y sustancialmente más difícil de probar), si Γ es una curva rectificable, entonces β (Γ)
1 (Γ).
Generalizaciones y curvatura de Menger
Espacio euclidiano y espacio de Hilbert
Kate Okikiolu demostró que el teorema del viajante se cumple en los espacios euclidianos generales , [2] es decir, el mismo teorema anterior es válido para conjuntos, d > 1, donde Δ es ahora la colección de cubos diádicos endefinido de manera similar como cuadrados diádicos. En su demostración, la constante C crece exponencialmente con la dimensión d .
Con algunas ligeras modificaciones a la definición de β ( E ), Raanan Schul [3] mostró que el teorema del viajante también es válido para los conjuntos E que se encuentran en cualquier espacio de Hilbert , y en particular, implica los teoremas de Jones y Okikiolu, donde ahora la constante C es independiente de la dimensión. (En particular, esto implica el uso de números β de bolas en lugar de cubos).
Curvatura de Menger y espacios métricos
Hahlomaa [4] ajustó aún más la definición de β ( E ) para obtener una condición para cuando un conjunto E de un espacio métrico arbitrario puede estar contenido en la imagen de Lipschitz de un subconjuntode medida positiva. Para ello, tuvo que redefinir la definición de los números β utilizando la curvatura de Menger (ya que en un espacio métrico no hay necesariamente una noción de cubo o de línea recta).
La curvatura de Menger , como en el ejemplo anterior, se puede usar para dar estimaciones numéricas que determinan si un conjunto contiene un subconjunto rectificable, y las pruebas de estos resultados frecuentemente dependen de números β .
Teorema de Denjoy-Riesz
El teorema de Denjoy-Riesz da condiciones generales bajo las cuales un conjunto de puntos puede ser cubierto por la imagen homeomórfica de una curva. Esto es cierto, en particular, para cada subconjunto compacto totalmente desconectado del plano euclidiano. Sin embargo, puede ser necesario que dicho arco tenga una longitud infinita y no cumpla las condiciones del teorema del viajante de comercio del analista.
Referencias
- ^ Jones, Peter (1990). "Conjuntos rectificables y el problema del viajante". Inventiones Mathematicae . 102 : 1-15. Código Bibliográfico : 1990InMat.102 .... 1J . doi : 10.1007 / BF01233418 .
- ^ Okikiolu, Kate (1992). "Caracterización de subconjuntos de curvas rectificables en Rn". Revista de la Sociedad Matemática de Londres . 46 (2): 336–348. doi : 10.1112 / jlms / s2-46.2.336 .
- ^ Schul, Raanan (2007). "Subconjuntos de curvas rectificables en el espacio de Hilbert — TSP del analista". Journal d'Analyse Mathématique . 103 : 331–375. arXiv : matemáticas / 0602675 . doi : 10.1007 / s11854-008-0011-y .
- ^ Hahlomaa, Immo (2005). "Curvatura de Menger y parametrizaciones de Lipschitz en espacios métricos" . Fondo. Matemáticas . 185 (2): 143-169. doi : 10.4064 / fm185-2-3 .