4
$\begingroup$

Given an $n \times n$ shortest path distance matrix $D$. And a complete graph $G(D)$ on $n$ nodes, where edge $(i, j)$ has weight $D_{ij}$. Furthermore, the distance matrix $D$ is computed for a connected network $T$ of $n$ nodes and $n-1$ edges - i.e. the shortest path distance between two nodes in $T$.

About the network $T$:

  • There are exactly $n$ nodes and $n-1$ edges.
  • The network is one connected component, thus it is a tree.
  • All edges have positive length.

My problem is that if I compute a minimum spanning tree $T'$ of $G(D)$ using, for instance, Kruskal's algorithm will the resulting tree $T'= T$?

  • I tried to argue that they are indeed equal, because if we consider an edge $e$ has been added in a step of Kruskal's algorithm then this edge must have been a light edge thus it is also the shortest path distance.

I am not sure if this argument holds. How can I argue that $T' = T$?

$\endgroup$
1
  • $\begingroup$ What did you find when you worked through some small examples by hand? $\endgroup$
    – D.W.
    Mar 17, 2019 at 15:51

1 Answer 1

2
$\begingroup$

If we consider an edge $e$ has been added in a step of Kruskal's algorithm then this edge must have been a light edge thus it is also the shortest path distance.

You are almost there. Let me continue your approach.

Suppose edge $(u,v)\not\in T$. Let $P=(u_0=u, u_1, \cdots, u_k=v)$ be the unique path from $u$ to $v$ in $T$ where $k\gt1$. For each edge $(u_i, u_{i+1})$, $d_{u_iu_{i+1}}=w((u_i, u_{i+1}))\lt \sum_{0\le j\le k-1} w((u_j, u_{j+1}))= d_{uv}$, where $w$ is the weight/length function on edges of $T$.

Consider $t_0$, the point of time when edge $(u,v)$ had been determined to be part of $T'$ but had not been added to $T'$ yet by Kruskal's algorithm. At time $t_0$, for all $0\le i\le k-1$, $(u_i, u_{i+1})$, an edge that is shorter than $(u,v)$ must have been tried, which meant node $u_i$ and $u_{i+1}$ must have been connected by a path in $K(t_0)$, the edges of $G(D)$ that had been determined to be part of $T'$ at time $t_0$. That means before $t_0$, node $u$ and $v$ had been connected by a path in $K(t_0)$, which implies that edge $(u,v)$ would not be added by Kruskal's algorithm.

The paragraph above shows that all edges of $T'$ must be in $T$. Since the number of edges in each one of them is $n-1$, $T=T'$.


Here is a direct generalization as an exercise.

Exercise. Suppose the connected network $T$ is a connected network (the number of whose edges should be no less than $n-1)$ with a positive distance between each adjacent nodes. The rest of the setup is the same as in the question. Show that a minimum spanning tree $T'$ of $G(D)$ is also a minimum spanning tree of $T$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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