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

浅夏110

1 基本概念
( R7 {+ X( B8 f: b0 ~: C& }连通的无圈图叫做树，记之为T 。若图G 满足V(G) =V(T ) ， E(T ) ⊂ E(G) ， 则称T 是G 的生成树。图G 连通的充分必要条件为G 有生成树。一个连通图的生成树 的个数很多，用τ (G) 表示G 的生成树的个数，则有公式
8 J' U  U5 x/ Q! v9 |/ I1 H
3 `, A0 R" k3 c4 r
树有下面常用的五个充要条件。

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

& X/ `" L8 i+ p8 U$ z3 r& x（ii）G 是树当且仅当G 无圈，且ε =ν −1。

（iii）G 是树当且仅当G 连通，且ε =ν −1。

（iv）G 是树当且仅当G 连通，且∀e∈ E(G) ，G − e 不连通。

（v）G 是树当且仅当G 无圈，∀e∉ E(G) ，G + e 恰有一个圈。
/ V# C4 m* R) f& |  ^2 h7 ]
2 应用—连线问题
欲修筑连接 n 个城市的铁路，已知i 城与 j 城之间的铁路造价为Cij ，设计一个线 路图，使总造价最低。
9 b$ c7 e, f. t* `* V/ J
/ j( f2 t+ |: z9 L( k5 A连线问题的数学模型是在连通赋权图上求权最小的生成树。赋权图的具最小权的生 成树叫做最小生成树。
1 {$ s3 y# h4 ]+ {3 q$ d
下面介绍构造最小生成树的两种常用算法。
, o* ^# H  y5 A5 X
+ @6 {% M1 w3 r# |" o2.1 prim 算法构造最小生成树
: v2 x1 P8 {# w, S* x9 ~$ q* I设置两个集合 P 和Q ,其中 P 用于存放G 的最小生成树中的顶点，集合Q 存放G的最小生成树中的边。令集合 P 的初值为 { P = v1 }（假设构造最小生成树时，从顶点 v1 出发），集合Q 的初值为Q = Φ 。
% Q! D& J7 Y2 C1 U% \: J, C
6 \# J, x9 r* o7 cprim 算法的思想是，从所有 p ∈ P ，v ∈V − P 的边 中，选取具有最小权值的边 pv ，将顶点 v 加入集合 P 中，将边 pv 加入集合Q 中，如 此不断重复，直到 P =V 时，最小生成树构造完毕，这时集合Q 中包含了最小生成树 的所有边。

' i1 I8 S5 w. _) z# Q: C

例 13         用 prim 算法求图 5 的最小生成树。 我们用  的第一、二、三行分别表示生成树边的起点、终点、权集合。Matlab 程序如下：
/ I9 L$ g, H2 }5 _* w

; Q) Q, [* I8 |  gclc;clear;
a=zeros(7);
0 ]3 P2 F) F' @& e/ [" ca(1,2)=50; a(1,3)=60;
, r% `' H0 I" Qa(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;
& ~# M& W0 u) {  x( p3 Ma(5,6)=70;
a=a+a';a(find(a==0))=inf;
3 R" _' o; g2 z9 z9 lresult=[];p=1;tb=2:length(a);
# ~9 t1 W/ j8 v' B- i' r; v* }while length(result)~=length(a)-1
, T8 Z+ G* h, e/ v3 R, i    temp=a(p,tb);temp=temp(;
5 ~  u- t& l0 E/ g) P& y6 @    d=min(temp);
+ ?+ V4 j& n, W$ y    [jb,kb]=find(a(p,tb)==d);
    j=p(jb(1));k=tb(kb(1));
4 r* G( I% W( a$ g9 o0 C" K    result=[result,[j;k;d]];p=[p,k];tb(find(tb==k))=[];
+ _/ g1 t" o2 [7 w7 D- e* }end
result

2.1 Kruskal 算法构造最小生成树
科茹斯克尔（Kruskal）算法是一个好算法。Kruskal 算法如下:

/ Q9 u0 N+ R+ M$ Y

+ M: X6 ^: \( _$ _例 14   用 Kruskal 算法构造例 3 的最小生成树。 我们用 存放各边端点的信息，当选中某一边之后，就将此边对应的顶点序 号中较大序号u 改记为此边的另一序号v ，同时把后面边中所有序号为u 的改记为v 。
$ f4 y" }7 c; ?6 X2 Z3 t& ~4 L
7 L& w5 R: O2 j8 ]. ^1 K此方法的几何意义是：将序号u 的这个顶点收缩到v 顶点，u 顶点不复存在。后面继续 寻查时，发现某边的两个顶点序号相同时，认为已被收缩掉，失去了被选取的资格。 Matlab 程序如下：

1 e, h& \) e! m8 N4 _clc;clear;
( A; Z1 {- y% `9 A+ |8 ^; ua(1,2)=50; a(1,3)=60; a(2,4)=65; a(2,5)=40;
( V$ z3 C; t! Q/ Ra(3,4)=52;a(3,7)=45; a(4,5)=50; a(4,6)=30;
' k0 L' Q7 B& L, f8 fa(4,7)=42; a(5,6)=70;
[i,j,b]=find(a);
# |) Y$ b- z4 idata=[i';j';b'];index=data(1:2,;
/ H9 Y- P- z& ^# Jloop=max(size(a))-1;
5 r% q. Y* K- x/ e# }- k( rresult=[];
% o+ s1 B1 q* }while length(result)<loop
- A" g* f# I9 @7 a3 t3 I    temp=min(data(3,);
0 T3 J5 R/ ]) D, U5 X* Z( n! h2 r% t/ x6 e    flag=find(data(3,==temp);
    flag=flag(1);
    v1=data(1,flag);v2=data(2,flag);
    if index(1,flag)~=index(2,flag)
3 W. v2 L4 G! j3 E        result=[result,data(:,flag)];
    end
    index(find(index==v2))=v1;
# R6 ?1 ]9 }0 D7 x# ~' N4 V5 Z: b2 ^    data(:,flag)=[];
    index(:,flag)=[];
end
result
  {& _: ~. ]+ V* B
5 w& I8 ?) z; S) S: K7 _
6 e( N' h, X8 m/ z' r/ j" w% _1 D
$ p  J; N8 L5 v! \/ Z1 _& C————————————————
版权声明：本文为CSDN博主「wamg潇潇」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_29831163/article/details/89785681


1 C2 {" w9 F& q7 ?; Y