4
$\begingroup$

I am not familiar with graphs. However, I am curious about a question on graphs. Given a finite set equipped with a metric, is there any studying on the following problem?

Problem: given the metric $d$ for vertexes on $V$, build the undirected graph with the minimum number of edges such that, for each pair of vertices $(v_1, v_2)\in V$, the shortest path from $v_1$ to $v_2$ equals $d(v_1, v_2)$. Is this graph unique?

This kind of graph building would be very important to model depedency of agents on economical dynamic systems.

  • 0
    Actually I just want to know if this is a known problem or if there is a field of study for this kind of problem. What would be the complexity of your algorithm? I think it is $O(n^2)$2012-10-05

1 Answers 1

0

In general why should it be unique? If you have two disjoint say paths between v1 and v2 that are the same sum of edge lengths, but different connectivity of the vertices along the path, you could rotate the edge lengths from one path to the other, but keep the connectivity, so it wouldn't be unique in terms of edge lengths.

Doesn't this impose a kind of geometric problem though? What if edge lengths produce a layout that's contradictory. For instance say v1 and v2 are in separate subgraphs and all the other vertices adjacent to v1 are in G1 and all adjacent to v2 are in G2, and say all the other distances from vertices in G1 to those in G2 are very long say and the distance between v1 and v2 is short...Might this not be impossible? I.e. G may not be embeddable in d-dimensions.

I'm aware that you can take the distance matrix and obtain (or attempt to obtain) a layout in however many dimensions you like by taking the eigenvectors (by say the power iteration) of the all pairs shortest path matrix computed by the Floyd-Warshall algorithm from that distance matrix.

  • 0
    Cris, I'm sorry, but I don't understand your point. Since I wrote that $d$ is a metric in mathematical sense, it will always be finite. In other words, I can always construct a graph by combining all vertices. Hence, the problem has always a solution.2012-10-05