Incrustaciones de gráficos isomorfos en el espacio euclidiano

Aug 19 2020

Dado un gráfico no dirigido y no ponderado$G = (V, E)$, es posible encontrar un mapeo$f: V \rightarrow \mathbb{R}^k$para algunos$k$tal que por cada$i, j \in V$,$\|f(i) - f(j)\|_2^2 = \Delta(i, j)$, dónde$\Delta(i, j)$es la longitud del camino más corto entre$i$y$j$en$G$?

He estado probando algunos contraejemplos para los cuales estas incrustaciones isométricas en$\ell_2$no existen (por ejemplo, los 4 ciclos), pero en este caso funcionan.

Respuestas

12 KlausDraeger Aug 20 2020 at 01:53

Esto no es posible en general.

El ciclo de 4 es realmente útil para considerar: incrustarlo en$\mathbb{R}^k$en la forma en que lo describe requiere que las imágenes de los cuatro vértices sean coplanares, formando un cuadrado (ya que las distancias entre vértices adyacentes deben ser$1$y aquellos entre los pares no adyacentes deben ser$\sqrt{2}$).

Ahora considere el gráfico bipartito completo$K_{2,3}$. Llamemos a sus vértices$a_1,a_2,b_1,b_2,b_3$. En cualquier incrustación$f$satisfaciendo su condición, los 4 ciclos$(a_1,b_1,a_2,b_2)$,$(a_1,b_1,a_2,b_3)$y$(a_1,b_2,a_2,b_3)$todos tendrían que ser mapeados a cuadrados como arriba, pero las dos primeras de estas condiciones implican$f(b_2) = f(b_3)$, contradicción.