最小树与最小树形图(数学建模资料).ppt

网络优化
第3章最小树与最小树形图
Network Optimization
1
最小树问题的例子
例公路连接问题
某一地区有n个主要城市,现准备修建高速公路把这些城市连接起来, 使得从其中任何一个城市都可以经高速公路直接或间接到达另一个城市. 假定已经知道了任意两个城市i和j之间修建高速公路的成本(费用)wij (>0), 那么应任何决定在哪些城市间修建高速公路,使得总成本最小?
高速公路网正好构成这个完全图G的一个连通的支撑子图T.
为了使得总建设成本最小, 该子图必须是无圈的
无圈连通图称为树,上面这样一类问题称为最小树问题.
2
–定义
无圈连通图称为树(tree). 无圈图(即若干棵树的并)称为森林或者简称林(forest).
如果一个图的支撑子图是一棵树,则称这棵树为该图的支撑树或者生成树(spanning tree),并称支撑树中的弧为树弧(tree arc),而不属于支撑树中的弧为非树弧(nontree arc).
树是一类既简单而又非常重要的图形,在计算机科学、有机化学、电网络分析、最短连接及渠道设计等领域都有广泛的应用.
在本节及下一节中,我们假设所讨论的图与网络都是无向的.
3
–例
含6个顶点的树(非同构的):
共有6种
弧的条数= 节点数- 1
任何两个顶点之间存在唯一的一条路
4
- 树的等价定义
G=(N,E)为一个图,|N|=n,则下列命题等价:
G是一棵树;
G连通,且|E|=n-1;
G无圈,且|E|=n-1;
G的任何两个顶点之间存在唯一的一条路;
G连通,且将G的任何一条弧删去之后,该图成为非连通;
6) G无圈,且在G的任何两个不相邻顶点之间加入一条弧之后,该图正好含有一个圈.
5
- 最小树的定义
G=(N,E,W)为一个无向网络,W为权函数, 即W: E→R (这里R表示实数集合). G中权最小(大)的弧称为最小(大)弧.
如果H=(N1,E1)为G的一个子图,子图H的权定义为H所包含的所有弧的权之和,记为W(H),即W(H)= .
弧e =(i,j)上的权常记为W(e),We 或w(e),wij等
如果T*是G的一棵生成树,且对G的任何一棵生成树T都有 W( T* )≤W(T),则T*称为网络G的最小支撑树或者最小生成树(MST:minimum spanning tree),或者简称最小树.
图的最小树一般不唯一
6
- 最小树的应用一例
二维矩阵数据存贮问题
某些蛋白质的氨基酸序列差异不多,如果用二维矩阵的每一行记录一种蛋白质氨基酸序列,行与行之间的差异很小. 其中一种方法是只存贮其中一行作为参照行,再存贮行与行之间的一部分差异信息,使得我们可以在需要时根据参照行生成所有其它行的元素.
R1
R3
R2
R4
C13
C12
C24
一般地,给定差异信息cij,如何确定存贮哪些行之间的差异元素, 使得存贮空间尽可能少呢?这一问题可以用最小树问题来描述: 我们把矩阵每行作为一个节点构成一个完全图, 第i个节点对应于矩阵第i行,并令弧(i,j)上的权为cij. 对于存贮问题, 实际上只需要存贮一行的元素, 以及由该完全图的一棵支撑树所对应的差异元素. 最小树就对应于最优的存贮方案.
7
-
生成树T*是最小树的充要条件是:对T*中的任何一条弧,将该弧从T*中删除后形成的割中,该弧为最小弧.
最小树的“割最优条件”
T*
必要性:很容易用反证法证明。
e
e’
设w(e) > w(e’),令T’= T* - e + e’,则w(T* ) > w(T’)
8
T*
e
-
*是生成树并满足定理中的条件,但不是最小树,设最小树为T0. 记eT*\ T0, 将e从T*中删除后产生一个割.
将e加入T0后必然产生一个圈,该圈必然包括割中一条与e不同的弧e’,由假设,w(e)  w(e’).
最小树的“割最优条件”
重复这一过程,最后可以得到T*也是最小树
e’
由T0为最小树,w(e)  w(e’), 则w(e) = w(e’) ,因此, T1 = T0 - e’+ e也是最小树,与 T*有更多的公共弧
9
-
T*
生成树T*是最小树的充要条件是:对属于G但不属于T*的任何一条弧,将该弧加入T*后形成的圈中,该弧为最大弧.
必要性:很容易用反证法证明。
e’
e
若w(e) < w(e’),令T’= T* - e’+