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

1、数学建模讲座：数学建模中的图论方法图论是离散数学的重要组成部分，它可以为解决自然科学、工程技术、经济管理和社会现象等诸多问题提供强大的数学模型，特别是在国内外大学生数学建模竞赛中。本文简要介绍了图论及相关有效算法的关键概念和结论，希望听众能够提高对图论建模的认识和能力。多芯片模块中与图论相关的主题；1.90-b扫雪问题(中国第二邮递员的邮政路线)寻找欧拉路径的Fleury算法2.91-B通信网络的最小生成树寻找最佳斯坦纳树3.92-B紧急电力维修系统最小生成树算法4.94-b计算机网络的最小接通时间中国大学生数学建模竞赛试题：1.94-每座山上都有一条开阔的道路用Dijkstra算法寻找最短路

2、径94-B锁的包装离散傅立叶变换算法2.98-B灾难巡逻路线中国邮政的多邮递员路线问题3.99-B钻井布置图4.00-B钢管订购和运输1图论的基本知识图论中的“图”不是普通意义上的物体的几何图形或形状图，而是以抽象形式表达某些事物及其关系的数学系统。历史上，图论的建立始于对著名的七桥的研究。它是18世纪欧洲的一座城市。它位于河岸上。河中有两个岛屿，七座桥已经建好，把河岸和两个岛屿连接起来。当时，这个城市的居民热衷于讨论这样一个问题：如果你想从任何一片土地开始，你能不能每座桥都经过一次，不再重复，最后回到起点(图1)？瑞士数学家欧拉在1736年解决了这个问题。他发表了第一篇关于图论的论文。)，这

3、证明七桥问题没有解决方案。同时，他提出并解决了更普遍的问题，从而奠定了图论的基础。图1A.图的基本概念图g由非空节点集和边集组成，表示为。它的节点数称为顺序。根据边是否有方向，图可以分为有向图和无向图。通过从有向图的边缘去除方向而获得的图称为原始有向图的基本图(或基础图)。没有自环或多重边的图称为简单图。一些从实际问题中抽象出来的图的边上通常有信息。一些数字被附加到边上以描述边并对它们进行称重。此时，这些图被称为加权图。无向图中与节点V相关联的边数称为V的度。记住，有向图中以V为起点或终点的边数分别称为V的出度和入度。握手定理：(1)无向图中所有节点的度数之和等于边数的两倍。(2)有向图中所有

4、节点的出度(入度)之和等于边数。推论：任何图的奇数节点必须是偶数。例如，在一群人中，那些有奇数个朋友的人必须有偶数个。如果一个简单无向图的任意两个节点是相邻的，则称之为完全图，n阶完全图表示为，每个节点的度等于，边的个数等于。如果它是一个N阶简单图，通过去掉相应完全图中的所有边得到的图称为补图，表示为。一系列边(或点)称为路径，闭合路径称为循环。具有非重复边的路径称为简单路径，而具有非重复点的路径称为基本路径。路径中的边数称为路径长度。如果从节点u到v有一条路径，则称它是从u到v可达的。如果u到v可达，则u到v的最短路径称为测地线(或测地线)，其长度称为u到v的距离，其表达式为：如果你无法到达

5、，请记住。如果无向图G的任意两个节点都是可达的，那么G称为连通图。有向图的连通性更为复杂：如果G中的任意两个节点可以相互访问，则G被称为强连通；如果g中任意两个节点之间的至少一个节点可以到达另一个节点，则g被称为单向连接(简单连接)；如果G的基本图是连通的让我们设置一个图，如果有双射函数，保持它们之间的连接关系，即它们之间的连接关系与它们之间的连接关系完全相同，并且保持有向图中边的方向，并且在多个图中具有相同的多重性，那么它被称为同构，其被写成。下面给出了几组同构图(图中显示了节点的对应关系)。图22.图的矩阵表示为了用计算机存储和处理图形，有必要用矩阵来表示图形。常用的有：邻接矩阵、可达性矩

6、阵、距离矩阵等。如果定义了N阶图的节点集，则N阶方阵称为G的邻接矩阵，其中aij表示以vi为起点、vj为终点的边数。图的邻接矩阵完全描述了图中节点之间的邻接关系。如图3所示，它们的邻接矩阵是：,第五颅神经的眼支v2v3v4图3从邻接矩阵的定义中，很容易得到以下结论：(1)无向图的邻接矩阵是对称的；(2)当且仅当所有元素都是0或1时，图没有平行边；(3)当且仅当主对角元素都是0时，图没有自环；(4)当且仅当所有元素都是0时，图是零图；(5)如果它是无向图，那么(6)如果它是有向图，那么定理假设N阶图G的节点集和A是G的邻接矩阵，那么Ak中的元素等于路径数(，)，长度k是从vi到vj如图3所示，、

