文档详情

运筹学章图与网络分析.ppt

发布:2017-11-16约9.04千字共139页下载文档
文本预览下载声明
哥尼斯堡七桥问题 哥尼斯堡(现名加里宁格勒)是欧洲一个城市,Pregei河把该城分成两部分,河中有两个小岛,十八世纪时,河两边及小岛之间共有七座桥,当时人们提出这样的问题:有没有办法从某处(如A)出发,经过各桥一次且仅一次最后回到原地呢? 有7个人围桌而坐,如果要求每次相邻的人都与以前完全不同,试问不同的就座方案共有多少种? 用顶点表示人,用边表示两者相邻,因为最初任何两个人都允许相邻,所以任何两点都可以有边相连。 得到第一次就座方案是(1,2,3,4,5,6,7,1),继续寻求第二次就座方案时就不允许这些顶点之间继续相邻,因此需要从图中删去这些边。 得出第二次就座方案是(1,3,5,7,2,4,6,1),那么第三次就座方案就不允许这些顶点之间继续相邻,只能从图中删去这些边。 引论 图的用处 某公司的 组织机构设置图 根据破圈法和避圈法两种方式得到了图的两个不同的生成树,由此可以看到连通图的生成树不是唯一的。 W12 =11+5=16 W13 =11+5+6=22 W14 =11+5+6+8=30 W15 =11+5+6+8+11=41 W16 =11+5+6++8+11+18=59 2 3 7 1 8 4 5 6 6 1 3 4 10 5 2 7 5 9 3 4 6 8 2 X={1,2,4} min {c13,c23,c25,c47}=min {0+3,2+6,2+5,1+2}=min {3,8,7,3}=3 X={1,2,4,6}, p6=3 p2=2 p4=1 p1=0 p6=3 2 3 7 1 8 4 5 6 6 1 3 4 10 5 2 7 5 9 3 4 6 8 2 X={1,2,4,6} min {c23,c25,c47,c67}=min {2+6,2+5,1+2,3+4}=min {8,7,3,7}=3 X={1,2,4,6,7}, p7=3 p2=2 p4=1 p1=0 p6=3 p7=3 2 3 7 1 8 4 5 6 6 1 3 4 10 5 2 7 5 9 3 4 6 8 2 X={1,2,4,6,7} min {c23,c25,c75,c78}=min {2+6,2+5,3+3,3+8}=min {8,7,6,11}=6 X={1,2,4,5,6,7}, p5=6 p2=2 p4=1 p1=0 p6=3 p7=3 p5=6 2 3 7 1 8 4 5 6 6 1 3 4 10 5 2 7 5 9 3 4 6 8 2 X={1,2,4,6,7} min {c23,c53,c58,c78}=min {2+6,6+9,6+4,3+8}=min {8,15,10,11}=8 X={1,2,3,4,5,6,7}, p3=8 p2=2 p4=1 p1=0 p6=3 p7=3 p5=6 p3=8 2 3 7 1 8 4 5 6 6 1 3 4 10 5 2 7 5 9 3 4 6 8 2 X={1,2,3,4,6,7} min {c38,c58,c78}=min {8+6,6+4,3+7}=min {14,10,11}=10 X={1,2,3,4,5,6,7,8}, p8=10 p2=2 p4=1 p1=0 p6=3 p7=3 p5=6 p3=8 p8=10 2 3 7 1 8 4 5 6 6 1 3 4 10 5 2 7 5 9 3 4 6 8 2 X={1,2,3,4,6,7,8} 1到8的最短路径为{1,4,7,5,8},长度为10。 p2=2 p4=1 p1=0 p6=3 p7=3 p5=6 p3=8 p8=10 求从V1 到 V8 的最短路线。 V1 V2 V3 V4 V5 V6 V7 V8 ① P=0 T=+∞ T=+∞ T=+∞ T=+∞ T=+∞ T=+∞ T=+∞ ② P=T=3 T=+∞ T=7 T=+∞ T=+∞ T=+∞ T=+∞ ? ③ T=6 T=7 P=T=5 T=+∞ T=+∞ T=+∞ ? ④ P=T=6 T=6 ? T=8 T=+∞ T=+∞ ? ? ⑤ P=T=6 ? T=8 T=9 T=12 ? ? ? ? ⑥ P=T=8 T=10 T=10 ? ? ? ? ? ⑦ P=T=9 T=11 再无其它T 标号,所以 T(V8)=P(V8)=10; min L(μ)=10 ⑧ P=T=10 由此看到,此方法不仅求出了从V1 到 V8 的最短路长,同时也求出了从V1 到 任意一点 的最短路长。将从V1 到 任一点的最短路权标在图上,即可求出从V1
显示全部
相似文档