2

In the following, I assume the set of all feasible solutions is the set $\{(T,uv):T$ is a not necessarily minimum spanning tree of $G$ and $uv$ is a distinguished edge in $T\}$, with the cost of a particular solution $(T,uv)$ being the sum of the edges in $T$ minus $\min(D,w(uv))$. Let $(T, uv)$ be an optimal solution to the problem you describe, having ...


2

If there is not a unique light edge crossing any cut, it means that every node has at least 2 edges of minimum weight. If you use Prim's algorithm to build your MST which is: Grow the tree, adding nodes one by one. On each step, select the minimum weight edge leading to a new node. You realise that whatever is the starting node, you have at least 2 choices....


1

Run Kruskal's algorithm on the weighted graphs of all buildings as vertices and all pipes with original costs as edges with weights, with the following modification. When we are going to select the next edge (pipe) whose weight (cost) is minimum among the available edges, we choose one among the active pipes first if there is such a pipe. At end of the ...


1

No. Here is a proof. Suppose $G$ is a weighted undirected graph such that for every cut of the graph, there is not a unique lightest edge crossing the cut. Let $M$ be a (or "the" in case it is unique) minimum spanning tree of $G$. Let $v$ be a leaf node of $M$. Consider the cut $\{\{v\},V\setminus \{v\}\}$ of $G$. Since $M$ is spanning, it contains an ...


1

I found this answer in a book: Consider a graph with 3 vertices a,b,c and weights w(a,b) = w(a,c) = 1 and w(b,c) = 2. The graph has a unique minimal spanning tree (containing edges (a,b) and (a,c)), however cut ({a}, {b,c}) doesn’t have a unique light edge crossing the cut. I hope it helps!


Only top voted, non community-wiki answers of a minimum length are eligible