最新数学建模之图论模型讲解

各种图论模型及其解答摘要：本文用另一种思路重新组织《图论及其应用》相关知识。

首先，用通俗化语言阐述了如何对事物间联系的问题进行图论建模；接着从现实例子出发，给出各种典型图论模型，每种图论模型对应于图论一个重要内容；再者，介绍相关知识对上述提到的图论模型涉及的问题进行解答；最后，补充一些图论其他知识，包括图论分支、易混概念。

符号约定：Q(Question)表示对问题描述，M(Modeling)表示数学建模过程，A(Answer)表示原问题转化为何种图论问题。

一、引言图论是研究点、线间关系的一门学科，属于应用数学的一部分。

现实生活中，凡是涉及到事物间的关系，都可以抽象为图论模型。

点表示事物，连线表示事物间的联系。

整个求解过程如下：原问题——>图论建模——>运用图论相关理论求解——>转化为原问题的解整个过程关键在于图论建模，所谓图论建模，就是明确点表示什么，连线表示什么，原问题转化为图论中的什么问题。

存在以下两种情况：①若事物间联系是可逆的(比如双行道，朋友)，则抽象成无向图②若事物间联系是不可逆的(比如单行道，状态转化不可逆)，则抽象成有向图如果需要进一步刻画事物间的联系（比如城市间的距离），就给连线赋一个权值，从而抽象成赋值图。

综上，根据实际问题，可建模成下列图论模型的一种：无向赋权图、有向赋权图、无向非赋权图、有向非赋权图。

例1.宴会定理：任何一宴会中，一定存在两个人有相同的数量朋友M：点表示人，连线表示当且仅当该两个人是朋友A：问题转化为任何一个图一定存在两个顶点的度相等二、图论模型接下来介绍若干典型的图论模型，每种模型几乎对应于图论的一个重要内容，这些内容将在第三章进行讨论，也就给出了这些模型的解答思路。

2.1 偶图模型凡涉及两类事物间的联系（即只考虑两类事物间的联系，而不考虑同类事物间的联系），均可抽象成偶图模型。

作图时，将两类事物分成两行或者两列。

这类模型通常被包含在后续的模型中，但因许多现实问题可抽象成该模型，所以单列出来讨论。

. 图论一．最短路问题问题描绘：找寻最短路径就是在指定网络中两结点间找一条距离最小的路。

最短路不只是指一般地理意义上的距离最短,还能够引申到其他的胸怀,如时间、花费、线路容量等。

将问题抽象为赋权有向图或无向图 G ，边上的权均非负 对每个极点定义两个标记（l(v)，z(v)），此中：l(v)：表示从极点到v 的一条路的权 z(v)：v 的父亲点，用以确立最短路的路线 ：拥有永远标号的极点集算法：即在每一步改良这两个标记，使最后 l(v)为最短路的权 输入：G 的带权毗邻矩阵w(u,v) 步骤： （1） 赋初值：令l(u 0) 0，对v u 0，令 l(v) ，S={u 0}，i 0。

（2）面S 会合的点），用min{l(v),l(u)uS i极点u 和v 之间边的权值。

计算极点记为u i1，令S i1S i（3）w(uv)} 取代l(v)，这里w(uv)表示 l(v)}，把达到这个最小值的一个V1，则停止；若i V1，则用i 1取代i ，转（2）算法结束时，从 u 0到各极点v 的距离由v 的最后一次编号 l(v)给出。

在v 进入S i 以前的编号l(v)叫T 标号，v 进入S i 以后的编号l(v)叫P 标号。

算法就是不停改正各极点的T 标号，直至获取P 标号。

若在算法运转过程中，将每 一极点获取P 标号所由来的边在图上注明，则算法结束时，u 0至各极点的最短路也在图上标示出来了。

理解：贪婪算法。

选定初始点放在一个会合里，此时权值为0初始点搜寻下一个相连结点，将所有相连结的点中离初始点近来的点归入初始点所在的会合，并更新权值。

而后以新归入的点为起点持续搜寻，直到所有的点遍历。

..{u i1}。

若iu Si m in{.Matlab代码：function[mydistance,mypath]=Dijk(a,sb,db);%sb为起点，db为终点n=size(a,1);visited(1:n)=0;%n为结点数visited为结点标号distance(1:n)=inf;distance(sb)=0;%起点到各终点距离的初始化visited(sb)=1;u=sb;%u为新的P标号极点（初始点）parent(1:n)=0;%父节点的初始化%经过以下一个for..end便能够找到最短路径及该最短路径对应的最短行程fori=1:n-1%(找所有未标号的点)id=find(visited==0);%查找未标号的极点forv=id%找到一个未标号的点vifa(u,v)+distance(u)<distance(v)%uv之间的距离+起点到u的距离小于v到起点的距离（第一次是无量大的，所以第一次必定知足，下一次则找比这个点到u距离小的v）distance(v)=distance(u)+a(u,v);%改正标号值则v到原点的距离（权）改正。

数学建模中的图论方法一、前言我们知道，数学建模比赛中有问题A和问题B。

一般而言，问题A是连续系统中的问题，问题B是失散系统中的问题。

因为我们在大学数学教育内容中，连续系统方面的知识的比率较大，而离散数学比率较小。

所以好多人有这样的感觉，A题下手快，而B题不好下手。

其他，在有限元素的失散系统中，相应的数学模型又可以区分为两类，一类是存在有效算法的所谓P类问题，即多项式时间内可以解决的问题。

但是这种问题在MCM中特别少见，事实上，由于比赛是开卷的，参照有关文件，使用现成的算法解决一个P类问题，不可以显示参赛者的建模及解决实诘问题能力之大小；还有一类所谓的NP问题，这种问题每一个都还没有成立有效的算法，或许真的就不行能有有效算法来解决。

命题经常以这种NPC问题为数学背景，找一个详细的实质模型来考验参赛者。

这样增添了成立数学模型的难度。

但是这也其实不是说没法求解。

一般来说，因为问题是详细的实例，我们可以找到特其他解法，或许可以给出一个近似解。

图论作为失散数学的一个重要分支，在工程技术、自然科学和经济管理中的好多方面都能供给有力的数学模型来解决实诘问题，所以吸引了好多研究人员去研究图论中的方法和算法。

应当说，我们对图论中的经典例子或多或少仍是有一些认识的，比方，哥尼斯堡七桥问题、中国邮递员问题、四色定理等等。

图论方法已经成为数学模型中的重要方法。

好多灾题因为归纳为图论问题被奇妙地解决。

并且，从历年的数学建模比赛看，出现图论模型的频次极大，比方：AMCM90B－扫雪问题；AMCM91B－找寻最优Steiner树；AMCM92B－紧迫修复系统的研制(最小生成树)AMCM94B－计算机传输数据的最小时间(边染色问题)CMCM93B－足球队排名(特点向量法)CMCM94B－锁具装箱问题(最大独立极点集、最小覆盖等用来证明最优性)CMCM98B－灾情巡视路线(最优回路)等等。

这里面都直接或是间接用到图论方面的知识。