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

浅夏110

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

树有下面常用的五个充要条件。
5 k8 D4 b3 Q) m9 G9 w( u7 X2 ~
  ]0 x' v+ A( L定理 1 （i）G 是树当且仅当G 中任二顶点之间有且仅有一条轨道。

* [* W% g! _! t2 U/ K% m  [（ii）G 是树当且仅当G 无圈，且ε =ν −1。

0 [; ~4 v; I, ]+ `（iii）G 是树当且仅当G 连通，且ε =ν −1。
: n1 _5 J7 U; ?" ~! `* L
9 d- j( q+ N: H! g3 G# B（iv）G 是树当且仅当G 连通，且∀e∈ E(G) ，G − e 不连通。

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

2 应用—连线问题
欲修筑连接 n 个城市的铁路，已知i 城与 j 城之间的铁路造价为Cij ，设计一个线 路图，使总造价最低。

5 b# m% o+ o6 ]连线问题的数学模型是在连通赋权图上求权最小的生成树。赋权图的具最小权的生 成树叫做最小生成树。

+ J$ a4 z% x- x. t" K下面介绍构造最小生成树的两种常用算法。

- I7 T5 d7 w' Y: Y2.1 prim 算法构造最小生成树
% |6 r% C" L( _( a3 g. M1 L设置两个集合 P 和Q ,其中 P 用于存放G 的最小生成树中的顶点，集合Q 存放G的最小生成树中的边。令集合 P 的初值为 { P = v1 }（假设构造最小生成树时，从顶点 v1 出发），集合Q 的初值为Q = Φ 。
1 j" e' T) z" k. s+ I# p; H
5 X/ N/ o3 _3 J' m0 h9 _prim 算法的思想是，从所有 p ∈ P ，v ∈V − P 的边 中，选取具有最小权值的边 pv ，将顶点 v 加入集合 P 中，将边 pv 加入集合Q 中，如 此不断重复，直到 P =V 时，最小生成树构造完毕，这时集合Q 中包含了最小生成树 的所有边。


' q' \% z  T; y1 ?7 B* r4 b3 ?0 k
/ {2 s. {2 y  `) i$ m" @例 13         用 prim 算法求图 5 的最小生成树。 我们用  的第一、二、三行分别表示生成树边的起点、终点、权集合。Matlab 程序如下：

5 ?6 I7 R, k, D. E+ G
" }! U- N) X) p( t% ]' gclc;clear;
1 u4 F6 l7 Y" N- i$ t' ha=zeros(7);
4 i/ v, U( ]2 r! v$ B( Za(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;
a=a+a';a(find(a==0))=inf;
result=[];p=1;tb=2:length(a);
while length(result)~=length(a)-1
    temp=a(p,tb);temp=temp(;
( V6 C- T$ `$ k$ b+ r: F    d=min(temp);
    [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
2 X" b- p" j( Y! Cresult
: w; l1 a. w; W" i9 k
$ U' `. Y/ z" V% V' q2.1 Kruskal 算法构造最小生成树
1 B; N) q! ~6 D' q( X3 F科茹斯克尔（Kruskal）算法是一个好算法。Kruskal 算法如下:
6 j% K& m- D  d$ _
* B3 `  R% Q! s) V+ t" }

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

此方法的几何意义是：将序号u 的这个顶点收缩到v 顶点，u 顶点不复存在。后面继续 寻查时，发现某边的两个顶点序号相同时，认为已被收缩掉，失去了被选取的资格。 Matlab 程序如下：

clc;clear;
7 k7 s# {  ]) @! o  [a(1,2)=50; a(1,3)=60; a(2,4)=65; a(2,5)=40;
/ P' x* L* U3 ^; La(3,4)=52;a(3,7)=45; a(4,5)=50; a(4,6)=30;
a(4,7)=42; a(5,6)=70;
5 \2 [0 D/ f- |( n, V[i,j,b]=find(a);
  H% ~  D5 X( W1 Udata=[i';j';b'];index=data(1:2,;
loop=max(size(a))-1;
$ z$ _; _' \1 M. r3 Presult=[];
( T$ M4 M/ ]$ R5 Vwhile length(result)<loop
& g1 }2 Y$ D0 u- s* F- Y5 p1 g9 f    temp=min(data(3,);
6 r9 R; `. c( F0 r) R    flag=find(data(3,==temp);
( u6 s  ^0 ]1 ?& g4 z, _    flag=flag(1);
    v1=data(1,flag);v2=data(2,flag);
! [6 ?1 j, \0 F* ], K1 u3 R    if index(1,flag)~=index(2,flag)
        result=[result,data(:,flag)];
    end
  P  j! o2 C1 r9 l  U- v0 C  G4 m    index(find(index==v2))=v1;
5 v+ {& i' M# s, t    data(:,flag)=[];
    index(:,flag)=[];
% L% g  N4 c! k0 j' ?- r9 dend
result
4 G; p1 @  P, s! W; d4 h
& e: Z" |0 u/ \- b

! D3 v" n% @4 b7 `& s% h————————————————
版权声明：本文为CSDN博主「wamg潇潇」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
) O& N7 |9 A0 ^) ]6 y4 O原文链接：https://blog.csdn.net/qq_29831163/article/details/89785681

1 U/ T4 D4 J# \5 m% f9 j; s# w
) m8 S: t* U5 V