Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
Why don't you just start with a complete graph, then eliminate any edge $(v_1, v_2)$ for which there is a vertex $v_3$ such that $d(v_1,v_3) + d(v_3,v_2) = d(v_1,v_2)$? –  Robert Israel Oct 5 '12 at 18:40
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)$ –  user38397 Oct 5 '12 at 18:52

1 Answer 1

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.

share|improve this answer
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. –  user38397 Oct 5 '12 at 21:21

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.