运筹学图与网络分析补例4.doc

运筹学图与网络分析补例
1、证明下列序列不可能是某个简单图的次的序列
(1)7,6,5,4,3,2;(2)6,6,5,4,3,2,1;(3)6,5,5,4,3,2,1
证(1)已知定理,而在此序列中为奇数,所以此序列不可能作为图的次的序列。或由已知定理:奇点的个数应为偶数,而在此序列里,奇点7、5、3为奇数个,,所以此序列不可能作为图的次的序列。
(2)由已知定理:奇点的个数应为偶数,而在此序列里,奇点5、3、1为奇数个,,所以此序列不可能作为图的次的序列。
(3)对于七个点的图,假定,并假设该图G为简单图,则存在于其它六个点的连线,与间存在边,而次为1,所以一定不与以外的其它点相连,因而与、以外的四个点个有一条线相连。
由于假设G(V,E)为简单图,则余下的中任意点(用表示)以确定存在,无。对于的该点来说,必与除以外的每一点都有连线,设。
由此推得,都同时与,即的次数至少是3,这与相矛盾。
故假设“是某个简单图的次的序列”不成立,即该图可能有环或多重边,该序列不是某个简单图的次的序列。
2、求最小支撑树(生成树)
例求右图的最小树
解 1)用破圈法:取一圈去掉,取一圈去掉,取一圈去掉,取一圈去掉
得到一棵支撑树
2)用避圈法:在中取权值最小的边有,从中任取一条;在中取权值最小的边;在中取权值最小的边有,从中任取一条;在中取权值最小的边;在中取权值最小的中任何一条,都会与已知边构成圈,故停止。
特点:破圈法始终连通,避圈法则是由可能不连通走向连通。
3、已知世界6大城市:Pe,Pa,T,M,N,L。试在下表所示交通网络的数据中确定最小树。
Pe
T
Pa
M
N
L
Pe
13
51
77
68
50
T
13
60
70
67
59
Pa
51
60
57
36
2
M
77
70
57
20
55
N
68
67
36
20
34
L
50
59
2
55
34
解将题设中的表用图表示
采用避圈法,寻找最小边的过程如下:
最后找到的构成最小支撑树如图所示
4、求右图从点到各点的最短路经
解首先在始点标以,然后在标以,由于
所以在标以,在标以,然后在标以。
由于
所以在标以,在标以,最后由于
所以在终点处应标以。所有点度获得了标号,反向追踪得到到的最短路为。长度为3。
5、有9个城市,其公路网如下图所示。弧旁边的数字是该段公路的长度,有一批货物从运到,问走哪条路最短?
解以表示到的弧上的距离权,则可以写出网络的距离矩阵,其中若到没有弧,则。若网络是无向网络,则距离矩阵为对称矩阵。
最短路问题可以这样描述:要找从到的通路,使全长为最短,即
由题设,有
将其列入下表
1
2
3
4
5
6
7
8
9
初始值
第1次迭代
0+3
0+
0+4
0+
0+
0+
0+
0+
4
第2次迭代
3+3
3+
3+2
3+3
3+
3+
3+
5
6
第3次迭代
4+
4+
4+
4+3
4+
4+
6
7
第4次迭代
5+
5+3
5+
5+
5+
6
7
第5次迭代
6+
6+
6+
6+5
7
11
第6次迭代
6+1
6+
6+

第7次迭代
7+2
7+2
9
在表中的第一行是初始值表示,对应距离矩阵的第一列。
以后的行是由上一行中的与的和,T行是从上两行中对应的元素中取最小的一个,相当于
每次迭代在行选最小的,用表示,以后对应的列不再进行计算,相当于从中去掉。根据上述迭代,得到的最短路为,。
6、用求右图中从到各点的最短路
解计算过程如表所示
点
0
1
2
0
0
0
0
0
3
4
1
1
1
1
0
-2
0
5
1
4
1
1
4
0
-3
2
2
2
2
2
3
0
-1
-1
-1
2
2
0
以列为例(,含无穷仅写一个)计算:,
,,被加数不动,
,。类推…..
故
用Warshall-Flod方法求该图任意两点间的最短路如下:
开始(k=0)作距离矩阵和序号矩阵,其中为网络的顶点数,
,为弧上的权数,A为网络的弧集。
第一步:时,中第行和第列元素保持与相应元素相同,其它元素按下式计算,并填入中:,相应地的元素按下式变化:
第二步:若存在,计算终止;否则,置;
第三步:当时,计算终止。若表示不存在从到的路;否则,记表示由到的最短路长,相应地,最短路线可由追溯找出。
;
;
例如由于为到的路径长,查