Ravindra Ranwala's Blog

Electronic circuit designs often need to make the pins of several components electrically equivalent by wiring them together. To interconnect a set of $n$ pins, we can use an arrangement of  $n - 1$ wires, each connecting two pins. Of all such arrangements, the one that uses the least amount of wire is usually the most desirable. We can model this wiring problem with a connected, undirected graph $G = (V, E)$, where $V$ is the set of pins, $E$ is the set of possible interconnections between pairs of pins, and for each edge $(u,  \;v) \in E$, we have a weight $w(u,  v)$ specifying the cost (amount of wire needed) to connect $u$ and $v$. We then wish to find an acyclic subset $T \subseteq E$ that connects all of the vertices and whose total weight is minimized. $$\LARGE w(T) = \sum_{(u, \;v) \in T} w(u, \;v)$$ Since $T$ is acyclic and connects all of the vertices, it must form a tree, which we call a spanning tree since it “spans” the graph $G$. We call the problem of...