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

浅夏110

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

! L& _/ P7 p# N7 U$ g
树有下面常用的五个充要条件。
$ \$ m1 w* O2 {* u
定理 1 （i）G 是树当且仅当G 中任二顶点之间有且仅有一条轨道。
4 T9 T7 x3 N3 C- |$ q/ l
1 v! u/ H9 L; |7 }% J0 }" I（ii）G 是树当且仅当G 无圈，且ε =ν −1。

' l0 T  e6 P0 i8 `5 T2 v（iii）G 是树当且仅当G 连通，且ε =ν −1。
5 d- m9 r# P. _* q* e. P5 A
（iv）G 是树当且仅当G 连通，且∀e∈ E(G) ，G − e 不连通。
* V) S. ~2 i( g$ c. s! J
（v）G 是树当且仅当G 无圈，∀e∉ E(G) ，G + e 恰有一个圈。

2 应用—连线问题
8 L5 M. |8 m6 m) S: e# o* W 欲修筑连接 n 个城市的铁路，已知i 城与 j 城之间的铁路造价为Cij ，设计一个线 路图，使总造价最低。
1 q, G$ [# @8 c
0 q- [/ n2 Q* P+ v! U连线问题的数学模型是在连通赋权图上求权最小的生成树。赋权图的具最小权的生 成树叫做最小生成树。

下面介绍构造最小生成树的两种常用算法。
: f8 a7 d( y6 L4 D6 j" F+ \8 i
% o* c+ \4 ?  C6 L% R) F2.1 prim 算法构造最小生成树
3 K# {  ^# i+ S# X; w设置两个集合 P 和Q ,其中 P 用于存放G 的最小生成树中的顶点，集合Q 存放G的最小生成树中的边。令集合 P 的初值为 { P = v1 }（假设构造最小生成树时，从顶点 v1 出发），集合Q 的初值为Q = Φ 。

. n; k5 V6 r) E  q' ^+ _prim 算法的思想是，从所有 p ∈ P ，v ∈V − P 的边 中，选取具有最小权值的边 pv ，将顶点 v 加入集合 P 中，将边 pv 加入集合Q 中，如 此不断重复，直到 P =V 时，最小生成树构造完毕，这时集合Q 中包含了最小生成树 的所有边。



. m) {4 Q/ ~" Q0 j! x8 V8 v例 13         用 prim 算法求图 5 的最小生成树。 我们用  的第一、二、三行分别表示生成树边的起点、终点、权集合。Matlab 程序如下：


clc;clear;
a=zeros(7);
a(1,2)=50; a(1,3)=60;
9 b. \1 U- u! \$ g% X; `a(2,4)=65; a(2,5)=40;
; \8 C8 c2 U+ m+ R1 q( e% ^+ Ga(3,4)=52;a(3,7)=45;
/ A' h! V# ?6 n& {. p/ Za(4,5)=50; a(4,6)=30;a(4,7)=42;
a(5,6)=70;
a=a+a';a(find(a==0))=inf;
7 \' j! `( E: \: X& \8 n: V" kresult=[];p=1;tb=2:length(a);
! i2 b/ ?5 B* j+ b- S, G$ cwhile length(result)~=length(a)-1
    temp=a(p,tb);temp=temp(;
    d=min(temp);
& e, J2 F) U( v8 c7 J# y    [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
result

) t4 [  L2 ]6 q( `1 P( ]2.1 Kruskal 算法构造最小生成树
科茹斯克尔（Kruskal）算法是一个好算法。Kruskal 算法如下:


% `. m9 k% i$ P( f2 D! y' S) ^4 `
9 {- N4 [! c8 X" s* n7 l4 ]/ q例 14   用 Kruskal 算法构造例 3 的最小生成树。 我们用 存放各边端点的信息，当选中某一边之后，就将此边对应的顶点序 号中较大序号u 改记为此边的另一序号v ，同时把后面边中所有序号为u 的改记为v 。
3 b5 e4 P. u' a# }
! z6 e: l; W0 J7 s6 q* h' e: G; l此方法的几何意义是：将序号u 的这个顶点收缩到v 顶点，u 顶点不复存在。后面继续 寻查时，发现某边的两个顶点序号相同时，认为已被收缩掉，失去了被选取的资格。 Matlab 程序如下：
: z4 w/ h. Y' {; e$ R
clc;clear;
a(1,2)=50; a(1,3)=60; a(2,4)=65; a(2,5)=40;
+ _2 D4 W0 l# d/ ~a(3,4)=52;a(3,7)=45; a(4,5)=50; a(4,6)=30;
0 ^, C; l7 v: e  K; j) ta(4,7)=42; a(5,6)=70;
[i,j,b]=find(a);
data=[i';j';b'];index=data(1:2,;
loop=max(size(a))-1;
result=[];
while length(result)<loop
    temp=min(data(3,);
    flag=find(data(3,==temp);
1 N6 S5 g: v  F+ K) H' N    flag=flag(1);
    v1=data(1,flag);v2=data(2,flag);
    if index(1,flag)~=index(2,flag)
        result=[result,data(:,flag)];
; u2 X, T  ~# h( r  P* p2 T7 _& l    end
    index(find(index==v2))=v1;
    data(:,flag)=[];
" k. s% Q1 J' q3 x1 D    index(:,flag)=[];
7 ~5 ^) h& y/ x$ W* {end
result
7 o0 [9 o; ^' v) B* a& f0 L( G
& u+ f# V8 {& u2 c
! F3 r1 o( M  G+ o: ]
7 s0 S$ b+ ~% B5 r0 @$ _1 c————————————————
版权声明：本文为CSDN博主「wamg潇潇」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
$ |3 N$ }1 \+ ]$ P0 D. k: i- x原文链接：https://blog.csdn.net/qq_29831163/article/details/89785681

: T: z% ?- O, V, f* C4 o