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

浅夏110

1 基本概念
连通的无圈图叫做树，记之为T 。若图G 满足V(G) =V(T ) ， E(T ) ⊂ E(G) ， 则称T 是G 的生成树。图G 连通的充分必要条件为G 有生成树。一个连通图的生成树 的个数很多，用τ (G) 表示G 的生成树的个数，则有公式
& p& c, z& y, A# i8 @
3 A4 ^3 e8 d. h0 F& z
树有下面常用的五个充要条件。
8 y- e) U) m3 r% V( k0 v6 u
. G# ]7 D# w  I( ~0 y/ X+ \定理 1 （i）G 是树当且仅当G 中任二顶点之间有且仅有一条轨道。

（ii）G 是树当且仅当G 无圈，且ε =ν −1。
- W+ ~8 y# H# P8 Y$ |
  B' c& ^: B2 v" d' V（iii）G 是树当且仅当G 连通，且ε =ν −1。

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

  n9 p& W( N* r) l（v）G 是树当且仅当G 无圈，∀e∉ E(G) ，G + e 恰有一个圈。

" h; w. s8 X" g2 A! ]2 G0 ^; `+ A2 应用—连线问题
  x8 s- o' }7 O* K6 U 欲修筑连接 n 个城市的铁路，已知i 城与 j 城之间的铁路造价为Cij ，设计一个线 路图，使总造价最低。

连线问题的数学模型是在连通赋权图上求权最小的生成树。赋权图的具最小权的生 成树叫做最小生成树。
4 z3 L3 i  g0 C* O% i5 {. |
+ l6 e; D2 k+ S# N1 D下面介绍构造最小生成树的两种常用算法。
+ c( l" _; ~$ t/ z* z
0 N* G6 u" z9 l5 v2.1 prim 算法构造最小生成树
6 a3 c" z& a8 s# ]) l设置两个集合 P 和Q ,其中 P 用于存放G 的最小生成树中的顶点，集合Q 存放G的最小生成树中的边。令集合 P 的初值为 { P = v1 }（假设构造最小生成树时，从顶点 v1 出发），集合Q 的初值为Q = Φ 。

/ ~: c$ p* C1 u% Y7 E1 q/ \7 Gprim 算法的思想是，从所有 p ∈ P ，v ∈V − P 的边 中，选取具有最小权值的边 pv ，将顶点 v 加入集合 P 中，将边 pv 加入集合Q 中，如 此不断重复，直到 P =V 时，最小生成树构造完毕，这时集合Q 中包含了最小生成树 的所有边。



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

; V) e. y: @! g' sclc;clear;
5 V( T9 w0 Y; v' P. g- J" g. Z8 Ua=zeros(7);
a(1,2)=50; a(1,3)=60;
a(2,4)=65; a(2,5)=40;
a(3,4)=52;a(3,7)=45;
# s2 d. y1 j; W6 L; xa(4,5)=50; a(4,6)=30;a(4,7)=42;
) H9 m% p; B6 q" l2 v9 ha(5,6)=70;
3 [( G! }$ f7 ha=a+a';a(find(a==0))=inf;
result=[];p=1;tb=2:length(a);
while length(result)~=length(a)-1
/ p/ @9 v4 p! x5 |; }6 H    temp=a(p,tb);temp=temp(;
5 U" O) d9 b  p! @    d=min(temp);
    [jb,kb]=find(a(p,tb)==d);
    j=p(jb(1));k=tb(kb(1));
" {8 [% X, E$ O- R( L    result=[result,[j;k;d]];p=[p,k];tb(find(tb==k))=[];
+ K& c8 m: ^1 y5 oend
4 J+ W5 r; R: M+ `result

2.1 Kruskal 算法构造最小生成树
科茹斯克尔（Kruskal）算法是一个好算法。Kruskal 算法如下:

$ x3 V. }, x9 j  R3 f
2 S9 M) G+ {, \$ U( e
, q6 i" ~" h& k6 ]4 n8 g例 14   用 Kruskal 算法构造例 3 的最小生成树。 我们用 存放各边端点的信息，当选中某一边之后，就将此边对应的顶点序 号中较大序号u 改记为此边的另一序号v ，同时把后面边中所有序号为u 的改记为v 。
% @3 j9 y4 s4 U" O6 d4 t
此方法的几何意义是：将序号u 的这个顶点收缩到v 顶点，u 顶点不复存在。后面继续 寻查时，发现某边的两个顶点序号相同时，认为已被收缩掉，失去了被选取的资格。 Matlab 程序如下：

8 a' G6 e; v- k/ r5 [clc;clear;
% C/ e! W/ k4 a( J$ W& @% ta(1,2)=50; a(1,3)=60; a(2,4)=65; a(2,5)=40;
a(3,4)=52;a(3,7)=45; a(4,5)=50; a(4,6)=30;
& b# {; i8 U2 r- G4 l/ qa(4,7)=42; a(5,6)=70;
[i,j,b]=find(a);
data=[i';j';b'];index=data(1:2,;
loop=max(size(a))-1;
' B* ]2 T6 q  e7 [6 Jresult=[];
while length(result)<loop
    temp=min(data(3,);
1 C- c1 l! T! \% ]1 I( \3 w+ v) D    flag=find(data(3,==temp);
    flag=flag(1);
- j& J' K3 J! z$ X4 }; I  h    v1=data(1,flag);v2=data(2,flag);
8 t7 k# I- }9 p/ y$ ?4 f    if index(1,flag)~=index(2,flag)
7 u* h# z  P* _) }        result=[result,data(:,flag)];
    end
8 Q% x" x; D! u3 v. H! Z& S4 |    index(find(index==v2))=v1;
: x3 C- X+ b/ p7 s; a    data(:,flag)=[];
/ F4 p4 l; H) n. g; L- g    index(:,flag)=[];
6 g! I' \9 c3 lend
result



1 k- v: I- Y0 a* D————————————————
版权声明：本文为CSDN博主「wamg潇潇」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_29831163/article/details/89785681
5 C2 U7 _: T+ r% k' l$ h
& p+ l# f. {+ E