图论介绍及应用。
图论是运筹学的一个分支，广泛应用于物理学、现代控制理论、信息论、管理科学、计算机技术等诸多领域。利用图论的理论和方法能够提供有力的数学模型是问题得到解决。图论中的图是由若干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系。
1 图论起源背景。
图论起源于著名的柯尼斯堡七桥问题。在柯尼斯堡的普莱格尔河上有七座桥将河中的岛及岛与河岸联结起来，如下图所示，a、b、c，d表示陆地。
问题是要从这四块陆地中任何一块开始，通过每一座桥正好一次，再回到起点。然而无数次的尝试都没有成功。欧拉在2024年解决了这个问题，他用抽象分析法将这个问题化为第一个图论问题：
即把每一块陆地用一个点来代替，将每一座桥用联接相应的两个点的一条线来代替，从而相当于得到一个「图」（如下图）。问题成为从任一点出发一笔画出七条线再回到起点。欧拉考察了一般一笔画的结构特点，给出了一笔画的一个判定法则：
这个图是连通的，且每个点都与偶数线相关联，将这个判定法则应用于七桥问题，得到了“不可能走通”的结果，不但彻底解决了这个问题，而且开创了图论研究的先河。
2 图的基本概念。
图是由顶点集v=（v1，v2，….vm），边集e=（e1，e2,…,en）以及各个顶点和各边之间确定的关联关系ψ组成的一种结构，记作图g=（v, e,ψ）一般也记作g=(v, e)。显然这里的图不是几何意义上的图，只要保持v, e,ψ不变，顶点的位置，边的长短曲直都可以任意选择。
如果各条边都加上方向，称为有向图，否者称为无向图。既有无向边又有有向边的图称为混合图。
如果图的两顶点间最多有一条边，且每条边的两个顶点都不重合的图，则称为简单图。
如果图的两顶点间有边相连，则称顶点相邻 ，每一对顶点都相邻的图称为完全图，否则称为非完全图，完全图记为k 。
若且x 中任意两顶点不相邻，y 中任意两顶点不相邻，则称为二分图；若x中每一顶点皆与y 中一切顶点相邻，称为完全二分图记为(m=|x|,n=|y|)。
奇数的顶点称为奇点，否则称为偶点。
定理 1 g为二分图的充要条件是g中无长为奇数的圈。
定义 1) 在无向图g中，与顶点v关联的边的数目(环算两次),称为顶点v的度或次数，记为d(v)或 dg(v).。称度为奇数的顶点为奇点，度为偶数的顶点为偶点。
在图中，一个顶点的度就是与该顶点相关联的边的数目，顶点v的度记为d（v）。若g为有向图，则把以顶点v为终点的边的数目称为顶点v的入度，记为id（v）；把以顶点v为始点的边的数目称为v的出度，记为od（v），路径长度是该路径上边或弧的数目。在无向图g中，若从顶点vi到顶点vj有路径，则称vi与vj是连通的。
若v（g）中任意两个不同的顶点vi和vj都连通（即有路径），则称g为连通图。
有时在图的每条边上附上相关的数值，这种与图的边相关的数值叫权。
2 树的基本概念。
定义 1 一个无圈的连通图称为树。
下面介绍树的一些重要性质。
定理 2 设图 g= (v, e)是一个树， p( g)≥2 ,则 g中至少有两个悬挂点。
定理 3 图 g= (v, e)是一个树的充分必要条件是 g不含圈， 且恰有 p - 1 条边。
定理 4 图 g= (v, e)是一个树的充分必要条件是 g是连通图，并且q( g) =p( g)– 1。
定理5 图 g是树的充分必要条件是任意两个顶点之间恰有一条链。
3 图论矩阵 1) 边和它的两端点称为互相关联。 2)与同一条边关联的两个端点称为相邻的顶点，与同一个顶点点关联的两条边称为相邻的边。3) 端点重合为一点的边称为环，端点不相同的边称为连杆。
4) 若一对顶点之间有两条以上的边联结，则这些边称为重边。5) 既没有环也没有重边的图，称为简单图。6) 任意两顶点都相邻的简单图，称为完全图。
记为kv.
图还可以用两种矩阵表示：
邻接矩阵表示法：是一个的矩阵，即，关联矩阵表示法是一个的矩阵，即，
带权图的最短路与关键路。
定义若图的每一条边e 都赋以一个实数w(e)，称w(e)为边e的权，g 连同边上的权，称为赋权图。
规定： u,v∈v, 边(u,v)的权记作 w(u,v) 1) w(u,u)=0 2) 如果结点u与v之间的边相连，则 w(u,v)=∞
4 关于最短路径的问题。
设有给定连接若干城市的公路网，寻求从指定城市到各城市去的最短路线。如图。
解决这一问题可以引用著名的dijkstra算法。
dijkstra 算法步骤：
5 最佳路线的选择问题。
下面结合具体的实例说明一下图论在实际问题中的应用。
98年全国大学生数学建模竞赛b题“最佳灾情巡视路线”中的前两个问题是这样的：
问题今年(2024年)夏天某县遭受水灾。 为考察灾情、组织自救，县领导决定，带领有关部门负责人到全县各乡（镇）、村巡视。 巡视路线指从县**所在地出发，走遍各乡（镇）、村，又回到县**所在地的路线。
1） 若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的巡视路线。 短且各组尽可能均衡的巡视路线。
2） 假定巡视人员在各乡（镇）停留时间t=2小时，在各村停留时间t=1小时，汽车行驶速度v=35公里/小时。 要在24小时内完成巡视，至少应分几组；给出这种分组下最佳的巡视路线。
建模过程。一 、 问题分析：
本题给出了某县的公路网络图，要求的是在不同的条件下，灾情巡视的最佳分组方案和路线。
将每个乡（镇）或村看作一个图的顶点，各乡镇、村之间的公路看作此图对应顶点间的边，各条公路的长度（或行驶时间）看作对应边上的权，所给公路网就转化为加权网络图，问题就转化图论中一类称之为旅行售货员问题，即在给定的加权网络图中寻找从给定点o出发，行遍所有顶点至少一次再回到点o，使得总权（路程或时间）最小。
本题是旅行售货员问题的延伸——多旅行售货员问题。
本题所求的分组巡视的最佳路线，也就是m条经过同一点并覆盖所有其他顶点又使边权之和达到最小的闭链（闭迹）.
如第一问是三个旅行售货员问题，第二问是四个旅行售货员问题。众所周知，旅行售货员问题属于np完全问题，即求解没有多项式时间算法。
显然本问题更应属于np完全问题。 有鉴于此，一定要针对问题的实际特点寻找简便方法，想找到解决此类问题的一般方法是不现实的，对于规模较大的问题可使用近似算法来求得近似最优解。
二、 假设。
1．汽车在路上的速度总是一定，不会出现抛锚等现象；
2．巡视当中，在每个乡镇、村的停留时间一定，不会出现特殊情况而延误时间；
3．每个小组的汽车行驶速度完全一样；
4．分组后，各小组只能走自己区内的路，不能走其他小组的路，除公共路外。
三、 模型的建立与求解。
将公路网图中，每个乡（镇）或村看作图中的一个节点，各乡（镇）、村之间的公路看作图中对应节点间的边，各条公路的长度（或行驶时间）看作对应边上的权，所给公路网就转化为加权网络图，问题就转化为在给定的加权网络图中寻找从给定点o出发，行遍所有顶点至少一次再回到o点，使得总权（路程或时间）最小，此即最佳推销员回路问题。
在加权图g中求最佳推销员回路问题是np—完全问题，我们采用一种近似算法求出该问题的一个近似最优解，来代替最优解，算法如下：
算法一求加权图的最佳旅行售货员回路近似算法：用图论软件包求出g中任意两个顶点间的最短路，构造出完备图，，；
1． 输入图的一个初始h圈；
2． 用对角线完全算法（见[23]）产生一个初始h圈；
3． 随机搜索出中若干个h圈，例如2000个；
4． 对第步所得的每个h圈，用二边逐次修正法进行优化，得到近似最佳h圈；
5． 在第5步求出的所有h圈中，找出权最小的一个，此即要找的最佳h圈的近似解。
由于二边逐次修正法的结果与初始圈有关，故本算法第步分别用三种方法产生初始圈，以保证能得到较优的计算结果。
问题一若分为三组巡视，设计总路程最短且各组尽可能均衡的巡视路线。
此问题是多个推销员的最佳推销员回路问题。即在加权图g中求顶点集v的划分，将g分成n个生成子图，使得。
1）顶点i=1，2，3……n
3），其中为的导出子图中的最佳推销员回路，为的权，i，j=1，2，3……n
定义称为该分组的实际均衡度。为最大容许均衡度。
显然，越小，说明分组的均衡性越好。取定一个后，与满足条件（3）的分组是一个均衡分组。条件（4）表示总巡视路线最短。
此问题包含两方面：第。
一、对顶点分组；第。
二、在每组中求最佳推销员回路，即为单个推销员的最佳推销员问题。
由于单个推销员的最佳推销员回路问题不存在多项式时间内的精确算法，故多个推销员的问题也不存在多项式时间内的精确算法。而图中节点数较多，为53个，我们只能去寻求一种较合理的划分准则，对图１1－9进行粗步划分后，求出各部分的近似最佳推销员回路的权，再进一步进行调整，使得各部分满足均衡性条件（3）.
从o点出发去其它点，要使路程较小应尽量走o点到该点的最短路。故用图论软件包求出o点到其余顶点的最短路，这些最短路构成一棵o为树根的树，将从o点出发的树枝称为干枝，见图１１－0，从图中可以看出，从o点出发到其它点共有6条干枝，它们的名称分别为。
根据实际工作的经验及上述分析，在分组时应遵从以下准则：
准则一：尽量使同一干枝上及其分枝上的点分在同一组；
准则二：应将相邻的干枝上的点分在同一组；
准则三：尽量将长的干枝与短的干枝分在同一组。
由上述分组准则，我们找到两种分组形式如下：
分组一。分组二。
2019数学建模A 图论部分作业
所谓套汇是指利用货币汇兑率的差异将一个单位的某种货币转换为大于一个单位的。同种货币。假设1美元可以买0.62英镑，1英镑可以买9.22法郎，且1法郎可以买到0.18 美元。通过货币兑换，一个商人可以从1美元开始 得到0.62 9.22 0.18 1.028952美元 回到美元 从而获得2.9 的利润...
“数学建模”讲座 图论方法及其建模
数学建模 讲座 数学建模中的图论方法。图论是离散数学的重要组成部分，它对于自然科学 工程技术 经济管理和社会现象等诸多问题，能够提供有力的数学模型加以解决，特别在国内外大学生数学建模竞赛当中，有不少问题可以应用图论模型解决。我们在此有针对性地把图论的骨干概念和结论以及相关的有效算法做一简要介绍，愿听...
图论大作业
图论及其应用 大作业。第一题 讲过 2.1.9证明 若g是森林且恰有2k个奇点，则在g中有k条边不重的路p1,p2.pk,使得e g e p1 e p2e pk 证明 对奇点数k使用数学归纳法。当k 1时，g是森林，且有且只有2个奇点。g只能为一颗树，且g的所有奇度顶点为两个1度顶点。g是一条路。满...