7、分别表示从到的长度为1、2、3和4的路径数，分别为1、1、2和3。请在图上验证并找出每条路径。如果定义了N阶图G的节点集，则N阶方阵称为G的可达矩阵，其中显然，无向图的可达矩阵是对称的，而有向图不是对称的。计算公式为：其中，并分别表示布尔和和布尔积。图3中的可达性矩阵是：图的邻接矩阵和可达性矩阵可以用来判断图的连通性，以下结果是显而易见的：(1)无向图g是连通图，当且仅当它的可达性矩阵p的所有元素都是1；(2)有向图G是强连通图，当且仅当它的可达性矩阵P的所有元素都是1；(3)有向图G是单向连通图，当且仅当它的可达矩阵P和它的转置矩阵PT的布尔和除了主对角元素外都是1；(4)有向图G是(弱)连

8、通图，当且仅当以其邻接矩阵A和其转置矩阵AT的布尔和作为邻接矩阵得到的可达矩阵的元素都是1。此外，图的可达矩阵还可以用来判断图G中是否存在回路，当且仅当其可达矩阵的主对角元素不全为零时。您也可以使用可达性矩阵来寻找无向图的连通分支。请考虑具体方法。三。几类重要人物1.双向树连通非循环图被称为树。其连通分支是树的无向图称为森林。在下图中，(a)、(b)、(c)和(d)都是树，(e)是森林。定理：如果一棵树的节点数是n，边数是m，那么m=n-1。当节点数确定时，树是连通图中边数最少的图和非循环图中边数最多的图。每个连通图G至少有一个生成子图是树，称之为G的生成树。显然，每个连通图都有一个生成树，但

9、一般来说，生成树不是唯一的(边数是一定的)。有6个城市之间连接有输油管道，其布局如图4.3(a)所示。战争期间，为了保护输油管道不被破坏，有必要派部队守卫输油管道，也有必要派一个连的士兵守卫一段输油管道。为了保证城市间的石油运输畅通，有必要至少派出几个连的士兵。他们应该驻扎在哪个油管？解决方案：这个问题是找到图4.3(a)中的生成树。从图中可以看出，节点数是6，所以它的生成树的边数是5，也就是说，至少要派5个士兵来保护它。参见图4.3(b)、(c)和(d)中绘制的线段。图4.3如果G是一个加权连通图，我们可以传统上，我们在顶部画根树的根，在底部画叶子，有向边都指向下，这样所有的箭头都可以省略。

10、3.Euratu如果在图G中有一个简单的环通过所有的边，它被称为欧拉路径，而有欧拉路径的图被称为欧拉图。如果在图G的所有边上都有一条简单的(非循环)路径，它就叫做欧拉路径。定理：(1)连通无向图G是欧拉图，当且仅当G的每个节点都是偶节点；(2)连通无向图G包含欧拉路径，当且仅当G正好有两个奇节点，并且欧拉路径必须从一个奇节点开始，在另一个奇节点结束。图7中的所有节点都是偶数节点，所以它们是欧拉图，欧拉路径是：图8有两个奇数节点，所以它不是欧拉图，但它有欧拉路径：从欧拉路径和欧拉路径的定义可以看出，图中的欧拉路径是通过图中所有边的最短回路(路径)。图7图8图9图10图9是街道图。洒水喷头从点a开

11、始执行洒水任务。有没有一条洒水路线可以让洒水器穿过所有街道而不重复，最后回到车库B？这个问题是为了验证图中是否有从A到B的欧拉路径。由于图中的每个节点都是偶数，除了A和B是奇数节点之外，从定理中可以知道存在这样的喷水线，如ACDEFBGCFGAB或AGFEDCFBGCAB，等等。(蚂蚁竞争问题)如图10所示，两只蚂蚁，一只和一只，分别位于节点处，图中的边被假定为长度相等。甲方和乙方竞争：从他们所在的节点开始，穿过图中的所有边，最后到达节点。如果他们有相同的速度，谁会先到达目的地？在图中，只有两个奇数节点，所以有从到的欧拉路。蚂蚁乙只需走一条欧拉路，边数为9；如果蚂蚁甲想走完所有的边才能到达，它

