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

浅夏110

1 基本概念
连通的无圈图叫做树，记之为T 。若图G 满足V(G) =V(T ) ， E(T ) ⊂ E(G) ， 则称T 是G 的生成树。图G 连通的充分必要条件为G 有生成树。一个连通图的生成树 的个数很多，用τ (G) 表示G 的生成树的个数，则有公式
& W6 @3 L1 Q1 t" R: h! Y0 M3 u

树有下面常用的五个充要条件。
6 q* y* {& h$ x' M
5 L4 A, Q7 k9 v* Z5 k定理 1 （i）G 是树当且仅当G 中任二顶点之间有且仅有一条轨道。
% z& ?9 B5 L$ w3 g3 P* d
（ii）G 是树当且仅当G 无圈，且ε =ν −1。
8 I0 |6 x) u1 ~2 H. v! h$ w0 R
（iii）G 是树当且仅当G 连通，且ε =ν −1。

6 |7 N9 `6 _5 H; A* K（iv）G 是树当且仅当G 连通，且∀e∈ E(G) ，G − e 不连通。
7 B, i4 U  [' @
1 x* n, o" [- F% B（v）G 是树当且仅当G 无圈，∀e∉ E(G) ，G + e 恰有一个圈。
- P" G* J8 }' `7 ^
2 应用—连线问题
7 Z4 l0 w2 B9 G' V, w5 B4 C 欲修筑连接 n 个城市的铁路，已知i 城与 j 城之间的铁路造价为Cij ，设计一个线 路图，使总造价最低。

连线问题的数学模型是在连通赋权图上求权最小的生成树。赋权图的具最小权的生 成树叫做最小生成树。
9 C8 ]/ d* R# B8 q: ^6 l
下面介绍构造最小生成树的两种常用算法。

2.1 prim 算法构造最小生成树
' l- l; P+ N3 m/ R* {7 ?0 m' S, m设置两个集合 P 和Q ,其中 P 用于存放G 的最小生成树中的顶点，集合Q 存放G的最小生成树中的边。令集合 P 的初值为 { P = v1 }（假设构造最小生成树时，从顶点 v1 出发），集合Q 的初值为Q = Φ 。
% O- h' {0 a$ `, W2 d
! c' Y, Z/ ]- D) G6 kprim 算法的思想是，从所有 p ∈ P ，v ∈V − P 的边 中，选取具有最小权值的边 pv ，将顶点 v 加入集合 P 中，将边 pv 加入集合Q 中，如 此不断重复，直到 P =V 时，最小生成树构造完毕，这时集合Q 中包含了最小生成树 的所有边。



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


1 c% W) r2 N' p6 Y' E5 I$ qclc;clear;
6 a( `& f& u& n. R3 X) t& r8 Ta=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;
! [5 H+ O/ R, ?+ Ua(4,5)=50; a(4,6)=30;a(4,7)=42;
a(5,6)=70;
a=a+a';a(find(a==0))=inf;
' h/ P+ [) h9 p& Presult=[];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);
    j=p(jb(1));k=tb(kb(1));
, L3 _5 q/ [: G1 ^. C    result=[result,[j;k;d]];p=[p,k];tb(find(tb==k))=[];
4 J) Y! H4 b: T. M$ y2 a4 tend
result

4 I# R+ l5 m3 M/ g% {2 b2.1 Kruskal 算法构造最小生成树
; B1 F  M; }* K: G1 }# K科茹斯克尔（Kruskal）算法是一个好算法。Kruskal 算法如下:

9 t& g" w7 p3 K( R) N8 E) Q

例 14   用 Kruskal 算法构造例 3 的最小生成树。 我们用 存放各边端点的信息，当选中某一边之后，就将此边对应的顶点序 号中较大序号u 改记为此边的另一序号v ，同时把后面边中所有序号为u 的改记为v 。

; P# m: C6 b& i; \此方法的几何意义是：将序号u 的这个顶点收缩到v 顶点，u 顶点不复存在。后面继续 寻查时，发现某边的两个顶点序号相同时，认为已被收缩掉，失去了被选取的资格。 Matlab 程序如下：
2 W/ j% I3 Y2 a9 U" }2 H1 f
clc;clear;
+ [7 f4 a- D' M; Ca(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;
5 S2 p' a/ V7 m& ^4 Q5 t8 ]9 k" Na(4,7)=42; a(5,6)=70;
[i,j,b]=find(a);
& y5 V% J0 x9 b/ [9 b9 ddata=[i';j';b'];index=data(1:2,;
loop=max(size(a))-1;
result=[];
while length(result)<loop
. ^/ N. N  a3 D/ p) X( T: k9 _    temp=min(data(3,);
+ t; q2 v! l' i# a" c    flag=find(data(3,==temp);
0 j: y8 `3 K$ A. b3 {    flag=flag(1);
) P3 Y5 Z$ ^3 n) w0 g4 D    v1=data(1,flag);v2=data(2,flag);
    if index(1,flag)~=index(2,flag)
        result=[result,data(:,flag)];
    end
    index(find(index==v2))=v1;
, Q" o# W% A: h& o6 R4 O# Q% e    data(:,flag)=[];
0 ~$ R2 @, `0 Z! {    index(:,flag)=[];
, j# d# j! {  g# ~! [; |end
9 u- j$ p1 ^; W2 ~2 R0 f3 ?result

. d, x9 q$ I  j5 a, R9 p
6 H2 Q3 e, N+ E, G: e
————————————————
, e* o- m0 X; i. {7 H6 G版权声明：本文为CSDN博主「wamg潇潇」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_29831163/article/details/89785681
: K# Q6 z& Q' {, X8 S# G3 T
1 c! L4 e9 E- [. a& A# q& [
' m8 z( d) v' O" \% p3 ^