“数学建模”讲座：图论方法及其建模

《“数学建模”讲座：图论方法及其建模》由会员分享，可在线阅读，更多相关《“数学建模”讲座：图论方法及其建模（26页珍藏版）》请在金锄头文库上搜索。

1、1数学建模数学建模讲座讲座：数学建模中的数学建模中的图论图论方法方法图论是离散数学的重要组成部分，它对于自然科学、工程技术、经济管理和 社会现象等诸多问题，能够提供有力的数学模型加以解决，特别在国内外大学生 数学建模竞赛当中，有不少问题可以应用图论模型解决。我们在此有针对性地把 图论的骨干概念和结论以及相关的有效算法做一简要介绍，愿听者增强图论建模 的意识和能力。MCM 中与图论有关的题目中与图论有关的题目：190-B 扫雪问题（二邮递员中国邮路问题）求欧拉回路的 Fleury 算法291-B 通讯网络的最小生成树寻找最优Steiner树392-B 应急电力修复系统最小生成树算法494-B 计

2、算机网络的最小接通时间中国大学生数学建模竞赛试题中国大学生数学建模竞赛试题：1. 94-A 逢山开路 利用求最短路的Dijkstra算法94-B 锁具装箱 DFS 算法2. 98-B 灾情巡视路线多邮递员中国邮路问题3. 99-B 钻井布局4. 00-B 钢管订购和运输11 图论的基础知识图论的基础知识图论中的“图”并不是通常意义下的几何图形或物体的形状图，而是以一种 抽象的形式来表达一些确定的事物及其关系的一个数学系统。 在历史上，图论的创立开始于对著名的七桥问题的研究。nigsbergoK (2) 连通无向图G含有欧拉路的充要条件是G恰有两个奇结点,且欧拉 路必始于一个奇结点而终止于另一个

3、奇结点. 图 7 的所有结点均为偶结点，故为欧拉图，一条欧拉回路为： 。aabcdefcebf图 8 有 2 个奇结点，故不是欧拉图，但有欧拉路：。bcdeabe 从欧拉回路和欧拉路的定义可知，图中的欧拉回路(欧拉路)是经过图中所有 边的最短回路(路径)。8abcdefabcde图 7 图 8ABCDFEGbcdae图 9 图 10 如图 9 是某街道图形。洒水车从 A 点出发执行洒水任务。试问是否存在一条 洒水路线，使洒水车通过所有街道且不重复而最后回到车库 B？ 此问题即为求证图中是否存在 A 到 B 的欧拉路。由于图中每个结点除 A，B 为 奇结点外其余均为偶结点，由定理可知，这样的洒水

4、线路是存在的，例如， ACDEFBGCFGAB 或 AGFEDCFBGCAB，等等。 （蚂蚁比赛问题）如图 10 所示，甲、乙两只蚂蚁分别位于结点处，并设ba, 图中的边长度相等。甲、乙进行比赛：从它们所在的结点出发，走过图中的所有 边最后到达结点处。如果他们的速度相同，问谁先到达目的地？e 在图中，仅有两个奇结点，因而存在从到的欧拉路，蚂蚁乙走到只eb,bee 要走一条欧拉路，边数为 9 条；而蚂蚁甲要想走完所有的边到达，至少要先走e 一条边到达，再走一条欧拉路，因而它至少要走 10 条边才能到达，所以乙必be 胜。 如图 11(a)是一幢房子的平面图，前门进入一个客厅，由客厅通向四个房间。

