数学模型

Wang Haihua

🍈 🍉🍊 🍋 🍌

---

最小生成树

生成树

树是图论中的基本概念。连通的无圈图称为树（Tree），就是不包含循环的回路的连通图。

对于无向连通图，如下图所示，生成树（Spanning tree）是原图的极小连通子图，它包含原图中的所有 n 个顶点，并且有保持图连通的最少的边，即只有足以构成一棵树的 n-1 条边。

生成树满足：

• （1）包含连通图中所有的顶点；
• （2）任意两顶点之间有且仅有一条通路。因此，生成树中边的数量 = 顶点数 - 1。

对于非连通无向图， 遍历每个连通分量中的顶点集合所经过的边是多颗生成树，这些连通分量的生成树构成非连通图的生成森林 。

最小生成树和最大生成树

遍历连通图的方式通常有很多种，也就是说一张连通图可能有多种不同的生成树。

无向赋权图的生成树中，各条边的权重之和最小的生成树，称为最小生成树（minimum spanning tree，MST），也称最小权重生成树。

对应地，各条边的权重之和最大的生成树，称为最大生成树（maximum spanning tree）。

最小生成树问题

最小生成树（MST）是图论中的基本问题，具有广泛的实际应用，在数学建模中也经常出现。

例如，在若干城市之间铺设通信线路，使任意两个城市之间都可以通信，要使铺设线路的总费用最低，就需要找到最小生成树。类似地，路线设计、道路规划、官网布局、公交路线、网络设计，都可以转化为最小生成树问题，如要求总线路长度最短、材料最少、成本最低、耗时最小等。

在实际应用中，不仅要考虑网络连通，还要考虑连通网络的质量和效率，就形成了带有约束条件的最小生成树：

直径限制最小生成树（Bounded diameter minimum spanning tree）：对给定的连通图，满足直径限制的生成树中，具有最小权的树，称为直径限制最小生成树。直径限制最小生成树问题在资源优化问题中应用广泛，如网络设计的网络直径影响到网络的传输速度、效率和能耗。

度限制最小生成树（Degree constrained minimum spanning tree）：对给定的连通图，满足某个节点或全部节点的度约束（如入度不超过 k）的生成树中，具有最小权的树，称为度限制最小生成树。实际应用中，为了控制节点故障对整个系统的影响，需要对节点的度进行限制。

最小生成树算法

构造最小生成树的算法很多，通常是从空树开始，按照贪心法逐步选择并加入 n-1 条安全边（不产生回路），最终得到最小生成树。

最小生成树的典型算法有普里姆算法（Prim算法）和克鲁斯卡算法（Kruskal算法）。

普里姆算法（Prim算法）

Prim 算法以顶点为基础构造最小生成树，每个顶点只与连通图连接一次，因此不用考虑在加入顶点的过程中是否会形成回路。

算法从某一个顶点 s 开始，每次选择剩余的代价最小的边所对应的顶点，加入到最小生成树的顶点集合中，逐步扩充直到包含整个连通网的所有顶点，可以称为“加点法”。

Prim 算法中图的存贮结构采用邻接矩阵，使用一个顶点集合 u 构造最小生成树。由于不断向集合u中加点，还需要建立一个辅助数组来同步更新最小代价边的信息。

Prim 算法每次选择顶点时，都需要进行排序，但每次都只需要对一部分边进行排序。Prim 算法的时间复杂度为 O(n*n)，与边的数量无关，适用于边很多的稠密图。

克鲁斯卡算法（Kruskal算法）

Kruskal 算法以边为基础构造最小生成树，利用避圈思想，每次找到不使图构成回路的代价最小的边。

算法初始边数为 0，每次选择一条满足条件的最小代价边，加入到边集合中，逐步扩充直到包含整个生成树，可以称为“加边法”。

Kruskal 算法中图的存贮结构采用边集数组，权值相等的边在数组中的排列次序是任意的。Kruskal算法开始就要对所有的边进行排序，之后还需要对所有边应用 Union-Find算法，但不再需要排序。

Kruskal 算法的时间复杂度为 O(mlogm)，主要是对边排序的时间复杂度，适用于边较少的稀疏图。

案例(天然气管道铺设问题)

某市区有 7个小区需要铺设天然气管道，各小区的位置及可能的管道路线、费用如图所示，要求设计一个管道铺设路线，使天然气能输送到各个小区，且铺设管道的总费用最小。 其中数值0代表无管道连接，非零代表建设费用。

	0	1	2	3	4	5	6	7	8	9
0	0	5	6	0	0	0	0	0	9	0
1	5	0	1	2	12	0	5	0	0	2
2	6	1	0	6	0	7	0	0	0	0
3	0	2	6	0	8	0	4	0	0	3
4	0	12	0	8	0	0	0	1	0	0
5	0	0	7	0	0	0	5	0	7	0
6	0	5	0	4	0	5	0	10	0	0
7	0	0	0	0	1	0	10	0	0	0
8	9	0	0	0	0	7	0	0	0	0
9	0	2	0	3	0	0	0	0	0	0

