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

浅夏110

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


" B1 J7 x0 d5 @. U; {8 R6 O树有下面常用的五个充要条件。
1 d; ?$ S6 F  h
8 {7 I) c. v; a! d! l6 U. l( c. b定理 1 （i）G 是树当且仅当G 中任二顶点之间有且仅有一条轨道。

% w  B3 E. o( S$ S（ii）G 是树当且仅当G 无圈，且ε =ν −1。
1 a; ?0 G6 r# u/ v" U' y
8 b, P0 f3 e& I$ E7 {0 o3 K（iii）G 是树当且仅当G 连通，且ε =ν −1。
$ m. u* \; t9 @5 h
（iv）G 是树当且仅当G 连通，且∀e∈ E(G) ，G − e 不连通。

- E; c# }8 y- s（v）G 是树当且仅当G 无圈，∀e∉ E(G) ，G + e 恰有一个圈。
* r, V8 [; c% L6 r3 G
2 应用—连线问题
+ g6 m) K( b$ r3 } 欲修筑连接 n 个城市的铁路，已知i 城与 j 城之间的铁路造价为Cij ，设计一个线 路图，使总造价最低。

连线问题的数学模型是在连通赋权图上求权最小的生成树。赋权图的具最小权的生 成树叫做最小生成树。

9 x+ t3 s# U& R5 \8 F下面介绍构造最小生成树的两种常用算法。

2.1 prim 算法构造最小生成树
( h+ M* I: z+ g% M设置两个集合 P 和Q ,其中 P 用于存放G 的最小生成树中的顶点，集合Q 存放G的最小生成树中的边。令集合 P 的初值为 { P = v1 }（假设构造最小生成树时，从顶点 v1 出发），集合Q 的初值为Q = Φ 。
- U8 r2 z2 C$ }9 Z0 S/ ?5 U5 b
6 p6 ~4 h3 j8 G. r% Gprim 算法的思想是，从所有 p ∈ P ，v ∈V − P 的边 中，选取具有最小权值的边 pv ，将顶点 v 加入集合 P 中，将边 pv 加入集合Q 中，如 此不断重复，直到 P =V 时，最小生成树构造完毕，这时集合Q 中包含了最小生成树 的所有边。
1 ^1 r* f/ n, h: I4 V  g
7 C# q: [" \) r
! f" q* |% p2 F2 J
" p0 e3 a4 f6 n$ V+ z例 13         用 prim 算法求图 5 的最小生成树。 我们用  的第一、二、三行分别表示生成树边的起点、终点、权集合。Matlab 程序如下：

6 \3 ]( M. u  D+ X9 M% A6 d  @& o
& `% q4 e" k# r* r  e( zclc;clear;
a=zeros(7);
1 d# w5 Z% k7 `& c$ Q: O: n5 ]a(1,2)=50; a(1,3)=60;
) c, [5 S+ n( O, ^$ u$ ga(2,4)=65; a(2,5)=40;
! s3 V$ W1 U. m5 j. I. aa(3,4)=52;a(3,7)=45;
a(4,5)=50; a(4,6)=30;a(4,7)=42;
a(5,6)=70;
a=a+a';a(find(a==0))=inf;
result=[];p=1;tb=2:length(a);
while length(result)~=length(a)-1
8 A6 i) I- L: e    temp=a(p,tb);temp=temp(;
    d=min(temp);
! n! m" B* R( ^  D3 n" G6 T    [jb,kb]=find(a(p,tb)==d);
1 X, V4 H7 `; i" G; Z    j=p(jb(1));k=tb(kb(1));
    result=[result,[j;k;d]];p=[p,k];tb(find(tb==k))=[];
end
result

2.1 Kruskal 算法构造最小生成树
: `% |* |. L3 ]5 _/ H" _4 K科茹斯克尔（Kruskal）算法是一个好算法。Kruskal 算法如下:



5 Q2 H+ w4 p' H$ M8 R# w- T% H例 14   用 Kruskal 算法构造例 3 的最小生成树。 我们用 存放各边端点的信息，当选中某一边之后，就将此边对应的顶点序 号中较大序号u 改记为此边的另一序号v ，同时把后面边中所有序号为u 的改记为v 。

此方法的几何意义是：将序号u 的这个顶点收缩到v 顶点，u 顶点不复存在。后面继续 寻查时，发现某边的两个顶点序号相同时，认为已被收缩掉，失去了被选取的资格。 Matlab 程序如下：
0 @0 E: N) \& D. Z9 O! A# O1 o
+ }5 i4 e& P2 A7 y& Y5 n' M  m, `clc;clear;
a(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;
/ }- [- e+ j4 [% ta(4,7)=42; a(5,6)=70;
[i,j,b]=find(a);
4 b  N- A( h6 ?% J8 V! Pdata=[i';j';b'];index=data(1:2,;
loop=max(size(a))-1;
result=[];
( {1 n: v! E0 ]# O  fwhile length(result)<loop
$ j5 I/ |5 Y/ g) o) ~$ W7 m3 T0 K    temp=min(data(3,);
  L1 ?- I6 J! C0 f! f4 g    flag=find(data(3,==temp);
0 I: U4 @' B6 `! z& `) v) ~    flag=flag(1);
    v1=data(1,flag);v2=data(2,flag);
    if index(1,flag)~=index(2,flag)
        result=[result,data(:,flag)];
" l4 M. e1 r! C  t$ |0 |: y5 m    end
! {2 W& x, }3 u( K$ S& C7 Z    index(find(index==v2))=v1;
    data(:,flag)=[];
8 G' F# D4 ]! ~$ x6 H+ C    index(:,flag)=[];
: y3 J' I# F4 X- H* ?7 h$ L0 wend
result
8 z' z0 Q: n5 I; Z0 Q  P' G- ^' {
0 y9 G9 j! e" a0 ]  O

$ @6 O3 R) h& [————————————————
$ m" u: H4 g$ y版权声明：本文为CSDN博主「wamg潇潇」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
4 g& l8 ]0 r3 k; L" y- h原文链接：https://blog.csdn.net/qq_29831163/article/details/89785681


% m- j2 \# Y1 j5 ~1 l- `+ u