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

浅夏110

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

树有下面常用的五个充要条件。
: u( ~% A6 `' x, R
定理 1 （i）G 是树当且仅当G 中任二顶点之间有且仅有一条轨道。

3 k& Q6 ^- v; y' D（ii）G 是树当且仅当G 无圈，且ε =ν −1。
) a3 c% ^4 f* u: j( [
# {' ]; c/ u5 g8 k) O7 M) Z4 r（iii）G 是树当且仅当G 连通，且ε =ν −1。

（iv）G 是树当且仅当G 连通，且∀e∈ E(G) ，G − e 不连通。
) p# D5 U8 y# @2 }7 l' a: r4 X
（v）G 是树当且仅当G 无圈，∀e∉ E(G) ，G + e 恰有一个圈。

2 应用—连线问题
3 S* t" j. m8 k" X+ {: c4 R. h- h 欲修筑连接 n 个城市的铁路，已知i 城与 j 城之间的铁路造价为Cij ，设计一个线 路图，使总造价最低。
9 o% |6 @5 V" ^% q
连线问题的数学模型是在连通赋权图上求权最小的生成树。赋权图的具最小权的生 成树叫做最小生成树。
9 O5 K: W8 ?7 e8 R0 G  D0 t  g, `
下面介绍构造最小生成树的两种常用算法。

2.1 prim 算法构造最小生成树
, k( t8 w3 E3 V+ [设置两个集合 P 和Q ,其中 P 用于存放G 的最小生成树中的顶点，集合Q 存放G的最小生成树中的边。令集合 P 的初值为 { P = v1 }（假设构造最小生成树时，从顶点 v1 出发），集合Q 的初值为Q = Φ 。

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


, H. Y8 l! w7 G: s0 M( B5 h3 G
例 13         用 prim 算法求图 5 的最小生成树。 我们用  的第一、二、三行分别表示生成树边的起点、终点、权集合。Matlab 程序如下：
# q; z, W; F7 Y+ R: d# b
8 I- L8 I$ ~  g. o5 Q
* H. G* _4 l" g! v1 A/ x( ]8 D6 H: ^clc;clear;
. v; u; |2 i1 V8 l1 R3 }a=zeros(7);
1 _9 G: e6 x1 E* h+ U. s; m  Wa(1,2)=50; a(1,3)=60;
a(2,4)=65; a(2,5)=40;
$ A$ j7 [/ U- T4 oa(3,4)=52;a(3,7)=45;
a(4,5)=50; a(4,6)=30;a(4,7)=42;
5 T4 [* F# v, ~# |+ o7 K, Z. Xa(5,6)=70;
( H% y! n# {3 d6 h' L9 Y  Ma=a+a';a(find(a==0))=inf;
5 C5 \; ]6 P: [5 z  S' zresult=[];p=1;tb=2:length(a);
while length(result)~=length(a)-1
  ?, Z! t9 m$ A    temp=a(p,tb);temp=temp(;
! s5 ]1 p: A# p9 a4 v7 C+ x# F* ^# \    d=min(temp);
    [jb,kb]=find(a(p,tb)==d);
    j=p(jb(1));k=tb(kb(1));
$ j" |8 Z% j* z- k5 w( A9 x. Q    result=[result,[j;k;d]];p=[p,k];tb(find(tb==k))=[];
8 Z  M6 W% ^/ D* c! `0 K  Y1 uend
result
" |4 f2 O4 i/ J( M4 f+ H
2.1 Kruskal 算法构造最小生成树
科茹斯克尔（Kruskal）算法是一个好算法。Kruskal 算法如下:

; [  k# B9 r+ X6 \8 j  L! B5 ?5 u: k

2 b4 x8 m3 y+ {+ x6 ?1 L' ?3 T6 U例 14   用 Kruskal 算法构造例 3 的最小生成树。 我们用 存放各边端点的信息，当选中某一边之后，就将此边对应的顶点序 号中较大序号u 改记为此边的另一序号v ，同时把后面边中所有序号为u 的改记为v 。
! {' J  ]& ^7 ?
, i9 J( y. ^# V- `9 Y2 c此方法的几何意义是：将序号u 的这个顶点收缩到v 顶点，u 顶点不复存在。后面继续 寻查时，发现某边的两个顶点序号相同时，认为已被收缩掉，失去了被选取的资格。 Matlab 程序如下：
' E3 f9 m$ P3 m
clc;clear;
a(1,2)=50; a(1,3)=60; a(2,4)=65; a(2,5)=40;
* B: g% [: @5 p) N$ c3 ^a(3,4)=52;a(3,7)=45; a(4,5)=50; a(4,6)=30;
  _# Q9 B3 P' |$ k/ Pa(4,7)=42; a(5,6)=70;
# }6 R7 h! h0 a; X" z" M[i,j,b]=find(a);
data=[i';j';b'];index=data(1:2,;
loop=max(size(a))-1;
result=[];
while length(result)<loop
1 J0 v( H7 s, G8 K    temp=min(data(3,);
0 K+ B7 l2 d- s: i    flag=find(data(3,==temp);
    flag=flag(1);
/ X9 Q1 Y& s2 `, l; c    v1=data(1,flag);v2=data(2,flag);
    if index(1,flag)~=index(2,flag)
        result=[result,data(:,flag)];
) g! s; S4 `. D/ F    end
    index(find(index==v2))=v1;
1 n' g. S' K! `  \    data(:,flag)=[];
    index(:,flag)=[];
end
7 z/ D2 h+ e' presult
5 s: H- Z$ y  [  _7 \# Z

! h& y/ n! {, y( V4 p1 Z6 T2 I
————————————————
3 r7 j4 n' C; Z$ |& t. T版权声明：本文为CSDN博主「wamg潇潇」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_29831163/article/details/89785681


( H- m! w& Q, N5 Z0 `