Say one has the following graph

enter image description here

One has $8$ (black) vertices.

Say one has a $8 \times 1$ vector of distances between each black vertex and the red vertex. By distances, I mean that all my vertices are members of a metric space, e.g. a geographical space. Let's denote this vector by $\boldsymbol{d}$.

Say one has a $8 \times 8$ matrix in which each element represents the percentage of edge-distance in common between two vertices (a fortiori with entries equal to $1$ on the main diagonal and a priori asymmetric since two vertices are very likely to share different percentages). Let's denote this matrix by $\boldsymbol{D}$.

Do you have any reference which explains how to compute the total distance over edges when having only $\boldsymbol{d}$ and $\boldsymbol{D}$ in hand?

Starting with a very simple case, and complexifying it progressively, I ended with

$|(\boldsymbol{D}^{-1})^{'} \boldsymbol{d}|$

Where the operator $|.|$ stands for the L$1$-norm, i.e. the sum of all the absolute elements' value of $(\boldsymbol{D}^{-1})^{'} \boldsymbol{d}$ (although the absolute-value of entries is not needed since everything is already positive).

Am I right by computing this (total graph) distance like this ?

  • $\begingroup$ Do you by "total distance" mean the number of edges in the graph? $\endgroup$ – wonce Sep 23 '17 at 16:26
  • $\begingroup$ @wonce. No I really mean that all my vertices are members of a metric space. As if each of the vertices were a location in a geographical world. $\endgroup$ – keepAlive Sep 23 '17 at 18:51
  • $\begingroup$ Are you assuming your graph is a tree (so there's exactly one path from any vertex to any other vertex)? $\endgroup$ – Gerry Myerson Jan 29 at 8:30
  • $\begingroup$ @GerryMyerson Yes it is a tree. $\endgroup$ – keepAlive Jan 29 at 9:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.