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

浅夏110

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

树有下面常用的五个充要条件。

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

2 e) M* t+ E5 V% y' ?" ]/ I! d# h（ii）G 是树当且仅当G 无圈，且ε =ν −1。
  G' }5 j" j. J: a) [# H5 R! M
4 O) P" R6 t3 O（iii）G 是树当且仅当G 连通，且ε =ν −1。
- c+ H. T% r% F+ J
" ]* x* w! L) U4 ~# y* P$ G5 `（iv）G 是树当且仅当G 连通，且∀e∈ E(G) ，G − e 不连通。

$ r$ Z1 j! m- `# }5 s5 {（v）G 是树当且仅当G 无圈，∀e∉ E(G) ，G + e 恰有一个圈。
: ^# ^$ r8 P" c8 r. S" m! e, f
2 应用—连线问题
, t4 |7 i& e+ D% [$ n: H: [3 C0 N- J. m 欲修筑连接 n 个城市的铁路，已知i 城与 j 城之间的铁路造价为Cij ，设计一个线 路图，使总造价最低。
$ y: \. J, I7 k8 q! w
: Z( D  V3 F# J: Q) r* [连线问题的数学模型是在连通赋权图上求权最小的生成树。赋权图的具最小权的生 成树叫做最小生成树。
) D) E3 P$ l3 _
$ Q5 @  n3 @4 S  K: p# c下面介绍构造最小生成树的两种常用算法。

2.1 prim 算法构造最小生成树
设置两个集合 P 和Q ,其中 P 用于存放G 的最小生成树中的顶点，集合Q 存放G的最小生成树中的边。令集合 P 的初值为 { P = v1 }（假设构造最小生成树时，从顶点 v1 出发），集合Q 的初值为Q = Φ 。
2 {0 J8 @: P1 m# u* _
prim 算法的思想是，从所有 p ∈ P ，v ∈V − P 的边 中，选取具有最小权值的边 pv ，将顶点 v 加入集合 P 中，将边 pv 加入集合Q 中，如 此不断重复，直到 P =V 时，最小生成树构造完毕，这时集合Q 中包含了最小生成树 的所有边。
' t6 ~/ N  b1 n
( A3 @% C1 r( x  k

例 13         用 prim 算法求图 5 的最小生成树。 我们用  的第一、二、三行分别表示生成树边的起点、终点、权集合。Matlab 程序如下：

% F% O3 K+ y" D0 e
3 {4 [2 Q, L9 @' _# gclc;clear;
a=zeros(7);
a(1,2)=50; a(1,3)=60;
a(2,4)=65; a(2,5)=40;
4 j8 |+ Z) b& f( q5 b; ^8 _  V- H2 x  D1 qa(3,4)=52;a(3,7)=45;
a(4,5)=50; a(4,6)=30;a(4,7)=42;
a(5,6)=70;
7 {+ D+ T9 `& r& @) R' ^4 Ua=a+a';a(find(a==0))=inf;
2 y9 n: g  ]0 n! |& y% w, `3 wresult=[];p=1;tb=2:length(a);
while length(result)~=length(a)-1
    temp=a(p,tb);temp=temp(;
    d=min(temp);
    [jb,kb]=find(a(p,tb)==d);
( P; k; `% I! [    j=p(jb(1));k=tb(kb(1));
    result=[result,[j;k;d]];p=[p,k];tb(find(tb==k))=[];
end
: N/ ?  M; a+ ?- o9 nresult

% u- Z. q' Y2 i( \* D2.1 Kruskal 算法构造最小生成树
科茹斯克尔（Kruskal）算法是一个好算法。Kruskal 算法如下:

0 N% [3 x; ]. z' D4 z1 l
6 E( m4 C. |1 _7 }5 _
例 14   用 Kruskal 算法构造例 3 的最小生成树。 我们用 存放各边端点的信息，当选中某一边之后，就将此边对应的顶点序 号中较大序号u 改记为此边的另一序号v ，同时把后面边中所有序号为u 的改记为v 。
; W9 y, C. `, A$ h8 ]
此方法的几何意义是：将序号u 的这个顶点收缩到v 顶点，u 顶点不复存在。后面继续 寻查时，发现某边的两个顶点序号相同时，认为已被收缩掉，失去了被选取的资格。 Matlab 程序如下：
3 I7 S' W6 V9 g1 Y' \7 E  |
clc;clear;
a(1,2)=50; a(1,3)=60; a(2,4)=65; a(2,5)=40;
0 {" a6 f/ m) \! G7 ia(3,4)=52;a(3,7)=45; a(4,5)=50; a(4,6)=30;
: s* t1 x1 ?4 S2 G7 O/ Pa(4,7)=42; a(5,6)=70;
* I* l9 Z! ]' t/ I+ K7 V[i,j,b]=find(a);
data=[i';j';b'];index=data(1:2,;
6 ~- D. u' h5 n: }- Nloop=max(size(a))-1;
result=[];
while length(result)<loop
/ z6 V6 J2 H% D5 G    temp=min(data(3,);
    flag=find(data(3,==temp);
4 |4 R: G1 q# k4 f# w5 h    flag=flag(1);
5 R: o6 V* C0 Q; r8 U8 N  M" e    v1=data(1,flag);v2=data(2,flag);
    if index(1,flag)~=index(2,flag)
! V1 b: v/ B) K0 c. }        result=[result,data(:,flag)];
    end
    index(find(index==v2))=v1;
+ ?6 ^1 P1 V8 g2 g6 r+ B    data(:,flag)=[];
3 s! `! o: G. S) r7 u: r    index(:,flag)=[];
! `3 t" p8 Z  T0 ~5 M& z" fend
result
) {; _% Z; w# B6 H* y& T


————————————————
4 Q: l' n6 h1 D; S- x- j5 ?( o版权声明：本文为CSDN博主「wamg潇潇」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_29831163/article/details/89785681
. w! o, _5 Q! U- E/ }2 L8 ~/ b
6 ]9 V! ?7 N9 @$ t