<p>A distance matrix uniquely characterizes a topology in a given space on some give elements given some property such as distance assuming a few ground hypotheses...</p>

<p>In your case, the distance matrix is defined from a given vertex to the other. If the matrix is symmetric with 0-diagonals, you have a simply connected graph. If you have diagonal elements, you are allowed to use self-loops and if the matrix is not symmetric, you have a digraph.</p>

<p>An analytic proof could go like this: assume the distance matrix did not characterize the graph uniquely, then you could build two graphs that are different from the same matrix...</p>

<p>Note that graph equivalence is usually defined in terms of isomorphism.</p>

<p>Additional information on the subject can be found in terms of spectral craph theory, which only defines isospectrality, not isomorphism.</p>

CC BY-SA 3.0
2013-07-25T01:51:47.553Z
2013-07-25T01:51:47.553Z
Phil
<p>I think the following example with four points answers your question (though it gives multi-sets of distances). See <a href="http://cs.sunysb.edu/~skiena/papers/turnpike.ps" rel="nofollow noreferrer">Reconstructing Sets From Interpoint Distances</a> by Skiena, Smith, and Lemke for more information.</p>

<p><img src="https://i.sstatic.net/X7du0.png" alt="example"></p>

CC BY-SA 3.0
2013-07-31T05:45:14.943Z
Thank you for your example. I actually just came across the notion of "homometric" sets, which seems to answer my question (and the answer is "no").

Two sets are homometric if they are structurally different, and yet provide the same unordered pairwise distances. A nice toy example is the sets A = {0, 1, 2, 5, 7, 9, 12} and B = {0, 1, 5, 7, 8, 10, 12}. The (unordered) pairwise distances between elements in A is equal to the pairwise distance between elements in B, and yet A and B are quite different. Examples exist for points in 2D etc as well.
RachM
CC BY-SA 3.0
2013-07-31T05:52:16.817Z
I should also say I'm happy to have multisets of distances.
RachM
CC BY-SA 3.0
2013-07-22T23:47:54.357Z
2013-07-22T23:47:54.357Z
Yota Otachi
<p>There are $n$ points in $R^2$ (i.e. the 2D real space). We can think of them as a complete graph where edge weights correspond to the distance between points.</p>

<p>Let $D$ be the distance matrix between all pairs of points, such that entry $D_{ij}$ corresponds to the distance between points $i$ and $j$. This matrix is of size $n \times n$ and the upper-triangle contains the distances between unique pairings of points.</p>

<p>Now imagine I put the elements from the upper triangle into a set, such that you no longer know which pairs of points produce the distance values. This is essentially the set of edge weights, with no information regarding the relationship between the weight and the edge the weight belongs to.</p>

<p>If you are given two sets and they are identical, does this imply the graphs corresponding to each set are also essentially the same?</p>

CC BY-SA 3.0
2013-07-22T12:23:23.260Z
What do you mean by same graph ? A graph can be translated and rotated to move some other position, yet the distances remains same. Are you considering these two graphs are same ?
rnbguy
CC BY-SA 3.0
2013-07-22T13:57:00.130Z
I think "Reconstructing Sets From Interpoint Distances" (http://www.cs.sunysb.edu/~skiena/papers/turnpike.ps‎
) by Skiena, Smith, and Lemke answers the question (and the answer is _no_).
Yota Otachi
CC BY-SA 3.0
2013-07-23T03:51:27.640Z
This seems related to structural rigidity. A good follow up question would be asking what if the original $n$ points have algebraically independent coordinates.
Chao Xu
CC BY-SA 3.0
2013-07-31T05:42:42.353Z
@rnbcoder: yes, I am allowing translation and rotation, so 2 graphs (one translated/rotoated from the other) would be the same.
RachM
CC BY-SA 3.0
2013-07-31T05:47:26.203Z
@ChaoXu: yes, we can assume algebraically independent coordinates of the original n points. I read about rigidity, but it seems complete graphs are only rigid for a small n (I think it's for n <= 3, but I can't quite remember...).
RachM
<graph-theory><co.combinatorics><tsp>
Given a set of distances (no info regarding what points the distances correspond to) from a complete graph, is the realization of the graph unique?
RachM
# Given a set of distances (no info regarding what points the distances correspond to) from a complete graph, is the realization of the graph unique?

(Asked by: username_0 on 2013-07-22)

There are $n$ points in $R^2$ (i.e. the 2D real space). We can think of them as a complete graph where edge weights correspond to the distance between points.

Let $D$ be the distance matrix between all pairs of points, such that entry $D\_{ij}$ corresponds to the distance between points $i$ and $j$. This matrix is of size $n \times n$ and the upper-triangle contains the distances between unique pairings of points.

Now imagine I put the elements from the upper triangle into a set, such that you no longer know which pairs of points produce the distance values. This is essentially the set of edge weights, with no information regarding the relationship between the weight and the edge the weight belongs to.

If you are given two sets and they are identical, does this imply the graphs corresponding to each set are also essentially the same?

**Tags:** graph-theory, co.combinatorics, tsp

> **Comments:**
> **username_1**: What do you mean by same graph ? A graph can be translated and rotated to move some other position, yet the distances remains same. Are you considering these two graphs are same ?  
> **username_2**: I think "Reconstructing Sets From Interpoint Distances" (http://www.cs.sunysb.edu/~skiena/papers/turnpike.ps‎ ) by Skiena, Smith, and Lemke answers the question (and the answer is _no_).  
> **username_3**: This seems related to structural rigidity. A good follow up question would be asking what if the original $n$ points have algebraically independent coordinates.  
> **username_0**: @rnbcoder: yes, I am allowing translation and rotation, so 2 graphs (one translated/rotoated from the other) would be the same.  
> **username_0**: @ChaoXu: yes, we can assume algebraically independent coordinates of the original n points. I read about rigidity, but it seems complete graphs are only rigid for a small n (I think it's for n <= 3, but I can't quite remember...).  

---

## 2 answers

### Answer by username_2 on 2013-07-22. Score: 8 | Accepted answer

I think the following example with four points answers your question (though it gives multi-sets of distances). See [Reconstructing Sets From Interpoint Distances](http://cs.sunysb.edu/~skiena/papers/turnpike.ps) by Skiena, Smith, and Lemke for more information.

![example](https://i.sstatic.net/X7du0.png)

> **Comments:**
> **username_0**: Thank you for your example. I actually just came across the notion of "homometric" sets, which seems to answer my question (and the answer is "no").  Two sets are homometric if they are structurally different, and yet provide the same unordered pairwise distances. A nice toy example is the sets A = {0, 1, 2, 5, 7, 9, 12} and B = {0, 1, 5, 7, 8, 10, 12}. The (unordered) pairwise distances between elements in A is equal to the pairwise distance between elements in B, and yet A and B are quite different. Examples exist for points in 2D etc as well.  
> **username_0**: I should also say I'm happy to have multisets of distances.  

---

### Answer by username_4 on 2013-07-25. Score: 0

A distance matrix uniquely characterizes a topology in a given space on some give elements given some property such as distance assuming a few ground hypotheses...

In your case, the distance matrix is defined from a given vertex to the other. If the matrix is symmetric with 0-diagonals, you have a simply connected graph. If you have diagonal elements, you are allowed to use self-loops and if the matrix is not symmetric, you have a digraph.

An analytic proof could go like this: assume the distance matrix did not characterize the graph uniquely, then you could build two graphs that are different from the same matrix...

Note that graph equivalence is usually defined in terms of isomorphism.

Additional information on the subject can be found in terms of spectral craph theory, which only defines isospectrality, not isomorphism.


---

