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

浅夏110

1 基本概念
* h; b6 B2 J; V( v( J连通的无圈图叫做树，记之为T 。若图G 满足V(G) =V(T ) ， E(T ) ⊂ E(G) ， 则称T 是G 的生成树。图G 连通的充分必要条件为G 有生成树。一个连通图的生成树 的个数很多，用τ (G) 表示G 的生成树的个数，则有公式


树有下面常用的五个充要条件。
  t; P- c$ a, M% r5 W0 {
: q' h8 `" l7 r定理 1 （i）G 是树当且仅当G 中任二顶点之间有且仅有一条轨道。

" U6 O4 I8 o  j3 e. e! o& R（ii）G 是树当且仅当G 无圈，且ε =ν −1。
# I; A8 H& E3 Y3 s/ V/ l+ [7 ], B7 q/ N
/ v0 J3 K# E& v2 F& B. x（iii）G 是树当且仅当G 连通，且ε =ν −1。

8 ?/ j# I! y( c+ M6 |. P  ~+ D（iv）G 是树当且仅当G 连通，且∀e∈ E(G) ，G − e 不连通。

9 R/ D, n% b; [# ]3 r3 y" P& i（v）G 是树当且仅当G 无圈，∀e∉ E(G) ，G + e 恰有一个圈。

8 E) t: v1 G% Q$ Z. A2 应用—连线问题
欲修筑连接 n 个城市的铁路，已知i 城与 j 城之间的铁路造价为Cij ，设计一个线 路图，使总造价最低。
" @: w# K8 |$ o6 Q* y, Q
连线问题的数学模型是在连通赋权图上求权最小的生成树。赋权图的具最小权的生 成树叫做最小生成树。

下面介绍构造最小生成树的两种常用算法。

2.1 prim 算法构造最小生成树
$ K+ M4 T, m$ v  \2 z$ S, a4 Z设置两个集合 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 中包含了最小生成树 的所有边。


5 J7 u) `8 Z# A" W
0 E+ B# v( `/ R例 13         用 prim 算法求图 5 的最小生成树。 我们用  的第一、二、三行分别表示生成树边的起点、终点、权集合。Matlab 程序如下：


: y! x- F8 f2 {: I" Qclc;clear;
a=zeros(7);
# [1 F) Q; I5 `& Z4 W" Ga(1,2)=50; a(1,3)=60;
6 ^6 t0 `' r) o$ V) P+ g/ na(2,4)=65; a(2,5)=40;
a(3,4)=52;a(3,7)=45;
a(4,5)=50; a(4,6)=30;a(4,7)=42;
/ b- e. L) u7 na(5,6)=70;
- C* T2 x! l5 x/ u2 La=a+a';a(find(a==0))=inf;
- r7 D- b  P4 L# dresult=[];p=1;tb=2:length(a);
while length(result)~=length(a)-1
( G$ f/ y) g. ]& C: Q    temp=a(p,tb);temp=temp(;
: v4 J- [7 G) j+ X7 ^1 U    d=min(temp);
+ _0 T5 O3 _1 ^: w4 D) V+ Z    [jb,kb]=find(a(p,tb)==d);
1 v, j1 H6 @* P" P- d    j=p(jb(1));k=tb(kb(1));
+ U; G1 G) g' N& \    result=[result,[j;k;d]];p=[p,k];tb(find(tb==k))=[];
end
result
+ S6 z+ b+ `+ u' u  j
2.1 Kruskal 算法构造最小生成树
  ^7 \, z1 t2 P科茹斯克尔（Kruskal）算法是一个好算法。Kruskal 算法如下:
1 I. y! h& Z/ m$ x


例 14   用 Kruskal 算法构造例 3 的最小生成树。 我们用 存放各边端点的信息，当选中某一边之后，就将此边对应的顶点序 号中较大序号u 改记为此边的另一序号v ，同时把后面边中所有序号为u 的改记为v 。
5 {/ p0 _2 E7 E
4 B! @: `$ P& `此方法的几何意义是：将序号u 的这个顶点收缩到v 顶点，u 顶点不复存在。后面继续 寻查时，发现某边的两个顶点序号相同时，认为已被收缩掉，失去了被选取的资格。 Matlab 程序如下：

clc;clear;
- x- m- O0 a7 X3 Oa(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;
& l  K$ }- d4 O$ _+ z2 n& ya(4,7)=42; a(5,6)=70;
& v+ x* }* y$ S# T: h[i,j,b]=find(a);
data=[i';j';b'];index=data(1:2,;
loop=max(size(a))-1;
4 T+ }8 _9 j5 X  Jresult=[];
while length(result)<loop
7 z9 g' z; o% f! k  a6 f    temp=min(data(3,);
6 z6 M3 m( y% G8 I    flag=find(data(3,==temp);
    flag=flag(1);
    v1=data(1,flag);v2=data(2,flag);
+ B' Z/ _, l/ C' N1 ]0 s    if index(1,flag)~=index(2,flag)
        result=[result,data(:,flag)];
; d& s/ o. f8 ~    end
: ~! `3 F% x* i& @: f" z    index(find(index==v2))=v1;
0 I7 l) @' ]0 _) z* a% r    data(:,flag)=[];
    index(:,flag)=[];
. k) _/ v. A" n# G# Fend
/ a9 ?8 i* t$ s6 }1 nresult
5 ^# C* }! |/ ^) X7 i8 i$ @. o


————————————————
! p# C, V1 R- F6 N9 J9 y" ?版权声明：本文为CSDN博主「wamg潇潇」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_29831163/article/details/89785681
8 J( }/ p, f  @  U; ~) G3 q
" [! m+ n% h6 ?. |) Q
' ?' ?2 M! h, D% _5 o