数学建模-图论.doc

《数学建模-图论.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、初等数学方法建模现实世界中有很多问题，它的机理较简单，用静态,线性或逻辑的方法即可建立模型，使用初等的数学方法，即可求解，我们称之为初等数学模型。本章主要介绍有关自然数，比例关系，状态转移，及量刚分析等建模例子，这些问题的巧妙的分析处理方法，可使读者达到举一反三，开拓思路，提高分析,解决实际问题的能力。第一节有关自然数的几个模型1.1鸽笼原理鸽笼原理又称为抽屉原理，把个苹果放入个抽屉里，则必有一个抽屉中至少有2个苹果。问题1：如果有个人，其中每个人至多认识这群人中的个人（不包括自己），则至少有两个人所认识

2、的人数相等。分析：我们按认识人的个数，将个人分为类，其中类，表示认识个人，这样形成个“鸽笼”。若，则个人分成不超过类，必有两人属于一类，也即有两个人所认识的人数相等；若，此时注意到类和类必有一个为空集，所以不空的“鸽笼”至多为个，也有结论成立问题2：在一个边长为的正三角形内最多能找到几个点，而使这些点彼此间的距离大于.分析：边长为1的正三角形，分别以为中心，为半径圆弧，将三角形分为四个部分（如图1-1），则四部分中任一部分内两点距离都小于，由鸽笼原理知道，在三角形内最多能找四个点，使彼此间距离大于，且确实

3、可找到如及三角形中心四个点。图1—1问题3：能否在的方格表的各个空格中，分别填写这三个数中的任一个，使得每行，每列及对角线的各个数的和都不相同？为什么？分析：若从考虑填法的种类入手，情况太复杂；这里我们注意到，方格表中行,列及对角线的总数为个；而用填入表格，每行,列及对角线都是个数，个数的和最小为，最大为，共有种；利用鸽笼原理，个“鸽”放入个“鸽笼”，必有两个在一个“鸽笼”，也即必有两个和相同。所以题目中的要求，无法实现。思考题：在一个边长为的正三角形内，若要彼此间距离大于，最多能找到几个点？1.2“奇偶

4、校验”方法所谓“奇偶校验”，即是如果两个数都是奇数或偶数，则称这两个数具有相同的奇偶性；若一个数是奇数，另一个数是偶数，则称具有相反的奇偶性。在组合问题中，经常使用“奇偶校验”考虑配对问题。问题1（棋盘问题）：假设你有一张普通的国际象棋盘，一组对角上的两个方格被切掉，这样棋盘上只剩下个方格（如图1—2）。若你还有块骨牌，每块骨牌的大小为方格。试说明用互不重叠的骨牌完全覆盖住这张残缺的棋盘是不可能的。分析：关键是对图1—2的棋盘进行黑白着色，使得相邻的两个方格有不同的颜色；用一块骨牌覆盖两个方格，必是盖住颜

5、色不同的方格。我们计算一下黑白着色棋盘的黑格，白格个数，分别为和；因此不同能用块骨牌盖住这张残缺的棋盘。用奇偶校验法，我们可以把黑色方格看成奇数方格，白色方格看成偶数方格；因为奇偶个数不同，所以不能进行奇偶配对，故题中要求的作法是不可能实现的。图1-3图1-2问题2（菱形十二面体上的H路径问题）：沿一菱形十二面体各棱行走，要寻找一条这样的路径它通过各顶点恰好一次，该问题被称为Hamilton路径问题。分析：我们注意到菱形十二面体每个顶点的度或者为或者为，所谓顶点的度是指通过这一顶点的棱数，如图1—3；且每

6、度顶点刚好与个度顶点相连，而每个度顶点刚好与个度顶点相连。因此一个Hamilton路径必是度与度顶点交错，故若存在Hamilton路径，则度顶点个数，与度顶点个数要么相等，要么相差。用奇偶校验法度顶点为奇数顶点，度顶点为偶数顶点，奇偶配对，最多只能余个；而事实上菱形十二面体中，有度顶点个，度顶点个；可得结论，菱形十二面体中不存在Hamilton路径.思考题：1、设一所监狱有间囚室，其排列类似棋盘，看守长告诉关押在一个角落里的囚犯，只要他能够不重复地通过每间囚室到达对角的囚室（所有相邻囚室间都有门相通）,他

7、将获释，问囚犯能否获得自由？2、某班有个学生，坐成行列，每个坐位的前后左右的坐位叫做它的邻座，要让个学生都换到他的邻座上去，问是否有这种调换位置的方案？1.3自然数的因子个数与狱吏问题令为自然数的因子个数，则有的为奇数，有的为偶数，见下表:n12345678910111213141516d(n)1223242434262445我们发现这样一个规律，当且仅当为完全平方数时,为奇数；这是因为的因子是成对出现的,也即;只有为完全平方数,才会出现的情形，才为奇数。下面我们利用上述结论研究一个有趣的问题.狱吏问题：

8、某王国对囚犯进行大赦，让一狱吏n次通过一排锁着的n间牢房，每通过一次按所定规则转动门锁,每转动一次,原来锁着的被打开,原来打开的被锁上；通过n次后，门锁开着的，牢房中的犯人放出，否则犯人不得获释。转动门锁的规则是这样的，第一次通过牢房，要转动每一把门锁，即把全部锁打开；第二次通过牢房时，从第二间开始转动，每隔一间转动一次；第k次通过牢房，从第k间开始转动，每隔k-1间转动一次；问通过n次后，那些牢房的锁仍然是打开的？问题分析：