La construcción de un gráfico de pares distancias

Question

Yo no estoy familiarizado con los gráficos. Sin embargo, tengo curiosidad sobre una pregunta en los gráficos. Dado un conjunto finito equipado con una métrica, hay algún estudio en el siguiente problema?

Problema: dada la métrica $d$ de vértices en $V$, construir el grafo no dirigido con el mínimo número de aristas tal que, para cada par de vértices $(v_1, v_2)\in V$, el camino más corto de $v_1$ $v_2$es igual a $d(v_1, v_2)$. Es este gráfico único?

Este tipo de gráfico de la construcción, sería muy importante para el modelo de depedency de los agentes económicos dinámica de sistemas.

Answer 1

En general, ¿por qué debería ser único? Si usted tiene dos disjuntas decir rutas entre v1 y v2 que son la misma suma de borde de longitudes, pero diferente de la conectividad de los vértices a lo largo de la ruta, puede girar el borde longitudes de un camino a otro, pero mantener la conectividad, por lo que no sería único en términos de borde de longitudes.

No esta imponer un tipo de problema geométrico, aunque? Lo que si edge longitudes de producir un diseño que es contradictorio. Por ejemplo, digamos v1 y v2 están en distintos subdiagramas y todos los otros vértices adyacentes a la v1 están en G1 y todos los adyacentes a v2 están en el G2, y decir todas las otras distancias de los vértices de G1 a los del G2 son muy largos decir y la distancia entre v1 y v2 es corto...Quizás este no sea imposible? I. e. G no puede ser integrable en d dimensiones.

Soy consciente de que usted puede tomar la matriz de distancias y obtener, o intentar obtener) una presentación en sin embargo muchas de las dimensiones que quieras, tomando los vectores propios (por decir el poder de la iteración) de todos los pares de la ruta más corta de la matriz calculada por el algoritmo Floyd-Warshall de que la matriz de distancias.