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

浅夏110

1 基本概念
0 M. W3 p4 @4 I$ R+ f连通的无圈图叫做树，记之为T 。若图G 满足V(G) =V(T ) ， E(T ) ⊂ E(G) ， 则称T 是G 的生成树。图G 连通的充分必要条件为G 有生成树。一个连通图的生成树 的个数很多，用τ (G) 表示G 的生成树的个数，则有公式


1 a2 ]7 p  {2 @; R- Y* o树有下面常用的五个充要条件。
8 a& y3 i' o1 P) d
定理 1 （i）G 是树当且仅当G 中任二顶点之间有且仅有一条轨道。
6 i& ~. o: u4 H! U: i2 O
9 L# y' M7 R' i（ii）G 是树当且仅当G 无圈，且ε =ν −1。
' w! O8 u3 C. a9 U' R  \; L
4 [' K" w1 a# _; E0 T: h（iii）G 是树当且仅当G 连通，且ε =ν −1。

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

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

9 `; v& Z; O) H& K0 m0 o2 应用—连线问题
! _; @- ]# q# Y, ^* ] 欲修筑连接 n 个城市的铁路，已知i 城与 j 城之间的铁路造价为Cij ，设计一个线 路图，使总造价最低。

5 N  U+ ]3 s- `# p/ i连线问题的数学模型是在连通赋权图上求权最小的生成树。赋权图的具最小权的生 成树叫做最小生成树。
, u9 g8 j. f1 G& N3 S
下面介绍构造最小生成树的两种常用算法。

' i5 @7 N4 v& C( ?0 }2.1 prim 算法构造最小生成树
设置两个集合 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 中包含了最小生成树 的所有边。

! a  [" s9 f& F& v" b, {: x
  r/ D# v, ^( }5 m
7 h& x, e+ k2 k- `) M! f例 13         用 prim 算法求图 5 的最小生成树。 我们用  的第一、二、三行分别表示生成树边的起点、终点、权集合。Matlab 程序如下：


clc;clear;
a=zeros(7);
a(1,2)=50; a(1,3)=60;
a(2,4)=65; a(2,5)=40;
) x  _! r7 F# S0 Ja(3,4)=52;a(3,7)=45;
a(4,5)=50; a(4,6)=30;a(4,7)=42;
a(5,6)=70;
/ M" c- D; x5 i7 U) h$ {; qa=a+a';a(find(a==0))=inf;
2 e7 |! i& |  i5 i4 oresult=[];p=1;tb=2:length(a);
6 r3 s0 \& R) |" p6 j3 Owhile length(result)~=length(a)-1
    temp=a(p,tb);temp=temp(;
( o! w' ~; v4 A0 W    d=min(temp);
( K1 I% z+ t7 R% W    [jb,kb]=find(a(p,tb)==d);
4 O9 p& j9 M% a" x    j=p(jb(1));k=tb(kb(1));
    result=[result,[j;k;d]];p=[p,k];tb(find(tb==k))=[];
9 O0 ^% w9 q2 h. fend
& a& p2 @9 k5 ^3 {result
. }4 s5 l% B, H3 y$ @% A9 L2 k
2.1 Kruskal 算法构造最小生成树
科茹斯克尔（Kruskal）算法是一个好算法。Kruskal 算法如下:
# l4 T$ W5 r1 D9 E$ S! v
; ^+ s0 T  u5 x! Y3 l) G, v+ m
! s% m7 d: W1 d- T% A" n* N. i$ B* a
3 q4 e6 M+ u! X& y7 k- F/ y( x例 14   用 Kruskal 算法构造例 3 的最小生成树。 我们用 存放各边端点的信息，当选中某一边之后，就将此边对应的顶点序 号中较大序号u 改记为此边的另一序号v ，同时把后面边中所有序号为u 的改记为v 。
5 a" |9 c$ Z& S% T% Z8 m
此方法的几何意义是：将序号u 的这个顶点收缩到v 顶点，u 顶点不复存在。后面继续 寻查时，发现某边的两个顶点序号相同时，认为已被收缩掉，失去了被选取的资格。 Matlab 程序如下：
# G, R  G; x$ ^1 i) G
clc;clear;
a(1,2)=50; a(1,3)=60; a(2,4)=65; a(2,5)=40;
! c. F5 O8 f, T- ?, n/ h- r! ra(3,4)=52;a(3,7)=45; a(4,5)=50; a(4,6)=30;
( S  @) a5 c2 D( [6 \6 F" ta(4,7)=42; a(5,6)=70;
! l0 ?4 w! i/ B5 q4 Q- ?- i[i,j,b]=find(a);
data=[i';j';b'];index=data(1:2,;
loop=max(size(a))-1;
result=[];
while length(result)<loop
    temp=min(data(3,);
0 v' D0 d6 Q  c2 a( b3 m. K    flag=find(data(3,==temp);
8 w) |! g, [1 u0 K4 v    flag=flag(1);
1 u5 |! I& R8 ^- v: E; D    v1=data(1,flag);v2=data(2,flag);
+ T: v8 P. j  Z8 F* q) e    if index(1,flag)~=index(2,flag)
* d5 O- t6 l& F        result=[result,data(:,flag)];
    end
    index(find(index==v2))=v1;
    data(:,flag)=[];
$ [- y2 J9 l, o& r9 W4 J0 @8 U9 j    index(:,flag)=[];
end
result
; Y: K! j# p# m1 {& O8 F9 M
" A% e/ e+ n+ r0 ^
1 p; A! `6 h0 Y8 i
1 ^/ B: b* m5 S5 R————————————————
版权声明：本文为CSDN博主「wamg潇潇」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_29831163/article/details/89785681
5 E6 C+ v, g* g  u% f) |' M7 {; r
  B; p+ Y9 _2 {8 I/ ~& l. u9 Y
( x4 u  N  \- a3 M