数模竞赛中的图论问题

1、数模竞赛中的图论问题,上海海事大学 丁颂康 ,一.图上的问题,案例一 钢管的订购和运输（CMCM00-B）,1.问题的提出,铁路运价(万元/单位) 1000以上每增加1-100运价增加5万元 公路运价1单位钢管每0.1万元(不足1部分按1计算),2.分析和建模,购运费用最短路问题(shortest path) Dijkstra算法和Floyd-Warshell算法 (标号法和矩阵运算法) 解决实际问题的局限性 方案选择线性规划二次规划(略),案例二 扫雪车 (Snow Plowing MCM1990-B）,1.问题的提出,上图是Wicomico County (State of Marylan

2、d) 的公路图. 一场大雪以后,需要出动扫雪车进行清扫. 如果道路两边需要来回各清扫一遍, 并且出动两辆扫雪车, 应该如何安排任务?,2.分析和建模,Euler tour和 Euler 迹的Fleury算法 除非没有别的选择,不走剩下图的割边. 中国邮递路线问题管梅谷1960 (Chinese Postman Problem),Euler问题和边的行遍性,七桥问题,3.原问题的求解,单车单程 (等同于邮路问题) 单车双程 (有向Euler图) 双车双程 (边的分配单车双程) (简化:原图中去掉尽可能大的Euler子图),案例三 通讯网络的最小Steiner树 (MCM1991-B) 一.问题的

3、提出 9个通讯站位于以下坐标点处: 要设计一个连接这9个通讯站的局部网络,使总费用最省. (假定连线费用与距离成正比).,二.问题的分析和建模 最小连接问题: 树连通无圈图. 树的性质: 1.任意两点间存在唯一的路; 2.边数等于点数减1; 3.任意去掉一条边,树就变得不连通; 4.任意去掉一个非悬挂点,树就变得不连通; 5.任意添加一条边,就可得到唯一的圈. 注:3,4两条性质说明,就连通的意义而言,树具有极小性.,子图生成子图生成树 最小生成树 最小生成树的Kruskal算法和管梅谷算法 避圈和破圈 三角形中到三个顶点距离之和最小的点 Steiner点 推广 Steiner树 直角距离,竞

4、赛中的其它图论问题： 灾情巡视路线（1998 CMCM-B） 点的行遍性 乘公交，看奥运（2007 CMCM-B） 最短路算法 交巡警服务平台的设置与调度（2011-B） 最短路算法,二.可以用图论方法 讨论的问题,案例四 锁具装箱(CMCM1994-B）,1.问题的提出 一种弹子锁的钥匙有5个槽。每个槽的高度可以用1 6中的某个数表示。 工艺及其它原因， 5个槽的高度还有两个限制： 1）至少有3个不同的数； 2）相邻两槽的高度差不能为5。 满足以上条件的不同锁具称为一批。 两把锁能够互开的条件是: 5个槽的高度有4个相同 另一个槽的高度差1. 问题是: 1.每一批锁共有多少把？ 2.如何尽可

5、能避免同一顾客买到的锁具互开?,3.图论中的相关结果 二分图 二分图完美对集的存在性Hall定理 最大独立集Konig定理(1931): In a bipartite graph, the number of edges in a maximum matching is equare to the number of vertices in a minimum covering.,2.分析与建模 一批锁具的数量组合计数 (略) 互开的条件,案例五 足球队排名次(SMCM1993-B) 1.问题的提出,竞赛图 (tournament),邻接矩阵 （adjecency matrix）,当且仅当有弧从,指向,2.分析与建模,得分向量 逐级得分向量 可以证明: 其中 是全1向量,的第i,j个元素是 的长度为k的有向路的条数。,定理1 假设 A是点数不小于5的双向连通竞赛图D的邻 接矩阵。那么, 。其中, d是D的有向直径。 定理2 （Perron-Froben