12、必须先走至少一条边，然后再走另一条欧拉路，所以它必须走至少10条边才能到达，所以蚂蚁乙会赢。图11(a)是房屋的平面图。前门进入一个起居室，通向四个房间。如果每个门只需要通过一次，现在是从前门进入，你能穿过所有的房间(包括客厅)穿过所有的门，然后从后门出去吗？图11画出图(b)，四个房间，一个客厅和室外作为连接处，门作为边。因为B和E是仅有的两个奇数节点，所以从前门到后门的欧拉路径不存在，也就是说，这个问题没有解决方案。如果去掉“前门进，后门出”的条件，就有了“每扇门只经过一次”的办法。请找出具体的方法。4.哈密尔顿图所谓的哈密尔顿电路起源于一种叫做“环游世界”的游戏，它是由英国数学家哈密尔顿

13、于1859年提出的。他用一个正十二面体的20个顶点来代表20个大城市(图12(a)，这与一个平面图(图12(b)是同构的。它需要从一个城市沿着正十二面体的边缘开始，经过每个城市一次，然后回到起点。这个游戏曾经很受欢迎，它有几种解决方案。图12(b)给出了一个解决方案。定义：如果有一个基本回路(称为哈密尔顿回路)通过图G中的所有节点，它被称为哈密尔顿图。虽然哈密尔顿图的判断与欧拉图的判断一样有意义，但遗憾的是至今还没有找到判断哈密尔顿图的充分必要条件，这是图论中尚未解决的主要问题之一。图12 (b)5.两部分绘图让我们定义一个无向图。如果有一个划分使得G的每条边的两个端点都属于V1和V2，那么G

14、就叫做二部图(或偶图)。V1和V2被称为互补节点子集，G可以写成。显然，二部图没有自环，互补节点子集V1和V2中的节点彼此不相邻。图13(a)给出了互补节点子集为的二部图的例子。图13如果V1的每个节点只与V2的每个节点的一条边相关联，那么G被称为完全二部图。图13(b)示出了完整的二分图。定理无向图G=(V，E)是一个二部图，当且仅当G中没有奇数长度的环。得出非平凡树是二部图的结论。匹配问题与二部图的概念密切相关。假设它是一个二部图，如果m中的任意两条边不相邻，那么m是g的匹配；边数最多的匹配称为最大匹配；如果满足最大匹配m，则m被认为是g的完全匹配，如果满足，则m被认为是从V1到V2的完全

15、匹配。如果，那么M是G的完美匹配.在图14中，它是G1的最大匹配，在G1没有完全匹配，更不用说没有完美匹配；在G2中，它是完全匹配的，但在G2中没有完美匹配；在G3中，它是完美匹配，也是完美匹配。e3e1e2e1e2e3e2e1图14完全匹配存在的充要条件如下。霍尔定理设置二部图，那么当且仅当V1的任何k个节点至少与V2的k个节点相邻时，在g中从V1到V2是完全匹配的。定理中的条件称为相异条件。判断二部图是否满足相异条件通常比较复杂。这里有一个判断二部图是否完全匹配的充分条件。对于任何二部图，很容易确定这些条件。因此，在考察不同之前，我们应该先试试这个充分条件。定理集二部图，如果(1)1)V1

16、中的每个节点与至少t个边相关联；(2)2)V2中的每个节点最多与t个边相关联，从V1到V2在g中是完全匹配的，其中t是正整数。(足够，不必要)定理中的条件通常被称为T条件。6.计划如果一个无向图G有一种绘制方式，因此它没有非节点的交集，那么G被称为平面图。波兰数学家库拉托夫斯基给出了以下重要结论：(1)K5、K3、3和3不是平面图。(2)当且仅当G不包含与K5和K3，3同胚的子图时，G是平面图。定理(欧拉公式)如果G是一个连通平面图，那么其中n是节点数，m是边数，k是面数。一般化：如果一个平面图G有n个节点，m条边，k个面和(G)个连通分支，那么就有。2个综合例子示例1死锁问题这里有一个例子来说明图连通性在计算机科学中的应用。在操作系统中，允许多个进程同时工作。当进程工作时，它们需要动态地申请一些资源(如中央处理器、内存、外部存储器、输入/输出设备、编译器等)。)。有时可能会有一些冲突。例如，流程A占用资源R1，需要申请资源R2，而流程B占用资源R2，需要申请资源R1。这时，两个进程都不能执行，这就叫计算机系统处于“死锁”状态。有向图可以用来模拟资源的分配假设它是在时间T运行的一组程序，这是在时间T需要的一组资源。资源的分配状态如下：p