Skip to main content
added 30 characters in body
Source Link
MthQ
  • 41
  • 3
  • 15

Given a $n$x$n$ distance matrix of some undirected weighted tree graph, is it possible to infer the underlying tree and its edge weights?

For example, suppose we are given the following distance matrix \begin{pmatrix} 0 & 1 & 4 & 5 & 6 \\ 1 & 0 & 3 & 4 & 5 \\ 4 & 3 & 0 & 1 & 2 \\ 5 & 4 & 1 & 0 & 3 \\ 6 & 5 & 2 & 3 & 0 \end{pmatrix} Assuming strictly positive weights, we know that in each row every minimum corresponds to an edge and its weight, i.e. $1 \leftrightarrow 2$, $3\leftrightarrow 4$ and $3 \leftrightarrow 5$. From there, it's easy to determine that the underlying weighted adjacency graph is given by \begin{pmatrix} 0 & 1 & 0 & 0 & 0 \\ 1 & 0 & 3 & 0 & 0 \\ 0 & 3 & 0 & 1 & 2 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 2 & 0 & 0 \end{pmatrix} How to solve this problem in general for strictly positive weights?

Given a $n$x$n$ distance matrix of some undirected weighted tree graph, is it possible to infer the underlying tree and its edge weights?

For example, suppose we are given the following distance matrix \begin{pmatrix} 0 & 1 & 4 & 5 & 6 \\ 1 & 0 & 3 & 4 & 5 \\ 4 & 3 & 0 & 1 & 2 \\ 5 & 4 & 1 & 0 & 3 \\ 6 & 5 & 2 & 3 & 0 \end{pmatrix} Assuming strictly positive weights, we know that in each row every minimum corresponds to an edge and its weight, i.e. $1 \leftrightarrow 2$, $3\leftrightarrow 4$ and $3 \leftrightarrow 5$. From there, it's easy to determine that the underlying weighted adjacency graph is given by \begin{pmatrix} 0 & 1 & 0 & 0 & 0 \\ 1 & 0 & 3 & 0 & 0 \\ 0 & 3 & 0 & 1 & 2 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 2 & 0 & 0 \end{pmatrix} How to solve this problem in general?

Given a $n$x$n$ distance matrix of some undirected weighted tree graph, is it possible to infer the underlying tree and its edge weights?

For example, suppose we are given the following distance matrix \begin{pmatrix} 0 & 1 & 4 & 5 & 6 \\ 1 & 0 & 3 & 4 & 5 \\ 4 & 3 & 0 & 1 & 2 \\ 5 & 4 & 1 & 0 & 3 \\ 6 & 5 & 2 & 3 & 0 \end{pmatrix} Assuming strictly positive weights, we know that in each row every minimum corresponds to an edge and its weight, i.e. $1 \leftrightarrow 2$, $3\leftrightarrow 4$ and $3 \leftrightarrow 5$. From there, it's easy to determine that the underlying weighted adjacency graph is given by \begin{pmatrix} 0 & 1 & 0 & 0 & 0 \\ 1 & 0 & 3 & 0 & 0 \\ 0 & 3 & 0 & 1 & 2 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 2 & 0 & 0 \end{pmatrix} How to solve this problem in general for strictly positive weights?

edited title
Link
MthQ
  • 41
  • 3
  • 15

Infering Inferring tree graph from distance matrix

Source Link
MthQ
  • 41
  • 3
  • 15

Infering tree graph from distance matrix

Given a $n$x$n$ distance matrix of some undirected weighted tree graph, is it possible to infer the underlying tree and its edge weights?

For example, suppose we are given the following distance matrix \begin{pmatrix} 0 & 1 & 4 & 5 & 6 \\ 1 & 0 & 3 & 4 & 5 \\ 4 & 3 & 0 & 1 & 2 \\ 5 & 4 & 1 & 0 & 3 \\ 6 & 5 & 2 & 3 & 0 \end{pmatrix} Assuming strictly positive weights, we know that in each row every minimum corresponds to an edge and its weight, i.e. $1 \leftrightarrow 2$, $3\leftrightarrow 4$ and $3 \leftrightarrow 5$. From there, it's easy to determine that the underlying weighted adjacency graph is given by \begin{pmatrix} 0 & 1 & 0 & 0 & 0 \\ 1 & 0 & 3 & 0 & 0 \\ 0 & 3 & 0 & 1 & 2 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 2 & 0 & 0 \end{pmatrix} How to solve this problem in general?