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

浅夏110

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


树有下面常用的五个充要条件。

定理 1 （i）G 是树当且仅当G 中任二顶点之间有且仅有一条轨道。

% \% L0 H# I. K$ i" j0 }3 B* N$ ]（ii）G 是树当且仅当G 无圈，且ε =ν −1。
' u; _# O3 M# V% s. H
（iii）G 是树当且仅当G 连通，且ε =ν −1。
* |! m9 [/ W" f* R% `& _( F
（iv）G 是树当且仅当G 连通，且∀e∈ E(G) ，G − e 不连通。
, f' E8 `# y0 G; M" R
（v）G 是树当且仅当G 无圈，∀e∉ E(G) ，G + e 恰有一个圈。
  O! W3 a4 ?; O
1 X0 M& ~6 Y* M; f2 应用—连线问题
6 r/ |; ]1 d& \ 欲修筑连接 n 个城市的铁路，已知i 城与 j 城之间的铁路造价为Cij ，设计一个线 路图，使总造价最低。

8 y/ y& U0 w$ E9 Y连线问题的数学模型是在连通赋权图上求权最小的生成树。赋权图的具最小权的生 成树叫做最小生成树。

5 T$ F4 @9 J' s下面介绍构造最小生成树的两种常用算法。
( q& {- e. l: Y2 h( U" I! k5 N: v
2.1 prim 算法构造最小生成树
设置两个集合 P 和Q ,其中 P 用于存放G 的最小生成树中的顶点，集合Q 存放G的最小生成树中的边。令集合 P 的初值为 { P = v1 }（假设构造最小生成树时，从顶点 v1 出发），集合Q 的初值为Q = Φ 。
% y2 e. U& Y# a( G
prim 算法的思想是，从所有 p ∈ P ，v ∈V − P 的边 中，选取具有最小权值的边 pv ，将顶点 v 加入集合 P 中，将边 pv 加入集合Q 中，如 此不断重复，直到 P =V 时，最小生成树构造完毕，这时集合Q 中包含了最小生成树 的所有边。

# C9 O+ K( @3 P$ Z' g: T
2 s% i+ q8 n0 t  l; c6 S: \7 O
例 13         用 prim 算法求图 5 的最小生成树。 我们用  的第一、二、三行分别表示生成树边的起点、终点、权集合。Matlab 程序如下：


clc;clear;
) ^2 |& y/ w- y6 da=zeros(7);
a(1,2)=50; a(1,3)=60;
+ y; z# x4 _% D- d4 W) ja(2,4)=65; a(2,5)=40;
, u" J* y. L  @" Q" q: Xa(3,4)=52;a(3,7)=45;
a(4,5)=50; a(4,6)=30;a(4,7)=42;
a(5,6)=70;
$ _+ n" C7 M6 ?) Aa=a+a';a(find(a==0))=inf;
result=[];p=1;tb=2:length(a);
9 e2 x/ a' V, k" v1 w# twhile length(result)~=length(a)-1
0 U8 d9 m  ~2 z, E' M( K* q    temp=a(p,tb);temp=temp(;
    d=min(temp);
6 s, G3 P  ]7 c0 ^# G4 W    [jb,kb]=find(a(p,tb)==d);
    j=p(jb(1));k=tb(kb(1));
) K  ^0 C/ E/ O2 N% t    result=[result,[j;k;d]];p=[p,k];tb(find(tb==k))=[];
end
$ A( u8 @7 L9 vresult
% I, o' C# e# u# [5 l; r
2.1 Kruskal 算法构造最小生成树
科茹斯克尔（Kruskal）算法是一个好算法。Kruskal 算法如下:
( W. z! z7 D4 Q
: Z8 _/ J/ Y' x  G7 j8 E

例 14   用 Kruskal 算法构造例 3 的最小生成树。 我们用 存放各边端点的信息，当选中某一边之后，就将此边对应的顶点序 号中较大序号u 改记为此边的另一序号v ，同时把后面边中所有序号为u 的改记为v 。
$ q7 \" R* e7 [
( G  a# I8 @! o此方法的几何意义是：将序号u 的这个顶点收缩到v 顶点，u 顶点不复存在。后面继续 寻查时，发现某边的两个顶点序号相同时，认为已被收缩掉，失去了被选取的资格。 Matlab 程序如下：

clc;clear;
a(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);
data=[i';j';b'];index=data(1:2,;
+ b! n, |- D, m! S1 @. j- `loop=max(size(a))-1;
6 c4 {4 q! b# ]8 G$ [/ q) lresult=[];
; P% }, j# n. j7 ~while length(result)<loop
    temp=min(data(3,);
    flag=find(data(3,==temp);
; ?7 K3 m7 j7 X9 z2 Q    flag=flag(1);
* p, W+ t6 s9 T; Y# A3 O5 |* u    v1=data(1,flag);v2=data(2,flag);
    if index(1,flag)~=index(2,flag)
5 ^8 F! a3 y& V0 G  T1 A) {$ b* l& E9 k$ K        result=[result,data(:,flag)];
/ l: S/ f7 I, y) v- b6 l    end
    index(find(index==v2))=v1;
    data(:,flag)=[];
. F4 f+ A* I4 l/ M$ w' ^, [    index(:,flag)=[];
9 z8 I+ E" q; M8 _+ P9 y# t/ U; g: }end
% f6 g  k; b7 N) j9 t$ aresult
6 e, F$ y* Y: J% I+ n


0 H) ^- E: c  a0 A( X8 m. J————————————————
版权声明：本文为CSDN博主「wamg潇潇」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_29831163/article/details/89785681
6 R% b) S2 Y8 }1 o& c1 g  T
) @& N3 \7 J8 R0 v