5、 如果要求每扇门只能通过一次，现在由前门进入，能否通过所有的门走遍所有的 房间（包括客厅） ，然后从后门走出？9f d a b c e f a d e c 图 11 )(a)(b 将四个房间和一个客厅及室外作为接点，门作为边画出图(b)。由于 b 和 e 是 仅有的两个奇结点，故从前门进、后门出的欧拉路是不存在的，即本题无解。 如果把“前门进、后门出”这一条件去掉，则存在“每扇门通过一次且仅一 次”的走法。请读者找出具体的走法。4 4哈密尔顿图哈密尔顿图所谓哈密尔顿回路，起源于一个名叫“周游世界”的游戏，它是由英国数学 家哈密尔顿（Hamilton）于 1859 年提出的。他用一个正十二面体的

6、 20 个顶点代 表 20 个大城市（图 12(a)） ，这个正十二面体同构于一个平面图（图 12(b)） 。要 求沿着正十二面体的棱，从一个城市出发，经过每个城市恰好一次，然后回到出 发点。这个游戏曾风靡一时，它有若干个解。图 12(b)给出了一个解。 定义定义：如果图G中具有一条经过所有结点的基本回路（称哈密尔顿回路） ， 则称为哈密尔顿图哈密尔顿图。 虽然哈密尔顿图判定问题与欧拉图判定问题同样有意义，但遗憾的是至今为 止还没有找到一个判别它的充分必要条件，这是图论中尚未解决的主要问题之一。1 3 2 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

7、 (a)图 12 (b)105 5二部图二部图 定义定义 设无向图，如果存在的一个分划，使得G的每),(EVG V21,VV一条边的两个端点分属V1和V2，则称G为二部图二部图(或偶图偶图)。V1和V2称为互补互补 结点子集结点子集，此时可将G记为。),(21VEVG 显然，二分图没有自环，在互补结点子集V1和V2内各结点互不邻接 图 13(a)给出了一个二分图的例子，它的互补结点子集为，43211,vvvvV 7652,vvvV (a)(b)v1v5v2v6v7v3v4图 13如果V1的每个结点与V2的每个结点有且仅有一条边相关联，则称G为完全完全 二部图二部图，记为，其中。nmK,21,V

8、nVm图 13(b)给出了一个完全二部图。3 , 3K定理定理 无向图G=(V, E)是二部图的充分必要条件是G中无长度为奇数的回 路。 推论推论 非平凡树是二部图。 与二部图的概念紧密相关的问题是匹配问题。 设是二部图，若，且M中任何两条边均不相邻，则),(21VEVG EM 称M是G的一个匹配匹配；具有最大边数的匹配称为最大匹配最大匹配；若最大匹配M满足 ，则称M是G的一个完备匹配完备匹配，此时若，则称M21,minVVM 21VV 为V1到V2的一个完备匹配；若，则称M是G的一个完美匹完美匹MVV21 配配 在图 14 中，为G1中的最大匹配，G1中不存在完备匹配，更无完美21,ee匹配

9、；G2中，为完备匹配，但G2中无完美匹配；在G3中，321,eee为完备匹配，同时也是完美匹配321,eeee3e1e2 e1e2e3e2e1111G2G3G图 14 下面给出存在完备匹配的充分必要条件Hall 定理定理 设二分图，则G中存在从V1到V2的),(21VEVG 21VV 完备匹配当且仅当V1中任意k个结点至少邻接V2中的k个结点， 1, 2 , 1VkL定理中的条件称为相异性条件相异性条件判断一个二分图是否满足相异性条件通常比 较复杂，下面给出一个判断二分图是否存在完备匹配的充分条件，对于任何二分 图来说，都很容易确定这些条件因此，在考察相异性之前，应首先试用这个充 分条件 定理

10、定理 设二分图，如果),(21VEVG （1）V1中每个结点至少关联t条边； （2）V2中每个结点至多关联t条边， 则G中存在从V1到V2的完备匹配，其中t为正整数 （充分，不必要） 定理中的条件通常称为t条件条件6.6.平面图平面图如果无向图G有一种画法，使其没有非结点的交叉，则称G为平面图平面图。 波兰数学家 Kuratowsky 给出下面的重要结论：（1）K5与K3,3不是平面图。（2）G是平面图的充分必要条件是G中不含与K5与K3,3同胚的子图。 定理定理(欧拉公式) 设G是连通平面图，则有 2kmn 其中n为结点数，m为边数，k为面数。 推广：若平面图G有n个结点，m条边，k个面和(

11、G)个连通分支，则有 .)(1Gkmn1222 综合例题综合例题例例 1 1 “死锁死锁”问题问题 下面举一个例子说明图的连通性连通性在计算机科学中的应用 在操作系统中允许多个进程同时工作，在进程工作时需要动态申请一些资源 (如 CPU，内存，外存，输入输出设备，编译程序等)，有时可能会出现一些冲突， 如进程A占有资源R1且需要申请资源R2，而进程B占有资源R2且需要申请资 源R1，此时两个进程均无法执行，这被称为计算机系统处于“死锁”状态可用 有向图来模拟对资源的分配以及产生死锁的特征，从而便于检出和纠正死锁 设是t时刻运行的程序集合，是t时4321,ppppPt4321,rrrrRt刻所需

12、的资源集合资源的分配状况如下：p1占有资源r4且申请资源r1；p2占有 资源r1且申请资源r2及r3；p3占有资源r2且申请资源r3；p4占有资源r3且申请 资源r1及r4它们的资源分配情况可用图 15 表示图 15 显然，当且仅当分配图中含有多于一个结点的强连通分支时，或者含有回路 时，计算机系统才在t时刻产生死锁。用矩阵方法可以计算出图中是否含有多于 一个结点的强连通分支或是否含有回路，从而检测出是否存在死锁。例例 2 2 证明任意六个人的集会上，总会有三人互相认识或者不认识 证明证明 这是 1947 年匈牙利数学竞赛出的一道试题，因为它很有趣且很重要， 后来曾收录到美国数学月刊及其它数学

13、刊物上。这类问题可以转化为图论中 的完全图染色问题 把参加集会的人看作结点，作一个完全图，如果两个人认识，则两结点间6K的连线涂上红色，否则涂上蓝色问题转化为：无论怎样涂色，总可以找到红 或蓝3K3K设六个结点为。从引出的边有五条，而颜色只有红蓝两种，6 , 1 Livi1v由抽屉原理，至少有三条边同色，不失一般性，假定有三条边 为红色。313121,vvvvvvr1 r4 r2 r3 13（1）如果结点之间至少有一条红边，比如是红边，则得到432,vvv32,vv红色的三角形；321vvv（2）如果结点之间的边全是蓝色的，则得到蓝色的三角形。432,vvv432vvv关于问题中的结点数，对任

14、何，命题都成立但当时，命题便不6n5n 成立了。这说明：不同的六个点是保证用两色涂染其边，存在同色三角形的最少 点数。例例 3 3 出席某次国际学术会议的有六个成员a, b, c, d, e, f，其中：a会 讲汉语、法语和日语；b会讲德语、日语和俄语；c会讲英语和法语；d会讲汉语 和西班牙语；e会讲英语和德语；f会讲俄语和西班牙语如将此六人分成两组， 是否会发生同一组内的任意两人不能互相直接交谈的情况？ 解解 用结点表示成员，两成员间如有共同语言，则用边相连，可得图 18由 于图中的回路长度均为偶数，故此图为二部图设，feaV,1，当六位代表如此分组时，则同一组内的任意两个人都不能直接交dc

15、bV,2 谈例例 4 4 作为二叉树的一个应用，下面介绍一下有关前缀码前缀码的问题 问题的提出：在通讯中，常用 0 和 1 的字符串作为英文字母来传递信息由 于各个字母被使用的频率相差很大，人们希望将一些常用字的编码缩短，从而大 大缩短信息串的总长但这就产生了一个问题：当我们用不同长度的序列去表示 字母时，在接收端的人如何将一长串的 0 和 1 准确无误地分割成字母对应的序列 呢？例如，用 00 表示 A，01 表示 B，0001 表示 T，那么当接收端收到信息串 0001 时，我们将不能分辨传递的内容是 AB 还是 T为了避免发生这种混乱，我们在编 码常常采用一种叫做前缀码的序列来表示英文字母 定义定义 一个序列的集合，若这个集合的任何序列都不是另外序列的前缀，则 这个序列集合称为前缀码前缀码 例如，000，001，01，10，11是前缀码，而1，0001，000则不是前缀 码 前缀码与二叉树有一一对应的关系 首先，任何一棵二叉树的树叶可对应一个前缀码 若给定一棵二叉树，将每个分枝点的左侧的边标 0，右侧的边标 1，这样每片 树叶将标定一个 0 和 1 的序列，它是由树根到这片树叶的路径上各边的标号所组 成的，显然没有一片树叶标号的序列是另一片树叶标号序列的前缀，因此这棵二abdfec图 1814叉树的树叶可对应一个前缀码 另一方面，如给定一个前缀码，表示前缀码中最长序列的长