求解

利用NetworkX种的克鲁斯卡算法，计算出最小生成树为：

---

import numpy as np
import matplotlib.pyplot as plt # 导入 Matplotlib 工具包
import networkx as nx  # 导入 NetworkX 工具包
import pandas as pd

B=np.array([[ 0,  5,  6,  0,  0,  0,  0,  0,  9,  0],
       [ 5,  0,  1,  2, 12,  0,  5,  0,  0,  2],
       [ 6,  1,  0,  6,  0,  7,  0,  0,  0,  0],
       [ 0,  2,  6,  0,  8,  0,  4,  0,  0,  3],
       [ 0, 12,  0,  8,  0,  0,  0,  1,  0,  0],
       [ 0,  0,  7,  0,  0,  0,  5,  0,  7,  0],
       [ 0,  5,  0,  4,  0,  5,  0, 10,  0,  0],
       [ 0,  0,  0,  0,  1,  0, 10,  0,  0,  0],
       [ 9,  0,  0,  0,  0,  7,  0,  0,  0,  0],
       [ 0,  2,  0,  3,  0,  0,  0,  0,  0,  0]])
B = pd.DataFrame(B)

print(B.to_markdown())

|    |   0 |   1 |   2 |   3 |   4 |   5 |   6 |   7 |   8 |   9 |
|---:|----:|----:|----:|----:|----:|----:|----:|----:|----:|----:|
|  0 |   0 |   5 |   6 |   0 |   0 |   0 |   0 |   0 |   9 |   0 |
|  1 |   5 |   0 |   1 |   2 |  12 |   0 |   5 |   0 |   0 |   2 |
|  2 |   6 |   1 |   0 |   6 |   0 |   7 |   0 |   0 |   0 |   0 |
|  3 |   0 |   2 |   6 |   0 |   8 |   0 |   4 |   0 |   0 |   3 |
|  4 |   0 |  12 |   0 |   8 |   0 |   0 |   0 |   1 |   0 |   0 |
|  5 |   0 |   0 |   7 |   0 |   0 |   0 |   5 |   0 |   7 |   0 |
|  6 |   0 |   5 |   0 |   4 |   0 |   5 |   0 |  10 |   0 |   0 |
|  7 |   0 |   0 |   0 |   0 |   1 |   0 |  10 |   0 |   0 |   0 |
|  8 |   9 |   0 |   0 |   0 |   0 |   7 |   0 |   0 |   0 |   0 |
|  9 |   0 |   2 |   0 |   3 |   0 |   0 |   0 |   0 |   0 |   0 |

G = nx.from_pandas_adjacency(B)

T = nx.minimum_spanning_tree(G)  # 返回包括最小生成树的图
print(T.nodes)  # 最小生成树的 顶点
print(T.edges)  # 最小生成树的 边
print(sorted(T.edges)) # 排序后的 最小生成树的 边
print(sorted(T.edges(data=True)))  # data=True 表示返回值包括边的权重

mst1 = nx.tree.minimum_spanning_edges(G, algorithm="kruskal") # 返回最小生成树的边
print(list(mst1))  # 最小生成树的 边
mst2 = nx.tree.minimum_spanning_edges(G, algorithm="prim",data=False)  # data=False 表示返回值不带权
print(list(mst2))

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[(0, 1), (1, 2), (1, 3), (1, 9), (3, 6), (3, 4), (4, 7), (5, 6), (5, 8)]
[(0, 1), (1, 2), (1, 3), (1, 9), (3, 4), (3, 6), (4, 7), (5, 6), (5, 8)]
[(0, 1, {'weight': 5}), (1, 2, {'weight': 1}), (1, 3, {'weight': 2}), (1, 9, {'weight': 2}), (3, 4, {'weight': 8}), (3, 6, {'weight': 4}), (4, 7, {'weight': 1}), (5, 6, {'weight': 5}), (5, 8, {'weight': 7})]
[(1, 2, {'weight': 1}), (4, 7, {'weight': 1}), (1, 3, {'weight': 2}), (1, 9, {'weight': 2}), (3, 6, {'weight': 4}), (0, 1, {'weight': 5}), (5, 6, {'weight': 5}), (5, 8, {'weight': 7}), (3, 4, {'weight': 8})]
[(0, 1), (1, 2), (1, 3), (1, 9), (3, 6), (6, 5), (5, 8), (3, 4), (4, 7)]

pos={0:(1,1),2:(3,1),3:(3,5),4:(5,1),5:(5,5),6:(7,1),7:(7,5),8:(9,1),9:(9,5),1:(1,5)}  # 指定顶点位置
nx.draw(G, pos, with_labels=True, node_color='c', alpha=0.8)  # 绘制无向图
labels = nx.get_edge_attributes(G,'weight')
nx.draw_networkx_edge_labels(G,pos,edge_labels=labels, font_color='m') # 显示边的权值
nx.draw_networkx_edges(G,pos,edgelist=T.edges,edge_color='orange',width=4)  # 设置指定边的颜色
plt.savefig('images/opt0701.png')
plt.show()