(精品)数模讲座之数模竞赛中的图论问题(丁颂康).ppt

数模竞赛中的图论问题 上海海事大学丁颂康一.图上的问题 案例一 钢管的订购和运输（CMCM00-B）1.问题的提出 铁路运价铁路运价(万元万元/单位单位)1000 1000以上每增加以上每增加1-1001-100运价增加运价增加5 5万元万元 公路运价公路运价1 1单位钢管每单位钢管每0.10.1万元万元(不足不足1 1部分按部分按1 1计算计算)里里 程程 ()300300301-350301-350351-400351-400401-450401-450451-500451-500运运 价价20202323262629293232里里 程程 ()501-600501-600601-700601-700701-800701-800801-900801-900900-1000900-1000运运 价价373744445050555560602.分析和建模 购运费用最短路问题(shortest path)DijkstraDijkstra算法和算法和Floyd-Floyd-WarshellWarshell算法算法 (标号法和矩阵运算法标号法和矩阵运算法)解决实际问题的局限性 方案选择线性规划二次规划(略)案例二 扫雪车(Snow Plowing MCM1990-B）1.问题的提出 上上图图是是Wicomico County (State of Maryland)Wicomico County (State of Maryland)的公路图的公路图.一场大雪以后,需要出动扫雪车进行清扫.如果道路两边需要来回各清扫一遍,并且出动两辆扫雪车,应该如何安排任务?2.分析和建模 Euler tourEuler tour和和 Euler Euler 迹的迹的FleuryFleury算法算法 除非没有别的选择除非没有别的选择,不走剩下图的割边不走剩下图的割边.中国邮递路线问题中国邮递路线问题管梅谷管梅谷19601960 (Chinese Postman Problem)(Chinese Postman Problem)EulerEuler问题和边的行遍性问题和边的行遍性七桥问题七桥问题3.原问题的求解 单车单程(等同于邮路问题)单车双程(有向Euler图)双车双程(边的分配单车双程)(简化:原图中去掉尽可能大的Euler子图)二.可以用图论方法讨论的问题 案例三 锁具装箱(CMCM1994-B)(CMCM1994-B)1.问题的提出 一种弹子锁的钥匙有一种弹子锁的钥匙有5 5个槽。每个槽的高度可以用个槽。每个槽的高度可以用116 6中的某个数表示。中的某个数表示。工艺及其它原因，工艺及其它原因，5 5个槽的高度还有两个限制：个槽的高度还有两个限制：1 1）至少有至少有3 3个不同的数；个不同的数；2 2）相邻两槽的高度差不能为相邻两槽的高度差不能为5 5。满足以上条件的不同锁具称为一批。满足以上条件的不同锁具称为一批。两把锁能够互开的条件是两把锁能够互开的条件是:5 5个槽的高度有个槽的高度有4 4个相同个相同另一个槽的高度差另一个槽的高度差1 1.问题是问题是:1.1.每一批锁共有多少把？每一批锁共有多少把？2.2.如何尽可能避免同一顾客买到的锁具互开如何尽可能避免同一顾客买到的锁具互开?3.图论中的相关结果 二分图二分图 二分图完美对集的存在性二分图完美对集的存在性HallHall定理定理 最大独立集最大独立集KonigKonig定理定理(1931):(1931):In a bipartite graph,the number of edges in a In a bipartite graph,the number of edges in a maximum matching is maximum matching is equareequare to the number of vertices to the number of vertices in a minimum covering.in a minimum covering.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 1向量向量 的第i,j个元素是 的长度为k的有向路的条数。定理1 假设 A是点数不小于5的双向连通竞赛图D的邻接矩阵。那么,。其中,d是D的有向直径。定理2（Perron-Frobenius定理定理）本原矩阵A的最大特征根r是一个正的实数。进而有 其中，s是A对应于r的正特征向量。上例中,点数小于5或非双向连通的情况.谢 谢2007.9