《复旦大学计算机科学与工程系 吴永辉 离散数学 图论应用》由会员分享，可在线阅读，更多相关《复旦大学计算机科学与工程系 吴永辉 离散数学 图论应用（84页珍藏版）》请在金锄头文库上搜索。
1、图论应用2004数学建模竞赛辅导 复旦大学计算机科学与工程系 吴永辉 博士 2004年7月12日基础知识n离散数学（图论）n程序设计语言n数据结构n算法设计与分析主要参考书目1 周咏基, 王建德. 金牌之路竞赛解题指导. 陕西师范大学出版社. 2001. 2 吴文虎, 王建德. 实用算法的分析与程序设计. 电子工业出版社. 1998. 3 吴文虎, 王建德. 图论的算法与程序设计. 清华 大学出版社. 1997. 4 朱洪等. 离散数学教程. 上海科技文献出版社. 1966. 5 雷功炎. 数学模型讲义. 北京大学出版社. 2000.6 Thomas H. Coremen, etc. Intr
2、oduction to Algorithm（算法导论）. 高等教育出版社， The MIT Press. 20027 Kenneth H. Rosen. Discrete Mathematics and its Applications（离散数学及其应用）. (4th Edition). 2002. 机械工业出版社, McGraw-Hill. (中、英文版) 8 Bela Bollobas. Modern Graph Theory (现代图 论). 科学出版社 顶点相邻当且仅当正方体有两个相对 的面分别桌的是这两种颜色；令Gi表示 正方体i的着色方式，i=1, 2, 3, 4； G=G1 G2
3、 G3 G4。n2）算法分析n 存在可行方案的充要条件是G中存 在两个生成子图，均含4条边，且标码 为1，2，3，4的边各只出现一次，每 个顶点关联两条边。n 先按G调整好棱柱的前后两个 侧面，使每个侧面都具有不同的颜色， 如下图1所示；再按G调整左右两个侧面 ，前后侧面颜色不变，使左右两个侧面 的颜色如下图2所示。前 后 左 右G R G YR B Y BY G B RB Y R G6 关键路径n1）PERT ( Program Evaluation and Review Technique ). 计划评审技术, 1956年。n2）PERT图 设D是n个结点的有向简单带权图，若满足： （1）
4、D中无回路； （2）D中有一个顶点的入度为0，记为v1，称v1为发点 ，有一个顶点的出度为0，记为vn，称vn为收点； （3）任意的vV-v1, vn，则v在某条从v1到vn的路径上 ，则称D是PERT图。n 在PERT图中，每条边表示一道工序 或一种活动，若有向边(vi, vj), (vj, vk)相邻 ，则表示工序(vj, vk)必须在(vi, vj)结束后 才能开始。n viV, vi表示一种状态，它表示关 联到它的工序都结束后，关联于它的工 序才能开始。n v1表示工程开始n vn表示工程结束。n3）关键状态，关键工序/关键活动在PERT图中的关键路径是从发点v1到收 点vn的最长（按
5、权计算）的路径。处于关键 路径上的顶点称为关键状态，处在关键路径 上的边称为关键工序或关键活动。n要使工期缩短，缩小关键路径上边的权。n4）最早完成时间/最晚完成时间n最早完成时间设PERT图为有向图D，任意的viV(D)， 称从发点v1沿最长的路到达vi所需要的时间为vi 的最早完成时间，记作TE(vi)。TE(vi)是以vi为起点的各工序的最早可能 开工时间，因而称为vi的最早完成时间，它是v1 到达vi的最长路径的权。n最晚完成时间在保证收点vn的最早完成时间TE(vn) 不增加的条件下，从v1最迟到达vi所需要 的时间，称为vi的最晚完成时间，记作 TL(vi)。TL(vi)为TE(v
6、n)与vi沿最长（按权计 算）路径到达vn所需时间之差，TL(vi)是 关联于vi的各道工序所允许的最迟开工时 间。n5）缓冲时间/松弛时间TL(vi)-TE(vi)为vi的缓冲时间或松弛 时间，记为TS(vi)。TS(vi)0，i=1, 2, , n.n定理：TS(vi)=0当且仅当vi处在关键路径上 。三、图论难题思考n1 图的基本概念（遍历）拯救大兵瑞恩n2 网络流标号法航天实验家园1 拯救大兵瑞恩n问题背景1944年，特种兵麦克接到国防部 的命令，要求立即赶赴太平洋上的一个 孤岛，营救被敌军俘虏的大兵瑞恩。瑞 恩被关押在一个迷宫里，迷宫地形复杂 ，但是幸好麦克得到了迷宫的地形图。迷宫的
7、外形是一个长方形，其在南北方向被划分为N行 ，在东西方向被划分为M列，于是整个迷宫被划分为N*M 个单元。我们用一个有序数对（单元的行号，单元的列号 ）来表示单元位置。南北或东西方向相邻的两个单元之间 可以互通，或者存在一扇锁着的门，又或者存在一堵不可 逾越的墙。迷宫中有一些单元存放着钥匙，并且所有的门 被分为P类，打开同一类的门的钥匙相同，打开不同类的 门的钥匙不同。大兵瑞恩被关押在迷宫的东南角，即（N,M）单元里， 并已经昏迷。迷宫只有一个入口，在西北角，也就是说， 麦克可以直接进入(1,1)单元。另外，麦克从一个单元移动 到另一个相邻单元的时间为1，拿取所在单元的钥匙的时 间以及用钥匙开
8、门的时间忽略不计。你的任务是帮助麦克以最快的方式抵达瑞恩所在单元 ，营救大兵瑞恩。 n输入输出结构n输入：n第一行是三个整数，依次表示N,M,P的值；n第二行是一个整数K，表示迷宫中门和墙的总个数；n第I+2行（1=1时，表示(Xi1,Yi1)单元与(Xi2,Yi2)单元之间有一扇第Gi类的门 ，当Gi=0时，表示(Xi1,Yi1)单元与(Xi2,Yi2)单元之间有一堵不可逾越的 墙；n（其中，|Xi1-Xi2|+|Yi1-Yi2|=1，0=Gi=P）n第K+3行是一个整数S，表示迷宫中存放的钥匙总数；n第K+3+J行(1=J=S)，有3个整数，依次为Xi1,Yi1,Qi：表示第J把钥匙 存放
9、在(Xi1,Yi1)单元里，并且第J把钥匙是用来开启第Qi类门的。（其 中1=Qi=P）n注意：输入数据中同一行各相邻整数之间用一个空格分隔。n输出：n输出文件只包含一个整数T，表示麦克营救到大兵瑞恩的最短时间的值，若不存在可行的营救方案则输出-1。 n网络流标号法n1 航天实验n2 家园n1 航天实验NASA正在为航天飞行计划一系列的太空 飞行, 在每次飞行中必须决定进行何种商业性实验 和配载何种仪器设备. S教授正在研究这一问题. 对 每次飞行NASA考察一个实验集合E=e1, , en, 并且实验ej的商业赞助人已同意为该实验的结果向 NASA支付pj美圆. 实验使用的全部仪器为集合 I
10、=I1, , In; 每个实验室所需要用到的仪器为子集 rjI.运送仪器Ik的运费为ck美圆。S教授的任务就是找一个有效算法以确定 在某一次指定的飞行中要进行哪些实验并运送哪 些仪器才能使净收益（进行实验所获得的全部收 入与运送仪器的全部费用的差额）最大。n输入输出结构n2 家园 问题背景由于人类对自然的疯狂破坏，人们意识到 在大约2300年之后，地球不能再居住了，于 是在月球上建立了新的绿地，以便在需要时 移民。令人意想不到的是，2177年冬由于未 知的原因，地球环境发生了连锁崩溃，人类 必须在最短的时间内迁往月球。现有n个太空站处于地球与月球之间（编号 1n），m艘公共交通太空船在其中来回
11、穿梭，每 个太空站Si可容纳无限的人，每艘太空船pi只可容 纳Hpi人。对于每一艘太空船pi，将周期性地停靠 一系列的太空站（Si1,Si2Sir），如：（1，3，4 ）表示停靠太空站1 3 4 1 3 4 1 3 4 。 任一艘太 空船从任一个太空站驶往另一个任意的太空站耗 时为1。人只能在太空船停靠太空站（或地球、月 球）时上船或下船。初始时的人全在地球上，太 空船全在初始站（太空船pi处于Si1），目标是让 所有的人尽快地全部转移到月球上。 n输入：文件第一行为三个正整数 n（太空站个数）、 m（太 空船个数）、 k（需要运送的地球上的人的个数），其 中 1=m=13, 1=n=20, 1=k=50。接下来的n行给出了太空船的信息，第i+1行说明太 空船pi，此行第一个数表示pi可容纳的人数Hpi，第二 个数表示pi停靠一个周期的太空站个数r，1=r=n+2, 随后r个数便是停靠的太空站的编号(Si1,Si2,Sir), 地 球用0表示，月球用-1表示。0时刻时，所有太空船都在 初始站，随后开始运行，在时刻1，2，3等正点时刻 各艘太空船停靠相应的太空站，即人只有在0,1,2等 正点时刻才能上下太空船。 n输出：n 文件只有一个数，若问题有解，输出 完成全部人员安全转移的时刻，否则输 出0。
