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

浅夏110

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

4 k$ j( ?+ W# Q$ n
树有下面常用的五个充要条件。

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

（ii）G 是树当且仅当G 无圈，且ε =ν −1。
" L# ^5 X/ @% |% t4 |
% e1 Q1 W7 N. Y" W（iii）G 是树当且仅当G 连通，且ε =ν −1。

! m% g0 H7 v+ a（iv）G 是树当且仅当G 连通，且∀e∈ E(G) ，G − e 不连通。

（v）G 是树当且仅当G 无圈，∀e∉ E(G) ，G + e 恰有一个圈。

4 I- o/ K9 L- h0 y4 C6 D, h2 应用—连线问题
) K. X0 @1 {& `* m8 S 欲修筑连接 n 个城市的铁路，已知i 城与 j 城之间的铁路造价为Cij ，设计一个线 路图，使总造价最低。
  x: W( S! W, [8 e7 T
( N0 T( b2 `/ L( ?9 D& z$ h连线问题的数学模型是在连通赋权图上求权最小的生成树。赋权图的具最小权的生 成树叫做最小生成树。

下面介绍构造最小生成树的两种常用算法。
4 H1 w% z+ F) Y$ o0 g# u# w
# E' d& @( @" V4 y! _: W2.1 prim 算法构造最小生成树
- T: {! N" T+ y( E设置两个集合 P 和Q ,其中 P 用于存放G 的最小生成树中的顶点，集合Q 存放G的最小生成树中的边。令集合 P 的初值为 { P = v1 }（假设构造最小生成树时，从顶点 v1 出发），集合Q 的初值为Q = Φ 。
* x/ e0 v: C4 y! i) d  F% W
prim 算法的思想是，从所有 p ∈ P ，v ∈V − P 的边 中，选取具有最小权值的边 pv ，将顶点 v 加入集合 P 中，将边 pv 加入集合Q 中，如 此不断重复，直到 P =V 时，最小生成树构造完毕，这时集合Q 中包含了最小生成树 的所有边。

- R: U. }% d1 A- I' n2 `; U6 n
, y( y9 e. b& z, j. A4 U
3 k- q& p$ E' D例 13         用 prim 算法求图 5 的最小生成树。 我们用  的第一、二、三行分别表示生成树边的起点、终点、权集合。Matlab 程序如下：
+ h- z8 s) }6 C9 H

5 t+ M6 R! |/ D* x/ H, `clc;clear;
a=zeros(7);
a(1,2)=50; a(1,3)=60;
8 \4 t0 y( q( ?" d; ?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;
$ l0 C& X9 ^( F1 P1 `, n( ka(5,6)=70;
a=a+a';a(find(a==0))=inf;
2 _" @) ?- p$ c+ ?  h/ G, ]5 Z, Mresult=[];p=1;tb=2:length(a);
while length(result)~=length(a)-1
    temp=a(p,tb);temp=temp(;
    d=min(temp);
3 z# l# e7 c9 r3 x( X- H% a2 M    [jb,kb]=find(a(p,tb)==d);
& E: K' G: G5 n( j$ L    j=p(jb(1));k=tb(kb(1));
    result=[result,[j;k;d]];p=[p,k];tb(find(tb==k))=[];
end
- K. L9 i6 S* x, _% dresult

2.1 Kruskal 算法构造最小生成树
8 n! h' g1 W" x5 V$ N2 A  C; g4 l1 l科茹斯克尔（Kruskal）算法是一个好算法。Kruskal 算法如下:
4 [4 P8 d- e! U7 `2 W7 T

0 ]! T7 r+ Q/ _: s$ L5 h
1 g/ G: ]5 X2 j* F例 14   用 Kruskal 算法构造例 3 的最小生成树。 我们用 存放各边端点的信息，当选中某一边之后，就将此边对应的顶点序 号中较大序号u 改记为此边的另一序号v ，同时把后面边中所有序号为u 的改记为v 。

: c6 j8 v# O7 w9 ~: z此方法的几何意义是：将序号u 的这个顶点收缩到v 顶点，u 顶点不复存在。后面继续 寻查时，发现某边的两个顶点序号相同时，认为已被收缩掉，失去了被选取的资格。 Matlab 程序如下：
& Z# `8 i9 _: r
clc;clear;
a(1,2)=50; a(1,3)=60; a(2,4)=65; a(2,5)=40;
6 W- H2 k+ `4 ^' T, ca(3,4)=52;a(3,7)=45; a(4,5)=50; a(4,6)=30;
* d* R4 l% K5 M2 qa(4,7)=42; a(5,6)=70;
6 L2 C$ \0 W5 b3 e% Z0 w[i,j,b]=find(a);
3 J4 D$ k' z8 e$ s1 z& p- wdata=[i';j';b'];index=data(1:2,;
  `' w/ W. g5 O+ E1 sloop=max(size(a))-1;
result=[];
1 a) v) r1 E7 H) B1 U9 r+ ?0 xwhile length(result)<loop
# u6 m. d, E1 N4 E1 f; H* d+ _% k    temp=min(data(3,);
0 O$ s  S6 U* K9 _    flag=find(data(3,==temp);
    flag=flag(1);
" u' g* S5 H9 E" U' [5 b0 u    v1=data(1,flag);v2=data(2,flag);
    if index(1,flag)~=index(2,flag)
        result=[result,data(:,flag)];
# W$ Y& a$ f$ l    end
    index(find(index==v2))=v1;
    data(:,flag)=[];
    index(:,flag)=[];
end
result
. `2 S$ X0 B: Q


————————————————
1 a" |8 A* o5 J4 n# W* ~版权声明：本文为CSDN博主「wamg潇潇」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
& [" I3 S  w* d/ E& S9 q原文链接：https://blog.csdn.net/qq_29831163/article/details/89785681

: _7 s8 z0 w, _4 _; ^/ |. ]
; p; B7 m9 H6 A# v8 t0 e