数模竞赛中图论问题.ppt

《数模竞赛中图论问题.ppt》由会员分享，可在线阅读，更多相关《数模竞赛中图论问题.ppt（24页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数模竞赛中的图论问题 上海海事大学 丁颂康一.图上的问题 案例一 钢管的订购和运输（CMCM00-B）1.问题的提出 铁路运价(万元/单位)1000以上每增加1-100运价增加5万元 公路运价1单位钢管每0.1万元(不足1部分按1计算)里 程()300301-350351-400401-450451-500运 价2023262932里 程()501-600601-700701-800801-900900-1000运 价37445055602.分析和建模 购运费用最短路问题(shortest path)Dijkstra算法和Floyd-Warshell算法 (标号法和矩阵运算法)解决实际问题的局

2、限性 方案选择线性规划二次规划(略)案例二 扫雪车(Snow Plowing MCM1990-B）1.问题的提出 上图是上图是Wicomico County (State of Maryland)Wicomico County (State of Maryland)的公路图的公路图.一场大雪以后,需要出动扫雪车进行清扫.如果道路两边需要来回各清扫一遍,并且出动两辆扫雪车,应该如何安排任务?2.分析和建模 Euler tour和 Euler 迹的Fleury算法 除非没有别的选择,不走剩下图的割边.中国邮递路线问题管梅谷1960 (Chinese Postman Problem)EulerEul

3、er问题和边的行遍性问题和边的行遍性七桥问题七桥问题3.原问题的求解 单车单程(等同于邮路问题)单车双程(有向Euler图)双车双程(边的分配单车双程)(简化:原图中去掉尽可能大的Euler子图)案例三 通讯网络的最小Steiner树(MCM1991-B)一.问题的提出n 9个通讯站位于以下坐标点处:n 要设计一个连接这9个通讯站的局部网络,使总费用最省.(假定连线费用与距离成正比).二.问题的分析和建模 最小连接问题:树连通无圈图.树的性质:1.任意两点间存在唯一的路;2.边数等于点数减1;3.任意去掉一条边,树就变得不连通;4.任意去掉一个非悬挂点,树就变得不连通;5.任意添加一条边,就可

4、得到唯一的圈.注:3,4两条性质说明,就连通的意义而言,树具有极小性.n 子图生成子图生成树n 最小生成树n 最小生成树的Kruskal算法和管梅谷算法 避圈和破圈n 三角形中到三个顶点距离之和最小的点 Steiner点 n 推广 Steiner树n 直角距离n竞赛中的其它图论问题：灾情巡视路线（1998 CMCM-B）点的行遍性 乘公交，看奥运（2007 CMCM-B）最短路算法 交巡警服务平台的设置与调度（2011-B）最短路算法二.可以用图论方法 讨论的问题案例四 锁具装箱(CMCM1994-B）1.问题的提出 一种弹子锁的钥匙有5个槽。每个槽的高度可以用16中的某个数表示。工艺及其它原

5、因，5个槽的高度还有两个限制：1）至少有3个不同的数；2）相邻两槽的高度差不能为5。满足以上条件的不同锁具称为一批。两把锁能够互开的条件是:5个槽的高度有4个相同另一个槽的高度差1.问题是:1.每一批锁共有多少把？2.如何尽可能避免同一顾客买到的锁具互开?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

6、.2.分析与建模 一批锁具的数量一批锁具的数量组合计数组合计数 (略略)互开的条件互开的条件 案例五 足球队排名次(SMCM1993-B)1.问题的提出 T1T2T3T4T5T6T7T8T9T10T11T12T1-0:12:22:03:11:00:10:21:01:1-T2-2:00:01:12:11:10:02:00:2-T3-4:22:13:01:00:11:00:1-T4-2:30:10:52:10:10:1-T5-0:1-1:00:0T6-T7-1:02:13:13:12:0T8-0:11:13:10:0T9-3:01:01:0T10-1:02:0T11-1:2 竞赛图(tournament)邻接矩阵（adjecency matrix）当且仅当有弧从 指向2.分析与建模 得分向量 逐级得分向量 可以证明:其中 是全1向量 的第i,j个元素是 的长度为k的有向路的条数。定理1 假设 A是点数不小于5的双向连通竞赛图D的邻 接矩阵。那么,。其中,d是D的有向直径。定理2（Perron-Frobenius定理定理）本原矩阵A的最大特征 根r是一个正的实数。进而有 其中，s是A对应于r的正特征向量。上例中,点数小于5或非双向连通的情况.谢 谢