最小生成树问题
树
连通图 G = ( V , E ) G=(V,E) G=(V,E),若G中不含任何回路,则称G为树。
∣ V ∣ = 1 |V |=1 ∣V∣=1时称之为平凡树
生成树
G = ( V , E ) G=(V,E) G=(V,E),若G的一个生成子图是一棵树,则称之为G的一棵生成树,或者支撑树
定理
任何连通图至少有一棵生成树
最小生成树
无向图G的所有生成树中,边的权值总和最小的称为G的最小生成树,或最短树
性质
假设一个图中存在最小生成树,并且该图具有n个节点,m条边,则该图的最小生成树一定含有n个节点,并且具有n-1条边
最小生成树构造方法
- Kruskal算法
每次选择一条最小且不会构成回路权边直至构成一个生成树 - Prim算法
从一个结点的子图开始构造生成树:
选择连接当前子图和子图外结点的最小权边,将相应结点和边加入子图,直至将所有结点加入子图。
构造最小生成树Kruskal算法
Kruskal算法基本思想
- 按所有边权值排序,升序(从小到大)
- 按排好序的边集合,选择一条边加入生成树
贪心准则:不会产生环路
按耗费递增顺序考察每条边
- 若产生环路,丢弃
- 否则,加入
Kruskal算法示例
B = ( 1 1 2 2 3 4 4 5 2 3 3 4 5 5 6 6 1 2 3 5 4 3 2 1 ) B=\begin{pmatrix} 1&&1&&2&&2&&3&&4&&4&&5 \\ 2&&3&&3&&4&&5&&5&&6&&6 \\ 1&&2&&3&&5&&4&&3&&2&&1 \end{pmatrix} B= 121132233245354453462561
按权值排序
B ′ = ( 1 5 1 4 2 4 3 2 2 6 3 6 3 5 5 4 1 1 2 2 3 3 4 5 ) B'=\begin{pmatrix} 1&&5&&1&&4&&2&&4&&3&&2 \\ 2&&6&&3&&6&&3&&5&&5&&4 \\ 1&&1&&2&&2&&3&&3&&4&&5 \end{pmatrix} B′= 121561132462233453354245
加入第一条边
加入第二条边
第三条边
加入46
不能加入23,和45会形成回路
加入35
Kruskal算法的Matlab实现
s = [1 1 2 2 3 4 4 5];
t = [2 3 3 4 5 5 6 6];
weights = [1 2 3 5 4 3 2 1];
G = graph(s, t, weights);
p = plot(G, 'EdgeLabel', G.Edges.Weight);
[T, pred] = minspantree(G);
highlight(p,T)
构造最小生成树Prim算法
贪心准则
- 加入后仍形成树,且耗费最小
- 始终保持树的结构一一Kruskal算法是森林
算法过程
- 从单一顶点的树T开始
- 不断加入耗费最小的边 ( u , v ) (u,v) (u,v),使 T ∪ { ( u , v ) } T\cup \left\{ (u,v) \right\} T∪{(u,v)}仍为树
- u , v u,v u,v中有一个已经在T中,另一个不在T中
Prim算法示例过程
W = ( 0 1 2 ∞ ∞ ∞ 1 0 3 5 ∞ ∞ 2 3 0 ∞ 4 ∞ ∞ 5 ∞ 0 3 2 ∞ ∞ 4 3 0 1 ∞ ∞ ∞ 2 1 0 ) W=\begin{pmatrix} 0&&1&&2&&\infty&&\infty&&\infty \\ 1&&0&&3&&5&&\infty&&\infty \\ 2&&3&&0&&\infty&&4&&\infty \\ \infty&&5&&\infty&&0&&3&&2 \\ \infty&&\infty&&4&&3&&0&&1 \\ \infty&&\infty&&\infty&&2&&1&&0 \end{pmatrix} W= 012∞∞∞1035∞∞230∞4∞∞5∞032∞∞4301∞∞∞210
从v1开始,v2和v3选,选择权值小的那一条边,连接v1v2
从相邻的边开始选,v1v3,v2v3,v2v4中选,选择权值最小的边v1v3
从v2v4和v3v5选择权值小的边,v3v5
再选择v5v6
选择v6v4
Kruskal算法和Prim算法比较
m是边数,n是顶点
最小生成树的应用
制造系统的分组技术
设用 M i M_{i} Mi表示需由机器 i i i加工的零件集,对任意两台机器 i , j i,j i,j,定义相异度
w ( i , j ) = ∣ M i ⊕ M j ∣ M i ∪ M j w(i,j)=\frac{| M_{i}\oplus M_{j}|}{M_{i}\cup M_{j}} w(i,j)=Mi∪Mj∣Mi⊕Mj∣
⊕ \oplus ⊕,对称差
分子:在机器i但不在机器j上加工,或在机器j但不在机器i上加工的零件数
分母:或在机器i,或在机器j上加工的零件数
显然 0 ≤ w ≤ 1 0\le w\le 1 0≤w≤1
构造加权图
以机器为顶点,作一个完全图,每条边 ( i , j ) (i,j) (i,j)被赋予权 w ( i , j ) w(i,j) w(i,j)。
原问题的转化
加权图的最小生成树是由那些相异度最小的边构成的连通图,如果希望把机器分成k个组,就继续删去最小生成树上权最大的k-1条边。于是得到k个分离的子树,每棵树的顶点集就构成各机器组。
对表1给出的数据,加权完全图的边权矩阵如下:
[1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 3 3 3 3 3 3 4 4 4 4 4 5 5 5 5 6 6 6 7 7 8;
2 3 4 5 6 7 8 9 3 4 5 6 7 8 9 4 5 6 7 8 9 5 6 7 8 9 6 7 8 9 7 8 9 8 9 9;
0.5 1 0.89 0.14 1 1 1 1 1 1 0.6 2 1 1 1 1 1 1 1 1 1 0.5 0.87 0.67 0.75 0.75 1 1 1 1 1 1 1 1 0 1 1]
第一行表示每条边的起点,第二行表示每条边的终点,第三行对应每条边的相异度例如第一列1 2 0.5,就表示边12的相异度为0.5,下面我们简单说明一下计算过程:
第1台机器能加工的零件为2, 3, 7, 8, 9, 12, 13
第2台机器能加工的零件为2, 7, 8, 11, 12
两者的并集为2, 3, 7, 8, 9, 11, 12, 13,
两者的交集为2,7,8,12,
则对称差为3, 9, 11, 13,
因此边12的相异度 w ( 1 , 2 ) = w(1,2)= w(1,2)=对称差元素个数/并集元素个数=4/8=0.5
sj=[1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 3 3 3 3 3 3 4 4 4 4 4 5 5 5 5 6 6 6 7 7 8;
2 3 4 5 6 7 8 9 3 4 5 6 7 8 9 4 5 6 7 8 9 5 6 7 8 9 6 7 8 9 7 8 9 8 9 9;
0.5 1 0.89 0.14 1 1 1 1 1 1 0.62 1 1 1 1 1 1 1 1 1 0.5 0.87 0.67 0.75 0.75 1 1 1 1 1 1 1 1 0 1 1];
s = sj(1,:);
t = sj(2,:);
weights = sj(3,:);
G = graph(s, t, weights);
[T, pred] = minspantree(G);
subplot(1, 2, 1);
plot(G, 'EdgeLabel', G.Edges.Weight);
subplot(1, 2, 2);
plot(T, 'EdgeLabel', T.Edges.Weight);
要分为三组,去掉两条最大的边
去掉1和0.87
机器的分组
3,9
1,2,5
4,6,7,8
机器分组的目的是减少零件跨组加工的情况
相异度 = 1,表示两个机器加工的零件是完全不同的,因此不会出现跨机器加工的情况,这两台机器可以分到不同的组。
相异度w = 0,表示两台机器加工零件完全相同,因此应该分到一个组里才能保证不会出现跨组加工现象。
相异度w越小,二者在一组里的可能性越大,因此可以达到我们对机器分组的目的。