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

浅夏110

1 基本概念
4 g: X1 {2 N$ a2 Q) h; z5 s( Z连通的无圈图叫做树，记之为T 。若图G 满足V(G) =V(T ) ， E(T ) ⊂ E(G) ， 则称T 是G 的生成树。图G 连通的充分必要条件为G 有生成树。一个连通图的生成树 的个数很多，用τ (G) 表示G 的生成树的个数，则有公式
7 `. W1 M0 G- N- C. v$ e% w) K
! S# v- z; P; H' G3 r) y6 w
树有下面常用的五个充要条件。

/ @* {' y7 H/ h" O定理 1 （i）G 是树当且仅当G 中任二顶点之间有且仅有一条轨道。

9 z# z/ c5 K3 N& T# X5 H. R（ii）G 是树当且仅当G 无圈，且ε =ν −1。

9 D; c* Q4 Q. R6 o. O（iii）G 是树当且仅当G 连通，且ε =ν −1。
. M. x+ N# c2 C- T7 {
（iv）G 是树当且仅当G 连通，且∀e∈ E(G) ，G − e 不连通。

. R, P) ~: ^. t- x/ A/ ?（v）G 是树当且仅当G 无圈，∀e∉ E(G) ，G + e 恰有一个圈。

: Z4 f% q  F( i) C4 M0 {2 应用—连线问题
0 h8 h1 x$ d) e6 O; c& A* j( R+ ] 欲修筑连接 n 个城市的铁路，已知i 城与 j 城之间的铁路造价为Cij ，设计一个线 路图，使总造价最低。
( G* I7 Y; y# T# x' ^
! n  T" n/ p9 V, n* X$ r# M7 X连线问题的数学模型是在连通赋权图上求权最小的生成树。赋权图的具最小权的生 成树叫做最小生成树。

下面介绍构造最小生成树的两种常用算法。
' Z+ @, w5 o2 m) \! X, ^9 e; h
2 Y3 ~' M( F  ~  p2.1 prim 算法构造最小生成树
/ y* ]! }7 D, H% J! N# s/ t设置两个集合 P 和Q ,其中 P 用于存放G 的最小生成树中的顶点，集合Q 存放G的最小生成树中的边。令集合 P 的初值为 { P = v1 }（假设构造最小生成树时，从顶点 v1 出发），集合Q 的初值为Q = Φ 。

! @  f- `: A" A1 B" w0 k0 zprim 算法的思想是，从所有 p ∈ P ，v ∈V − P 的边 中，选取具有最小权值的边 pv ，将顶点 v 加入集合 P 中，将边 pv 加入集合Q 中，如 此不断重复，直到 P =V 时，最小生成树构造完毕，这时集合Q 中包含了最小生成树 的所有边。
. x2 F4 K6 D8 y  A! u6 s% d1 [
8 ?# d- h  D- H% X8 C5 C3 J
, y9 s/ G3 K8 r% w
/ U0 P1 I. b- T# p例 13         用 prim 算法求图 5 的最小生成树。 我们用  的第一、二、三行分别表示生成树边的起点、终点、权集合。Matlab 程序如下：

& o/ G! b& B! L7 {/ i
/ }6 f* E  W0 T5 }# dclc;clear;
a=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;
- I( {& S* P# V. K% w3 ?6 W3 Ua(4,5)=50; a(4,6)=30;a(4,7)=42;
a(5,6)=70;
a=a+a';a(find(a==0))=inf;
3 |3 h* T* L2 `' K+ aresult=[];p=1;tb=2:length(a);
5 w* n! U. t7 @) _while length(result)~=length(a)-1
0 p" x5 }7 }8 ]2 ~' V    temp=a(p,tb);temp=temp(;
4 B4 Q2 f, D) P    d=min(temp);
    [jb,kb]=find(a(p,tb)==d);
5 I2 X; T" k* l& s9 j    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 算法构造最小生成树
; G2 T" o0 U: t* p  i" O- C/ P科茹斯克尔（Kruskal）算法是一个好算法。Kruskal 算法如下:



: h6 M/ V' |1 ^; }7 P例 14   用 Kruskal 算法构造例 3 的最小生成树。 我们用 存放各边端点的信息，当选中某一边之后，就将此边对应的顶点序 号中较大序号u 改记为此边的另一序号v ，同时把后面边中所有序号为u 的改记为v 。
$ y% V0 K3 y4 I2 B3 c: W/ ]
' i; D# I) e* F8 s$ p$ q此方法的几何意义是：将序号u 的这个顶点收缩到v 顶点，u 顶点不复存在。后面继续 寻查时，发现某边的两个顶点序号相同时，认为已被收缩掉，失去了被选取的资格。 Matlab 程序如下：

clc;clear;
/ d- m9 b, o, {2 {a(1,2)=50; a(1,3)=60; a(2,4)=65; a(2,5)=40;
' K, m( F" U0 E7 W. Aa(3,4)=52;a(3,7)=45; a(4,5)=50; a(4,6)=30;
3 z+ E) s; i8 J% pa(4,7)=42; a(5,6)=70;
[i,j,b]=find(a);
data=[i';j';b'];index=data(1:2,;
8 Q. ^. d$ Z0 L, L+ S/ K: a+ ]loop=max(size(a))-1;
) v! Y9 w0 a3 [- p# fresult=[];
  Q) L# H- Z" p  _# v' r" E* Y- Vwhile length(result)<loop
    temp=min(data(3,);
    flag=find(data(3,==temp);
. ~* C1 Q. W+ a$ G$ Q    flag=flag(1);
    v1=data(1,flag);v2=data(2,flag);
    if index(1,flag)~=index(2,flag)
' o) g  S+ H9 l- ~0 J        result=[result,data(:,flag)];
    end
( X+ i) b4 y- A+ c- T; f) l    index(find(index==v2))=v1;
    data(:,flag)=[];
    index(:,flag)=[];
4 R$ h" O" L( uend
result

" I4 a3 ?: d+ I

# e5 I8 w. [, k# c! N; m————————————————
* d6 h) s2 B6 b/ t6 B版权声明：本文为CSDN博主「wamg潇潇」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_29831163/article/details/89785681

7 v6 A' v- q8 K1 o- v! j, n% F