Puede finita de espacio métrico incrustado en el plano gráfico?

Question

Supongamos $(X,d)$ es finito, métrica, es decir,$|X|<\infty$. No siempre existe un promedio ponderado de plano gráfico de $G=(V,E,w)$ y una inyección de $f:X\rightarrow V$ de manera tal que la siguiente está satisfecho? $$\forall x,y\in X, d(x,y)=\min\{\sum_{e\in P}w(e)\mid P\text{ is a path from }f(x)\text{ to }f(y)\}$$

Tenga en cuenta que podría haber algún punto de transferencia, es decir,$|V|\geq |X|$.

Si no, ¿cuál es la condición necesaria y suficiente? Estoy bastante interesado en este problema, y no pude encontrar muchos resultados relevantes. La mayoría de los artículos que he encontrado considerar los casos en contrario, dicen que la incrustación gráfico métrica para algunos normativa espacio con distorsión. Empecé a pensar en esta pregunta cuando me enteré de árbol de métricas.

Answer 1

En general, la respuesta es negativa. Consideremos el conjunto a $X$ de los vértices del gráfico bipartito $K_{3,3}$ como un espacio métrico. Definir la distancia en el set $X$ poniendo $d(x,y)=3$ si los vértices $x$ $y$ pertenecen a una parte de la $K_{3,3}$ $d(x,y)=2$ si los vértices $x$ $y$ pertenecen a diferentes partes de $K_{3,3}$. Dado que el gráfico de $K_{3,3}$ no es plana, no existe diferentes vértices $x_1, y_1, x_2, y_2\in X$ de manera tal que los vértices $x_1$ $x_2$ pertenecen a una parte de la gráfica de $K_{3,3}$, los vértices $y_1$ $y_2$ pertenecen a la otra parte de la gráfica de $K_{3,3}$, y en el dibujo de la gráfica de $G(X, E, w)$ el menor ponderado de los caminos que conectan $f(x_1)$ $f(y_1)$ $f(x_2)$ $f(y_2)$ intersecta en un punto de $p$. A continuación, una de las rutas de $f(x_1)-p-f(x_2)$ o $f(y_1)-p-f(y_2)$ tiene el promedio ponderado de longitud en la mayoría de las $2$, pero $d(x_1,x_2)=d(y_1,y_2)=3$.