常用模型&算法总结—图&网络模型应用—树：连通性、最小生成树

浅夏110

1 基本概念
连通的无圈图叫做树，记之为T 。若图G 满足V(G) =V(T ) ， E(T ) ⊂ E(G) ， 则称T 是G 的生成树。图G 连通的充分必要条件为G 有生成树。一个连通图的生成树 的个数很多，用τ (G) 表示G 的生成树的个数，则有公式


8 J3 _* f+ A+ Z, R" I# ~树有下面常用的五个充要条件。
, t' T' c3 {; Q5 B  |8 w" @  H) x
7 h/ L% L" ~% j6 X定理 1 （i）G 是树当且仅当G 中任二顶点之间有且仅有一条轨道。
. |3 B6 |* {9 L5 c
（ii）G 是树当且仅当G 无圈，且ε =ν −1。

; |2 V- p0 B3 ~/ L* J/ a（iii）G 是树当且仅当G 连通，且ε =ν −1。
- W; A9 O7 {+ h: w1 L+ @
% y* H# H0 j5 y$ R（iv）G 是树当且仅当G 连通，且∀e∈ E(G) ，G − e 不连通。

（v）G 是树当且仅当G 无圈，∀e∉ E(G) ，G + e 恰有一个圈。
" R. }: g* k0 u3 `
2 应用—连线问题
) D$ X& L, T, O; }8 C( T( @$ | 欲修筑连接 n 个城市的铁路，已知i 城与 j 城之间的铁路造价为Cij ，设计一个线 路图，使总造价最低。

连线问题的数学模型是在连通赋权图上求权最小的生成树。赋权图的具最小权的生 成树叫做最小生成树。
! s8 A9 W, W# }# h. Q/ F" ^7 T
: P' i4 E4 w  @: a& i( |下面介绍构造最小生成树的两种常用算法。
. k& k  l% Z- E2 z
% A0 f) K4 r- ~6 |  W( b# U2.1 prim 算法构造最小生成树
设置两个集合 P 和Q ,其中 P 用于存放G 的最小生成树中的顶点，集合Q 存放G的最小生成树中的边。令集合 P 的初值为 { P = v1 }（假设构造最小生成树时，从顶点 v1 出发），集合Q 的初值为Q = Φ 。
1 H2 O0 K/ W+ |: k7 p
prim 算法的思想是，从所有 p ∈ P ，v ∈V − P 的边 中，选取具有最小权值的边 pv ，将顶点 v 加入集合 P 中，将边 pv 加入集合Q 中，如 此不断重复，直到 P =V 时，最小生成树构造完毕，这时集合Q 中包含了最小生成树 的所有边。

  U7 T% v1 k. u9 ^
3 u2 c; W7 w, ], f2 e
例 13         用 prim 算法求图 5 的最小生成树。 我们用  的第一、二、三行分别表示生成树边的起点、终点、权集合。Matlab 程序如下：
& Q" E; z& O+ q

* X5 {9 b2 ~9 _  _! g, Jclc;clear;
. L; n! s4 V* A$ P  T2 `( s  ma=zeros(7);
1 `0 A6 O2 ?; ]$ R& Wa(1,2)=50; a(1,3)=60;
* x2 J  `. M5 \  y- c6 Za(2,4)=65; a(2,5)=40;
a(3,4)=52;a(3,7)=45;
a(4,5)=50; a(4,6)=30;a(4,7)=42;
/ u5 Q7 m' t4 }! [% Wa(5,6)=70;
a=a+a';a(find(a==0))=inf;
result=[];p=1;tb=2:length(a);
while length(result)~=length(a)-1
4 p$ w' V7 w) i' h5 T4 n$ v; s% B: Q    temp=a(p,tb);temp=temp(;
    d=min(temp);
: v) A, p, ?0 B    [jb,kb]=find(a(p,tb)==d);
    j=p(jb(1));k=tb(kb(1));
    result=[result,[j;k;d]];p=[p,k];tb(find(tb==k))=[];
end
, h8 e& p5 C& @6 yresult
( K7 K+ W. T2 e7 s& J% M
9 x2 l) y5 D0 ~; @* }- q2.1 Kruskal 算法构造最小生成树
科茹斯克尔（Kruskal）算法是一个好算法。Kruskal 算法如下:
! o7 Q, i* T5 E& L0 V4 n3 Y


; B3 o! P7 y4 o0 C; d例 14   用 Kruskal 算法构造例 3 的最小生成树。 我们用 存放各边端点的信息，当选中某一边之后，就将此边对应的顶点序 号中较大序号u 改记为此边的另一序号v ，同时把后面边中所有序号为u 的改记为v 。

* V1 a' g" O# ]$ ]! s$ \此方法的几何意义是：将序号u 的这个顶点收缩到v 顶点，u 顶点不复存在。后面继续 寻查时，发现某边的两个顶点序号相同时，认为已被收缩掉，失去了被选取的资格。 Matlab 程序如下：
0 Z/ j( }+ m# N0 K0 F3 }4 o( T
( ~: }/ O, R, F$ A' P6 Eclc;clear;
% Y' d0 \0 a% R9 n8 ~, @: La(1,2)=50; a(1,3)=60; a(2,4)=65; a(2,5)=40;
a(3,4)=52;a(3,7)=45; a(4,5)=50; a(4,6)=30;
a(4,7)=42; a(5,6)=70;
[i,j,b]=find(a);
+ c5 q5 Y& M( I& n, O$ Y1 t# t* @data=[i';j';b'];index=data(1:2,;
5 f- ~! M: R0 i# x; [! w" floop=max(size(a))-1;
result=[];
while length(result)<loop
; E# x+ _- ?/ A* ^5 k' F    temp=min(data(3,);
    flag=find(data(3,==temp);
: O6 D2 s. |' Z9 A1 I    flag=flag(1);
" Q9 I  _6 k* }0 Q9 p. _- X2 T    v1=data(1,flag);v2=data(2,flag);
+ C  z0 V* S2 e3 l; W. P; V    if index(1,flag)~=index(2,flag)
# c( D* H) p2 o  F4 K7 x        result=[result,data(:,flag)];
# S. e5 D2 H5 j$ Z) ^5 k5 E    end
4 B8 W/ f9 {3 k! [: z    index(find(index==v2))=v1;
    data(:,flag)=[];
8 z. Y( O- {. E6 m    index(:,flag)=[];
end
- ~8 F+ e0 n1 ~4 P7 L/ h& zresult
; e& i3 d+ S' e& H; v2 Y
' p$ ^$ {% S$ D' x
" b" |" _: G6 p: M# n+ J' y  A5 H
- _# p4 E, Z- H. [9 ]5 c————————————————
2 G# I9 y: r$ {9 i* C7 |版权声明：本文为CSDN博主「wamg潇潇」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
" {3 d- }- d. _" L, N原文链接：https://blog.csdn.net/qq_29831163/article/details/89785681
6 l: ~( W: V( ^! Z: [6 q+ W" \5 l

  G2 O  x7 V9 b( @7 a