数学建模——最小树.ppt

最小树
1
最小树问题的例子
例公路连接问题
某一地区有n个主要城市,现准备修建高速公路把这些城市连接起来, 使得从其中任何一个城市都可以经高速公路直接或间接到达另一个城市. 假定已经知道了任意两个城市i和j之间修建高速公路的成本(费用)wij (>0), 那么应任何决定在哪些城市间修建高速公路,使得总成本最小?
高速公路网正好构成这个完全图G的一个连通的支撑子图T.
为了使得总建设成本最小, 该子图必须是无圈的
无圈连通图称为树,上面这样一类问题称为最小树问题.
2
1树的基本概念
定义1 无圈连通图称为树(tree). 无圈图(即若干棵树的并)称为森林.
如果一个图的支撑子图是一棵树,则称这棵树为该图的支撑树或者生成树(spanning tree),并称支撑树中的边为树边,而不属于支撑树中的边为非树边.
树是一类既简单而又非常重要的图形,在计算机科学、有机化学、电网络分析、最短连接及渠道设计等领域都有广泛的应用.
3
例1 含6个顶点的树(非同构的):
共有6种
4
引理
G=(N,E)为一个图,|N|=n,则下列命题等价:
1)G是一棵树;
2)G连通,且|E|=n-1;
3)G无圈,且|E|=n-1;
4)G的任何两个顶点之间存在唯一的一条路;
5)G连通,且将G的任何一条边删去之后,该图成为非连通图;
6)G无圈,且在G的任何两个不相邻顶点之间加入一条弧之后,该图正好含有一个圈.
5
最小树
定义2 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
最小树的应用一例
例2 二维矩阵数据存贮问题
某些蛋白质的氨基酸序列差异不多,如果用二维矩阵的每一行记录一种蛋白质氨基酸序列,行与行之间的差异很小. 其中一种方法是只存贮其中一行作为参照行,再存贮行与行之间的一部分差异信息,使得我们可以在需要时根据参照行生成所有其它行的元素.
R1
R3
R2
R4
C13
C12
C24
一般地,给定差异信息cij,如何确定存贮哪些行之间的差异元素, 使得存贮空间尽可能少呢?这一问题可以用最小树问题来描述: 我们把矩阵每行作为一个节点构成一个完全图, 第i个节点对应于矩阵第i行,并令弧(i,j)上的权为cij. 对于存贮问题, 实际上只需要存贮一行的元素, 以及由该完全图的一棵支撑树所对应的差异元素. 最小树就对应于最优的存贮方案.
7
最小树算法
算法开始时假设某支撑子图T 的边集合为空集;
算法运行过程中不断将一些边加入到子图中, 并且每次加入T 中的边就会成为最后找到的最小树的一员,而不会再从T 中退出.
贪婪算法(Greedy Algorithm):
8
基本思想:每次将一条权最小的弧加入子图T 中,并保证不形成圈. (避圈法)
如果当前弧加入后不形成圈, 则加入这条弧, 如果当前弧加入后会形成圈, 则不加入这条弧, 并考虑下一条弧.
STEP0. 令i=1, j=0, T=.把G的边按照权由小到大排列,即
;
Kruskal 算法(1956 )
STEP1. 判断T {ei}是否含圈. 若含圈, 转STEP2, 否则转STEP3.
STEP2. 令i=i+1. 若i  m,转STEP1;否则结束,此时G不连通,所以没有最小树.
STEP3. 令T=T {ei}, j =j+ j=n-1, 结束,T是最小树; 否则转STEP1.
正确性:圈最优条件
9
Prim 算法(1957)
基本思想:不断扩展一棵子树T=(S,E0),直到S包括原网络的全部顶点,得到最小树 T. (边割法)
每次增加一条边,使得这条边是由当前子树节点集S及其补集所形成的边割的最小边.
STEP0. 设v为N的任意一个顶点,令S={v},E0= 。
STEP1. 若S=N,结束,T=(S,E0)为最小树;否则转STEP2.
STEP2. 若= ,则G不连通,结束;否则,设
其中
令转STEP1.
正确性:割最优条件
10