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

浅夏110

1 基本概念
, H2 F! ]- C; }1 z9 m5 z/ J4 F连通的无圈图叫做树，记之为T 。若图G 满足V(G) =V(T ) ， E(T ) ⊂ E(G) ， 则称T 是G 的生成树。图G 连通的充分必要条件为G 有生成树。一个连通图的生成树 的个数很多，用τ (G) 表示G 的生成树的个数，则有公式
6 q7 y2 @; P/ _8 X; [: E# m! _  ?+ |
$ i( v: v' x" ]+ y- v. p' x0 N
树有下面常用的五个充要条件。
0 Q9 i& M& X9 X; p
定理 1 （i）G 是树当且仅当G 中任二顶点之间有且仅有一条轨道。

（ii）G 是树当且仅当G 无圈，且ε =ν −1。
4 N1 ^: [* X8 O1 ?$ A9 t
4 k1 y  A, u/ r+ c" P, b（iii）G 是树当且仅当G 连通，且ε =ν −1。

（iv）G 是树当且仅当G 连通，且∀e∈ E(G) ，G − e 不连通。
# Q2 h3 G) x+ A2 E' t. Z
  j$ h0 I/ `1 h3 k" N（v）G 是树当且仅当G 无圈，∀e∉ E(G) ，G + e 恰有一个圈。

2 应用—连线问题
欲修筑连接 n 个城市的铁路，已知i 城与 j 城之间的铁路造价为Cij ，设计一个线 路图，使总造价最低。

连线问题的数学模型是在连通赋权图上求权最小的生成树。赋权图的具最小权的生 成树叫做最小生成树。
* `: C8 w/ K7 `9 v" y
下面介绍构造最小生成树的两种常用算法。

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 中包含了最小生成树 的所有边。
# x/ S( B2 o5 x! ]


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

# P) x% y/ r& k9 ^+ A) t2 k/ b
! P2 \! V- z; \5 P7 @5 n- a9 sclc;clear;
8 A1 m8 S% f; `8 u0 Ka=zeros(7);
7 m; H/ {# ~% e$ [a(1,2)=50; a(1,3)=60;
3 O# T* B4 [5 O7 pa(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;
; _, N: g7 R1 d% {! f4 ha(5,6)=70;
a=a+a';a(find(a==0))=inf;
result=[];p=1;tb=2:length(a);
while length(result)~=length(a)-1
    temp=a(p,tb);temp=temp(;
    d=min(temp);
8 ]6 L. w% W/ a- S  {    [jb,kb]=find(a(p,tb)==d);
: ~! k! L& s" S/ s* j    j=p(jb(1));k=tb(kb(1));
8 m$ o* x! O$ I& v% [    result=[result,[j;k;d]];p=[p,k];tb(find(tb==k))=[];
end
2 m! ?" g% ]$ Y! Y' k( h& Dresult

/ G7 q1 A: X1 k0 _, i2.1 Kruskal 算法构造最小生成树
科茹斯克尔（Kruskal）算法是一个好算法。Kruskal 算法如下:
2 F/ |  l) X7 ?- p
' Q" W% ?' \* u; m3 i
* f' U& l; t% [
例 14   用 Kruskal 算法构造例 3 的最小生成树。 我们用 存放各边端点的信息，当选中某一边之后，就将此边对应的顶点序 号中较大序号u 改记为此边的另一序号v ，同时把后面边中所有序号为u 的改记为v 。

# f! k) m5 e+ k9 C- H- j) A此方法的几何意义是：将序号u 的这个顶点收缩到v 顶点，u 顶点不复存在。后面继续 寻查时，发现某边的两个顶点序号相同时，认为已被收缩掉，失去了被选取的资格。 Matlab 程序如下：

clc;clear;
! b# i, N2 J. O( Ra(1,2)=50; a(1,3)=60; a(2,4)=65; a(2,5)=40;
1 K$ |+ T" n/ Ia(3,4)=52;a(3,7)=45; a(4,5)=50; a(4,6)=30;
a(4,7)=42; a(5,6)=70;
[i,j,b]=find(a);
% B$ z  I4 c- q2 V/ T$ X+ K. A. q) i, ~data=[i';j';b'];index=data(1:2,;
: h7 d8 x7 C) o0 k7 Eloop=max(size(a))-1;
' Q  j' K: X% H+ |$ c# G' E2 _7 Vresult=[];
; k1 h5 F, A- iwhile length(result)<loop
5 `3 O9 }8 ]1 |( ?# f+ S# d    temp=min(data(3,);
3 T0 t, s" O3 S' W, ]    flag=find(data(3,==temp);
9 @! j) ?  i6 O$ F, o9 W    flag=flag(1);
& \* S+ u  I5 z% S. N- l* i& d; h    v1=data(1,flag);v2=data(2,flag);
% w# H4 B  w, U# ~    if index(1,flag)~=index(2,flag)
        result=[result,data(:,flag)];
% M. F9 `/ U$ G) {, c    end
    index(find(index==v2))=v1;
8 \6 _  m/ O8 Z1 \    data(:,flag)=[];
    index(:,flag)=[];
end
result
, d; `2 F! _; Z: s& E+ _0 h, e, \


4 p- f, I) A$ v; m! b————————————————
版权声明：本文为CSDN博主「wamg潇潇」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
4 p0 k# `! {% {5 E原文链接：https://blog.csdn.net/qq_29831163/article/details/89785681


  p; o) @5 S$ d8 ]