离散数学实验.doc

文档介绍：精品文档，仅供学习与交流，如有侵权请联系网站删除
【精品文档】第 1 页
实验一 油管铺设
实验准备
最小生成树问题，求最小生成树的Prim算法
实验目的
运用最小生成树思想和求最小生成树程序解决实际问题
实验过程
八口海上油井相互间距离如下表，其中1号井离海岸最近，为5km。问从海岸经1号井铺设油管把各井连接起来，怎样连油管长度最短（为便于检修，油管只准在油井处分叉）？
从～到
2
3
4
5
6
7
8
1







2






3





4




5



6


7

实验二 最短路问题
实验准备
图的邻接矩阵，求最短路的 Dijkstra算法
实验目的
运用最短路思想和求最短路程序解决实际问题
实验过程
某建筑公司签订了一项合同，要为一家制造公司建造一座新的加工厂。合同规定工厂的完工期限为12个月。要是工厂不能在一年内完工，就要赔款，因此建筑公司认真分析，找出建筑工厂必须完成的各道工序和这些工序之间的先后关系，并估计出它们延续的时间，如下表所示。为建筑公司制定工程完工计划提供理论依据。
工序（事项）
估计周数
紧前事项
1 平整土地
4
无
2 打桩
1
1
3 运进钢材
3
无
4 运进混凝土
2
无
5 运进木料
2
无
6 运进水管和电器材料
1
无
7 浇注地基
7
2,3,4
8 焊接钢梁
15
3,7
9 安装生产设备
5
7,8
10 分隔办公室
10
5,7,8
11 安装水电和电器
11
6,8,10
12 装饰墙壁
5
8,10,11
实验三