How Minimum Spanning Trees Optimize Network Design: Theory to Real‑World Gas Pipelines

1 Minimum Spanning Tree

1.1 Spanning Tree

A tree is a fundamental concept in graph theory. A connected acyclic graph is called a tree.

For an undirected connected graph, a spanning tree is a minimal connected subgraph that includes all vertices with the fewest possible edges, i.e., exactly |V|‑1 edges.

Properties of a spanning tree:

(1) It contains all vertices of the graph.

(2) There is exactly one path between any two vertices, so the number of edges equals vertices minus one.

1.2 Minimum Spanning Tree

A minimum spanning tree (MST) of a weighted undirected graph is a spanning tree whose total edge weight is minimal.

1.3 Minimum Spanning Tree Problem

The MST problem is a classic graph‑theoretic problem with many practical applications, such as designing cost‑effective communication lines, road networks, or gas pipelines.

2 Minimum Spanning Tree Algorithms

Many algorithms construct an MST by starting from an empty tree and repeatedly adding safe edges that do not create cycles.

Typical algorithms are Prim’s algorithm and Kruskal’s algorithm.

2.1 Prim’s Algorithm

Prim’s algorithm builds the MST by growing a vertex set; each vertex is added only once, so cycles cannot form.

The algorithm starts from an arbitrary vertex s, repeatedly selects the cheapest edge connecting the current tree to a new vertex, and expands until all vertices are included (“vertex‑addition” method).

2.2 Kruskal’s Algorithm

Kruskal’s algorithm builds the MST by considering edges, always choosing the smallest‑weight edge that does not create a cycle.

Starting with an empty edge set, it adds the cheapest admissible edge repeatedly until the tree spans all vertices (“edge‑addition” method).

3 Case Study (Natural Gas Pipeline Layout)

A city has seven districts that need gas pipelines. The matrix below gives possible routes and construction costs (0 means no connection). The goal is to design a pipeline layout that connects all districts with minimal total cost.

3.1 Solution

Using NetworkX’s implementation of Kruskal’s algorithm, the minimum spanning tree is obtained as shown:

4 Summary

This article introduced the concept of minimum spanning trees, described Prim’s and Kruskal’s algorithms, and demonstrated their application to a natural‑gas pipeline design problem.

References

youcans Python小白的数学建模课 https://www.zhihu.com/column/c_1381900867424075776