patternMinor
Constructing a minimum spanning tree from an all-shortest path graph?
Viewed 0 times
pathgraphshortestallminimumconstructingfromspanningtree
Problem
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$:
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 am not sure if this argument holds. How can I argue that $T' = 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$?
Solution
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$.
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$.
Context
StackExchange Computer Science Q#105644, answer score: 2
Revisions (0)
No revisions yet.