数模竞赛中的图论问题

数模竞赛中的图论问题上海海事大学丁颂康[e-mail]一.图上的问题案例一钢管的订购和运输（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.分析和建模购运费用—最短路问题(shortestpath)Dijkstra算法和Floyd-Warshell算法(标号法和矩阵运算法)解决实际问题的局限性方案选择—线性规划\二次规划(略)案例二扫雪车(SnowPlowingMCM1990-B）1.问题的提出上图是WicomicoCounty(StateofMaryland)的公路图.一场大雪以后,需要出动扫雪车进行清扫.如果道路两边需要来回各清扫一遍,并且出动两辆扫雪车,应该如何安排任务?2.分析和建模Eulertour和Euler迹的Fleury算法除非没有别的选择,不走剩下图的割边.中国邮递路线问题—管梅谷1960(ChinesePostmanProblem)nigsbergoKEuler问题和边的行遍性七桥问题3.原问题的求解单车单程(等同于邮路问题)单车双程(有向Euler图)双车双程(边的分配→单车双程)(简化:原图中去掉尽可能大的Euler子图)案例三通讯网络的最小Steiner树(MCM1991-B)一.问题的提出9个通讯站位于以下坐标点处:要设计一个连接这9个通讯站的局部网络,使总费用最省.(假定连线费用与距离成正比).)3,10()0,25()7,35()11,23()25,33()20,20()24,16()20,5()51,0(ihgfedcba二.问题的分析和建模最小连接问题:树—连通无圈图.树的性质:1.任意两点间存在唯一的路;2.边数等于点数减1;3.任意去掉一条边,树就变得不连通;4.任意去掉一个非悬挂点,树就变得不连通;5.任意添加一条边,就可得到唯一的圈.注:3,4两条性质说明,就连通的意义而言,树具有极小性.子图—生成子图—生成树最小生成树最小生成树的Kruskal算法和管梅谷算法—避圈和破圈三角形中到三个顶点距离之和最小的点—Steiner点推广—Steiner树直角距离竞赛中的其它图论问题：灾情巡视路线（1998CMCM-B）——点的行遍性乘公交，看奥运（2007CMCM-B）——最短路算法交巡警服务平台的设置与调度（2011-B）——最短路算法二.可以用图论方法讨论的问题案例四锁具装箱(CMCM1994-B）1.问题的提出一种弹子锁的钥匙有5个槽。每个槽的高度可以用1—6中的某个数表示。工艺及其它原因，5个槽的高度还有两个限制：1）至少有3个不同的数；2）相邻两槽的高度差不能为5。满足以上条件的不同锁具称为一批。两把锁能够互开的条件是:5个槽的高度有4个相同另一个槽的高度差1.问题是:1.每一批锁共有多少把？2.如何尽可能避免同一顾客买到的锁具互开?3.图论中的相关结果二分图二分图完美对集的存在性—Hall定理最大独立集—Konig定理(1931):Inabipartitegraph,thenumberofedgesinamaximummatchingisequaretothenumberofverticesinaminimumcovering.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)邻接矩阵（adjecencymatrix）)(ijaA1ija当且仅当有弧从iv指向jv000100100100110000001011111000111010A2.分析与建模得分向量逐级得分向量可以证明:其中是全1向量TS)1,2,2,3,3,4(TS)3,4,3,9,5,8(2TS)9,21,7,61,01,51(3TS)61,25,12,23,82,83(4TS)23,84,14,78,26,09(5TS)78,911,08,391,121,381(6JASkkJ0010110011111002003320102102003212002A3320103330210021226316001023223125223A6316009636106650314169666671537694754A4169661047156615941210191821515921159124127211613945A191821515923192714211514513241212634529371452914173613125029264817136AkA的第i,j个元素是的长度为k的有向路的条数。jivv定理1假设A是点数不小于5的双向连通竞赛图D的邻接矩阵。那么,。其中,d是D的有向直径。定理2（Perron-Frobenius定理）本原矩阵A的最大特征根r是一个正的实数。进而有其中，s是A对应于r的正特征向量。上例中,,点数小于5或非双向连通的情况.03dAsJrAkk)(lim232.2rTs)104.,150.,113.,231.,164.,238(.谢谢2013.9.7