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

浅夏110

1 基本概念
连通的无圈图叫做树，记之为T 。若图G 满足V(G) =V(T ) ， E(T ) ⊂ E(G) ， 则称T 是G 的生成树。图G 连通的充分必要条件为G 有生成树。一个连通图的生成树 的个数很多，用τ (G) 表示G 的生成树的个数，则有公式
1 a: ^7 H- ^5 Z$ }/ i- S
4 \, j4 s: A0 R, k* ^8 g
( a; n1 [1 l, t3 p- l$ [8 H; @树有下面常用的五个充要条件。
2 I2 S, u& R7 {+ H% y9 q" N
6 |" n. t! @6 q  E9 \定理 1 （i）G 是树当且仅当G 中任二顶点之间有且仅有一条轨道。
% |: U0 h( F) e8 n
( f9 Z2 W% z, Q, o# I: o6 f/ c. v1 W  R（ii）G 是树当且仅当G 无圈，且ε =ν −1。

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

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

% ^2 }. d) H- [8 ~$ ?* E' u4 ^（v）G 是树当且仅当G 无圈，∀e∉ E(G) ，G + e 恰有一个圈。
2 }+ _4 u* Z! B* l
3 V- \- u. Z  i2 应用—连线问题
欲修筑连接 n 个城市的铁路，已知i 城与 j 城之间的铁路造价为Cij ，设计一个线 路图，使总造价最低。
2 a: w$ r  P9 d3 z! y7 y* h% t
连线问题的数学模型是在连通赋权图上求权最小的生成树。赋权图的具最小权的生 成树叫做最小生成树。
" L7 E( T! @  S+ F' W2 i
下面介绍构造最小生成树的两种常用算法。
5 j: {' N* @6 x9 C! |; t, {
2.1 prim 算法构造最小生成树
% {' s3 z5 H$ g1 [( q+ l设置两个集合 P 和Q ,其中 P 用于存放G 的最小生成树中的顶点，集合Q 存放G的最小生成树中的边。令集合 P 的初值为 { P = v1 }（假设构造最小生成树时，从顶点 v1 出发），集合Q 的初值为Q = Φ 。
9 @/ u) c2 v6 G: [1 B9 @$ C
" H$ u: a1 ~  xprim 算法的思想是，从所有 p ∈ P ，v ∈V − P 的边 中，选取具有最小权值的边 pv ，将顶点 v 加入集合 P 中，将边 pv 加入集合Q 中，如 此不断重复，直到 P =V 时，最小生成树构造完毕，这时集合Q 中包含了最小生成树 的所有边。
* R/ E9 D% i: Y  {" a1 M% H1 }

: X  K* s# m$ F1 C' R+ V
例 13         用 prim 算法求图 5 的最小生成树。 我们用  的第一、二、三行分别表示生成树边的起点、终点、权集合。Matlab 程序如下：
# M, L) y" s) B4 B
+ w: K/ X1 J$ S2 E' @9 s) Z: ^  |
4 q8 l/ Q8 ^/ E0 ?& N; p3 {clc;clear;
: Z& o1 M% u0 O, }6 c- ma=zeros(7);
% M* V, n) D4 A( O5 D' f# x) Ta(1,2)=50; a(1,3)=60;
1 A7 y  T' r" B/ P% A9 ia(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) l+ B, t% `0 n5 [a(5,6)=70;
a=a+a';a(find(a==0))=inf;
2 r9 {- m+ }+ \+ A3 B* u" \result=[];p=1;tb=2:length(a);
while length(result)~=length(a)-1
    temp=a(p,tb);temp=temp(;
    d=min(temp);
; T& J. Q8 R/ S7 v9 H; u    [jb,kb]=find(a(p,tb)==d);
2 u# I. \& j; q+ {    j=p(jb(1));k=tb(kb(1));
    result=[result,[j;k;d]];p=[p,k];tb(find(tb==k))=[];
: F3 F% A8 c) E$ S: xend
result

/ B. {8 s0 E: U! d2.1 Kruskal 算法构造最小生成树
! n7 \, C) @# E. l6 T% \' @- j科茹斯克尔（Kruskal）算法是一个好算法。Kruskal 算法如下:


& o; B; J6 A  Y
5 z  x6 F1 L2 x! g例 14   用 Kruskal 算法构造例 3 的最小生成树。 我们用 存放各边端点的信息，当选中某一边之后，就将此边对应的顶点序 号中较大序号u 改记为此边的另一序号v ，同时把后面边中所有序号为u 的改记为v 。

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

- q7 S; V3 i& V* S% Nclc;clear;
4 N2 [+ a3 S% B1 v+ E0 C) s+ U6 Ua(1,2)=50; a(1,3)=60; a(2,4)=65; a(2,5)=40;
) ~- }* o; K3 W6 da(3,4)=52;a(3,7)=45; a(4,5)=50; a(4,6)=30;
a(4,7)=42; a(5,6)=70;
[i,j,b]=find(a);
+ [% M) L. ]* @" l5 C$ xdata=[i';j';b'];index=data(1:2,;
loop=max(size(a))-1;
result=[];
while length(result)<loop
    temp=min(data(3,);
. @- ~9 J  H0 a/ S4 }- h    flag=find(data(3,==temp);
& f3 z# u: Z0 L" B8 b- @$ b1 B" T    flag=flag(1);
  x1 i0 V# @4 L  `& u    v1=data(1,flag);v2=data(2,flag);
* t5 q5 ^3 X; A: Z    if index(1,flag)~=index(2,flag)
        result=[result,data(:,flag)];
    end
    index(find(index==v2))=v1;
4 l- e; w$ @& d, b- u* h    data(:,flag)=[];
    index(:,flag)=[];
end
* U5 T4 K' S" @7 J/ Tresult



————————————————
版权声明：本文为CSDN博主「wamg潇潇」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
- V/ P- z& i; y% h7 x; D. w原文链接：https://blog.csdn.net/qq_29831163/article/details/89785681
" o1 ?4 a6 W4 D7 e) m

' a( G; Y: }0 V0 X