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

浅夏110

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

8 W0 Y, y7 C7 k, h树有下面常用的五个充要条件。

定理 1 （i）G 是树当且仅当G 中任二顶点之间有且仅有一条轨道。
, ^) L  R5 d) C/ k- v: S
. m5 p/ H  L, a; P  d6 W（ii）G 是树当且仅当G 无圈，且ε =ν −1。
- A1 ^: _3 o9 B0 H2 v) U$ w
（iii）G 是树当且仅当G 连通，且ε =ν −1。

% ~: _5 ]% l" z  C（iv）G 是树当且仅当G 连通，且∀e∈ E(G) ，G − e 不连通。
) K, W8 d" f7 s2 W/ H, U
7 k, ]! \. H4 K$ C（v）G 是树当且仅当G 无圈，∀e∉ E(G) ，G + e 恰有一个圈。
( ]4 N1 q7 z, ^" ~* R
2 ^0 `% `3 [- I, G+ p* h8 G* B( L2 应用—连线问题
欲修筑连接 n 个城市的铁路，已知i 城与 j 城之间的铁路造价为Cij ，设计一个线 路图，使总造价最低。

: A4 O, r" ]4 J! d8 B连线问题的数学模型是在连通赋权图上求权最小的生成树。赋权图的具最小权的生 成树叫做最小生成树。
: j0 s0 x" J2 {) z3 U* X$ d( d) q
; W' a' q' s2 {% F; x下面介绍构造最小生成树的两种常用算法。

) m1 j4 k0 K! p" J, g2.1 prim 算法构造最小生成树
设置两个集合 P 和Q ,其中 P 用于存放G 的最小生成树中的顶点，集合Q 存放G的最小生成树中的边。令集合 P 的初值为 { P = v1 }（假设构造最小生成树时，从顶点 v1 出发），集合Q 的初值为Q = Φ 。
+ j; t4 A. C  K; L+ Q
prim 算法的思想是，从所有 p ∈ P ，v ∈V − P 的边 中，选取具有最小权值的边 pv ，将顶点 v 加入集合 P 中，将边 pv 加入集合Q 中，如 此不断重复，直到 P =V 时，最小生成树构造完毕，这时集合Q 中包含了最小生成树 的所有边。


6 z1 H. c* K8 C3 p
& p' q: `$ }- C9 L/ V例 13         用 prim 算法求图 5 的最小生成树。 我们用  的第一、二、三行分别表示生成树边的起点、终点、权集合。Matlab 程序如下：


  i2 X8 d* P9 S  ]; qclc;clear;
  q, U8 S+ Z( B3 y2 H1 Da=zeros(7);
a(1,2)=50; a(1,3)=60;
8 c  u- {, z6 p5 |' k5 U/ pa(2,4)=65; a(2,5)=40;
a(3,4)=52;a(3,7)=45;
$ g- n2 ]1 K1 @- }& f% B$ m  `a(4,5)=50; a(4,6)=30;a(4,7)=42;
5 X- V2 G' A$ X0 J/ }. Ia(5,6)=70;
7 X6 W" t, J1 f, N8 Ya=a+a';a(find(a==0))=inf;
) `- W- R: m4 @result=[];p=1;tb=2:length(a);
0 H5 {  o% Q) |: i, ~- Kwhile length(result)~=length(a)-1
# O( n% d; g2 D8 P    temp=a(p,tb);temp=temp(;
    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))=[];
, p( u# n( p* w% ^/ Z6 l# rend
" b1 V- x5 y( _result
. S) n. }* W1 p3 Q* E
2.1 Kruskal 算法构造最小生成树
) n! H+ L5 Q' @3 x/ n& M0 w科茹斯克尔（Kruskal）算法是一个好算法。Kruskal 算法如下:
( C% n. J5 p- F- q* ~
+ ?* @! V" a7 E

5 M; X, ?9 w. J8 U8 e例 14   用 Kruskal 算法构造例 3 的最小生成树。 我们用 存放各边端点的信息，当选中某一边之后，就将此边对应的顶点序 号中较大序号u 改记为此边的另一序号v ，同时把后面边中所有序号为u 的改记为v 。
& e, N+ C9 P7 m' Q: k- Y
此方法的几何意义是：将序号u 的这个顶点收缩到v 顶点，u 顶点不复存在。后面继续 寻查时，发现某边的两个顶点序号相同时，认为已被收缩掉，失去了被选取的资格。 Matlab 程序如下：

clc;clear;
a(1,2)=50; a(1,3)=60; a(2,4)=65; a(2,5)=40;
: X9 a$ Y4 i/ c. V" x; ta(3,4)=52;a(3,7)=45; a(4,5)=50; a(4,6)=30;
8 J$ C2 C0 i8 {+ ]* P; Ma(4,7)=42; a(5,6)=70;
[i,j,b]=find(a);
data=[i';j';b'];index=data(1:2,;
3 n0 s' A! B; x+ b+ b1 J! f7 K& floop=max(size(a))-1;
result=[];
while length(result)<loop
/ D* d* e" G! G0 b: ^" h    temp=min(data(3,);
    flag=find(data(3,==temp);
    flag=flag(1);
    v1=data(1,flag);v2=data(2,flag);
& r: n4 T" G, _8 C* ~    if index(1,flag)~=index(2,flag)
; h' R" T. ?) u8 W3 P+ Z        result=[result,data(:,flag)];
    end
' h8 d  C5 e8 X( s, P    index(find(index==v2))=v1;
    data(:,flag)=[];
    index(:,flag)=[];
end
result
7 ^7 c* Q) p: e
- i6 C3 ~4 v6 i1 C
  w+ B3 Y- r8 ^% n- k& v
! S# Y8 Q, @0 n" @% s————————————————
9 i1 E, r1 |3 }( d! x' _8 _版权声明：本文为CSDN博主「wamg潇潇」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
" W. E) c5 L& q8 K& y  i原文链接：https://blog.csdn.net/qq_29831163/article/details/89785681


  A: ?2 V  U: [1 f2 Z' |3 @2 h1 Y