例子
• 6个同学：姚金宇，李金宇，姚峰宏，陈峰宏
姚金宇 姚峰宏 姚金宇 李金宇 陈峰宏 陈峰宏 姚峰宏 李金宇
例子
• 4个同学：陈峰宏，囧峰宏，罗睿辞，廖叶子
陈峰宏 囧峰宏 陈峰宏 囧峰宏 罗睿辞 罗睿辞 廖叶子 廖叶子
• 罗睿辞同学想和廖叶子同学坐同一船是不行的，因为 他们不同名也不同姓
建模
考虑这样一个值：k’=max {bn} - L1，1<=n<L1,(b0=0, 不考虑) L1是最短的木棍，故k’>0. ⑴ k’不属于任何Si集合,否则与k’是某个S中最小元。 即k’不能被小木棍拼出。
∈ ⑵ 对任意L>k’,设L Sp，L+L1>max{bn}>=bp 故L>bpL1 ≡
而L
bp (mod p) 所以 L>=bp，所以L一定能够被拼出
c 12 a 3 g 2 9 4 8 9 9 6 5 20 1 e 22 5 3 f b d 15 11 2
考虑顶点b到顶点 的路径 考虑顶点 到顶点g的路径 到顶点
问题重述
• 加入步行的因素,即任意两个车站之间人都 可能通过步行到达,并给出步行的时间代价.
20 7 a 6 c
加入步行的路径 并给定权值
7 a 9 5 b(8) c
3
与经典最短路径问题比较
• 考虑a经过b到c的最短路径 • 由于有换乘的情况，只记录任意两点间的 最短路径是不够的。 • 并非一个标准的图论模型
7 a 6 5 b(8) c
Min(a,b)=5 Min(b,c)=3 Min(a,c)=5+6=11
3
转化成标准的图论模型
模型的假设
对”最优”的理解有三个具有代表性的指标： 时间最短 花费最少 最方便（换乘次数最少） 不同的人群对最优的理解不同,需要根据实 际定义.可以根据需要定义代价函数,三个指 标的权重不同,代价值也不同。 • 以时间最短为例 • • • • •
模型的建立
• • • • • G=(V,E) 每个车站：G的顶点 每条公交线路相邻两点的连线：G的边 边的权重：耗费时间 点的权重：换乘时间 并不是一个简单图，两点间可能有多条边
5
• 由于每两点之间均有步行路径,每次扩展都将涉及 到所有顶点,复杂度增加不少 • 改进的办法 – 预处理 找到两个相邻顶点之间路径的最小值, 如果它加上两个顶点的权值之后后,仍然小于一 些其它的路径,就可以将其它路径删除.这样至少 可以删除不少步行路径 – 考虑实际情况,可设定步行时间的上限.
算法的总结
思路一
只有6个人，人数非常少，可以枚举任意两人 之间的关系，然后判断每一种情况是否符合 题意。如果所有情况都满足，则命题成立。
虽然只有6个人，但是这样做的时间复杂度可 不低，枚举次数为215 只能借助计算机了。。。 有没有人可以直接证明的办 法呢？
思路二
有了图论这个强大的工具 我们还是像往常一样，以人为顶点，关系为边，建图 但是为了以后的直观，这里图的建立有一点小小的不同： 如果两个人之间相互认识，则在这两个人(顶点)间连一条红色边， 如果两个人不认识，则在这两个人(顶点)间连一条蓝色边(下面会 看到这样做的好处) 那么这样我们就得到了一个由红边和蓝边组成的6阶完全图 我们实际上要证明的就是这个图中或者存在一个红三角形(认识)， 或者存在一个蓝三角形(不认识)
可以考虑把能够拼出来的木棍长度x根据模3的结果分成3类(0,1,2) 对于x mod 3=0,3能够拼出来，那么6,9,12……等等模3为0的数都可以 被拼出来 对于x mod 3=1，7能被拼出来，那么7,10,13……等等都能被拼出来 对于x mod 3=2，5能被拼出来，那么8,11,14……等等都能被拼出来 也就是说，5确实是我们要求的答案
根据上面的证明，可以发现一种思路，不妨把 上述结果推广一下： 设n根木棍的长度为L1,L2,…,Ln,不妨设L1为所有 木棍中最短的 现在把能够拼出的木棍长度根据模L1的结果分 为L1类(0,1…L1-1),若某一类中的数模L1的结果 为i,则它们组成的集合为Si 显然，如果存在一个集合Si为空，则问题无解 现在考虑所有集合都不为空的情况： 设每个集合的最小元为b0,b1…bl1-1 (集合不为 空，肯定存在最小元) 那么如何去求题目要求的k呢？
• 将每一同学视为一元素，元素之间的关系为同名 或者同姓 • 构图是很自然的思路：2名同学同名或者同姓就连 一条边 姚金宇 李金宇 陈峰宏 囧峰宏
陈峰宏 姚峰宏 罗睿辞 廖叶子
• 一条边就代表了一种坐船的搭配方式 • 用最少的边覆盖图中的点——一般图的最小边覆
建模
• 图是本题信息最充分、最自然的模型，但其中 数据关系存在很多冗余，没有充分利用原题的 条件 • 单独看同名、同姓这2种关系，它们都是等价 关系，具有传递性 • 那么换一种模型构造如何？
由以上两点可知，k’一定是不能被拼出的木棍长度中 的最大值 那么k’+1就是我们要求的答案！
还剩下最后一步：求b0,b1,b2…bl1-1,也就是每个集合中的最小元 事实上，每一个能被拼出来的木棍长度x，都是从0开始，用已有的小木 棍拼出来的。那么就可以把集合的编号看做顶点，小木棍的长度看边的 长度，建立一个图。对于每个点i(集合i)，都连出n条边，长度为 L1,L2…Ln。对于长度为Lk的边，连向编号为(i+Lk) mod L1的顶点。 对于从顶点i到j的一条长度为L的路径，表示集合i中的一个数加上L后得到 的数属于集合j。 对于任意一个能拼出来的数x(设x mod L1=p),根据上面的建图规则，x一 定是点0到p的一条路径的长度。 反过来，0到p的所有路径长度都属于Sp。 所以，可以得出结论：Sp中的最小元其实就是顶点0到顶点p的最短路径 长度。 有了这个结论，我们就可以很容易的求出序列{bn}了 至此，这个问题也就被完美的解决
主要内容
• 建模的方法和步骤 ——汪瑜婧 • 图论模型的建立 ——罗睿辞 • 图论模型的选择和关系的简化 ——雷涛 • 其它数学模型举例 ——王尧
建模的方法和步骤
• • • • • • 模型准备 模型假设 模型的建立 模型求解与分析 模型检验 模型应用
问题的提出
• 2007CUMCM B题 乘公交，看奥运 • 给定若干条公交线路，以及在每条公交线 路中任意相邻的两站之间所花费的时间。 • 并且给定乘客在任意站点换乘的耗时 • 要求给出任意两公汽站点之间线路选择问 题的一般数学模型与算法，求出最佳的公 交线路.
• • • • • 关键在于如何解决换乘的耗时 扩展节点的策略与经典算法不同 算法实际用到了分支界限法的思想 类似于回溯法，但是求解的目标不同。 目标：找到使目标函数取极值的解。
分支界限法思想
• 以广度优先或以最小耗费（最大效益） 优先的方式搜索问题的解空间树 • 从一个点开始，每次以一定的策略扩展 一些结点。每一个活结点一旦成为扩展 结点，就一次性产生其所有子结点，并 从活节点中移除。在产生 的子结点中， 导致不可行解或导致非最优解的子结点 被舍弃，其余的加入活结点表中。
a b
1 1 a 1 1 b
2 2 1 2 1 a 1 2 1 2 2 b
3 2 1 2
2 1 a 1 2 1 2 3 2 b
3 2 1 2
2 1 a 1 2 1 2 3 4 2 b
3 2 1 2
2 1 a 1 2 1 2 3 4 5 2 b
3 2 1 2
2 1 a 1 2 1 2 3 4 5 6 6 2 b
任取一个顶点v0，由它连出5条边到其它的顶点，这五条边只有红色和蓝 色两种 根据抽屉原理，肯定有一种颜色的边有3条或3条以上,不妨设为红色 v0
vi
vk
vj 如果vi,vj,vk之间的边都是蓝边，则图中存在一个蓝三角形 如果至少有1条为红边，那么它总会与v0发出的两条红边组成 一个红三角形。 这样就证明了这个命题
建模步骤的总结
• 模型的分析与求解
– 已建立的模型是否有标准解法 – 转化成标准模型 – 对已有的标准解法修改，以适应模型的求解
• 模型的检验
– 灵敏性，鲁棒性
• 模型的应用
图论模型的引入
引例 现有6个人，任意两人之间或者相互 认识，或者相互不认识，证明这6个人中， 或者有3个人彼此都认识，或者有3个人 彼此不认识
数学建模——模型的选择、 关系的简化
• 很多问题都是通过建立图论模型解决的 • 图论中常见的模型有序列、树、各种图 • 如何有效选择数学模型，简化原问题中元素之 间的关系是数学建模的关键
题目
• 坐船问题（改编自湖南省信息学省队选拔赛试 题） • 北大有n个学生去公园划船： • 一只船最多坐2个人； 2 • 出于娱乐目的，大家决定同船的2个人要么同 姓要么同名； • 每个人都必须上船，且不能有脚踏多只船的情 况 • 问最少需要几只船。
3 2 1 2
2 1 a 1 2 1 2 3 4 5 6 6 7 7 2 b
3 2 1 2
2 1 a 1 2 1 2 3 4 5 6 6 7 2 b 8 7 8 8
建模步骤的总结
• 模型的准备
– 提出问题，搜集数据。
• 模型的假设
– 根据实际情况，提出合理的假设简化问题。
• 模型的建立
– 根据所作的假设分析对象的因果关系，利用 对象的内在规律和适当的数学工具，构造各 个量间的等式关系或其它数学结构。
• 把图转换成树来考虑
建模
• 对于原图中的每一个连通分量，一定可以转换成 一棵二叉树
罗睿辞 罗睿辞
罗贯中
罗纳尔多
罗贯中 罗纳尔多
廖睿辞
廖睿辞
Байду номын сангаас
树中一个结点的左孩子跟其同姓； 一个结点的右孩子跟其同名。 证明用反证法
现有n根长度不同的小木棍，每根木棍数量无限，取出一些小木棍可以拼 出一根长度为这些小木棍长度之和的木棍。现在要求最小的整数k，使得 长度大于等于k的木棍都能够被给出的n根小木棍拼出。 这个题看上去似乎毫无头绪，那就先看看简单的情况吧！ 例如，现在有3根小木棍，长度分别3,5,7 它们可以拼出长度为3,5,6,7,8,9,10,11,12,13……的木棍，看上去5就是 答案，怎么证明呢？