Steiner Points

Minimum Network Problems

A network is a graph where all the vertices are connected. How is this different from a spanning tree? A spanning tree must be a subgraph of the original network or the super graph. A network must connect all vertices of the original graph, but may introduce new vertices called junction points and new edges that were not in the original graph. That said, all spanning trees are networks, but not all networks are spanning trees.

Below is a complete graph on 3 vertices (K₃). It shows the weight of each edge and a progression of connecting these vertices with greater efficiency, until we get the minimum network using a special type of a junction called a Steiner point.

Terminology

• • • The network of minimum weight that connects all the points of a graph is called the shortest network or minimum network.
      

    • A point in a network that is not one of the original points is called a junction point.
      

    • A junction point in a network formed by three edges coming together forming three congruent angles (120˚ angles) is a called a Steiner point of the network.

Below is a network on 4 vertices. It shows the weight of each edge and a progression of connecting these vertices more efficiently, first by removing the redundancy created by the circuit, then by implementing interior junction points until we get the minimum network using two Steiner points.