数学建模中的图论方法
- 格式：pdf
- 大小：118.79 KB
- 文档页数：3
数学建模中的图论方法
一、前言
我们知道，数学建模比赛中有问题A和问题B。一般而言，问题A是连续系统中的问题，问题
B是失散系统中的问题。因为我们在大学数学教育内容中，连续系统方面的知识的比率较大，而离散数学比率较小。所以好多人有这样的感觉，A题下手快，而B题不好下手。
其他，在有限元素的失散系统中，相应的数学模型又可以区分为两类，一类是存在有效算法的所谓P类问题，即多项式时间内可以解决的问题。但是这种问题在MCM中特别少见，事实上，由
于比赛是开卷的，参照有关文件，使用现成的算法解决一个P类问题，不可以显示参赛者的建模及解决实诘问题能力之大小；还有一类所谓的NP问题，这种问题每一个都还没有成立有效的算法，或许
真的就不行能有有效算法来解决。命题经常以这种NPC问题为数学背景，找一个详细的实质模型
来考验参赛者。这样增添了成立数学模型的难度。但是这也其实不是说没法求解。一般来说，因为问题是详细的实例，我们可以找到特其他解法，或许可以给出一个近似解。
图论作为失散数学的一个重要分支，在工程技术、自然科学和经济管理中的好多方面都能供给有力的数学模型来解决实诘问题，所以吸引了好多研究人员去研究图论中的方法和算法。应当说，
我们对图论中的经典例子或多或少仍是有一些认识的，比方，哥尼斯堡七桥问题、中国邮递员问题、四色定理等等。图论方法已经成为数学模型中的重要方法。好多灾题因为归纳为图论问题被奇妙地解决。并且，从历年的数学建模比赛看，出现图论模型的频次极大，比方：
AMCM90B－扫雪问题；
AMCM91B－找寻最优Steiner树；AMCM92B－紧迫修复系统的研制(最小生成树)
AMCM94B－计算机传输数据的最小时间(边染色问题)
CMCM93B－足球队排名(特点向量法)CMCM94B－锁具装箱问题(最大独立极点集、最小覆盖等用来证明最优性)
CMCM98B－灾情巡视路线(最优回路)等等。这里面都直接或是间接用到图论方面的知识。要说明的是，这里图论但是解决问题的一种方
法，而不是唯一的方法。
本文将从图论的角度来说明怎样将一个工程问题转变为合理并且可求解的数学模型，重视介绍图论中的典型算法。这里但是一些基础、简单的介绍，目的在于认识这方面的知识和应用，拓宽大家的思路，希望起到抛砖引玉的作用，要掌握更多还需要我们进一步的学习和实践。
二、基本观点和性质
第一给出图论中的一些基本观点。
1．一个图G由一个极点集V和一个边的集E组成。E中每个元素e是连结极点集V中两个顶点u和v的边，称e与u，v关系。我们规定连结两个极点u、v至多有一条边，且一条边的两个顶
点不重合，这种图称为简单图。
2．极点集为V，边集为E的图G平时记为G=（V，E）。图G1=（V1，E1）称为G的子图，如
果V1V，E1E。
3．极点v的度(或“次”)是指与v有关系的边的个数。图G的度数之和为边数的两倍。4．若图G中随意两个极点u、v之间都存在连结它们的路，称G为连通图。5．W=v0e1v1e2ekvk，此中eiE，vjV，ei与vi-1，vi关系，称W是图G的一条道路。
v0是起点，vk是终点；各边相异的道路叫做行踪，各极点相异的道路叫做轨道；起点和终点重合的道路为回路；起点和终点重合的轨道为圈；包含图中每条边的回路称为Euler回路；含Euler回路的图称为Euler图。
6．一个无圈的连通图称为树。树是最简单而最重要的一类图。树有以下重要性质：性质：
1)在树中去掉随意一条边，所得的图是不连通的。
2)在树中随意两个不相邻的极点u、v之间增添一条新的边，所得的图恰有一个圈。下述定理是树的判判断理：定理：若图G拥有以下性质中的两条，则它是树，且也拥有第三条性质。
(1)．G是连通图；
(2)．G没有圈；
(3)．G的极点数=G的边数+1。7．假如图G=（V，E）的子图Gt=（Vt，Et）是一个树，且Vt=V，称Gt是G的生成树。G连通的充要条件是G有生成树。生成树一般而言数目很大。
8．设对图G=（V，E）的每一条边图)。假定G是连通的赋权图，要找Ge恩赐一个实数W（e），称为e的权，G称为赋权图(加权的连通子图G*=（V，E*），使得W（G*）=为最eE小。显然G*应为G的一个生成树。G的权最小的生成树称为G的最小生成树。
三、算法介绍3．1最短轨道问题W(e)背景：给定连结若干城市的铁路网，追求从指定城市v0到各城v去的最短道路。
数学模型：图G为一赋权图，对任给的vV(G)，追求轨道P(v0,v)，使得
W(P(v0,v))=min{W(P),P取自所有v0到v的轨道会合}此中W(P)是轨道P上各边权之和。
这一问题可用迪克斯特拉(Dijkstra)算法解决。基本思想：从起点v0开始，渐渐找寻抵达各点的最短路，在每一步都对极点记录一个数，称之为该点的标号，它表示v0到该点的最短距离的上界，或就是v0到该点的最短距离。实质上每一步都经过把最少一个拥有T标号的点变为P标号(即把一个不是最短距离标号的极点变为是最短距离标号的极点)，这样最多经过|V(G)|-1步便可达成。
步骤：记l(v)为v0到v的距离。
(1)l(v0)=0，l(v)=，(vv0)；S0={v0}，i=0。(2)对vSi，min{l(v)，l(vi)+w(viv)}取代l(v)；这样找到点vi＋1使得l(v)取最小值，v(i＋1)(Si的余集)。令S(i＋1)＝Si＋{v(i+1)}。
(3)i=|V(G)|-1时停止，不然，i+1，转到(2)。实例：CMCM94A－公路选址问题。3．2求最小生成树
1．克罗斯克尔(Kruskal)算法(1956年)，俗称“避圈法”背景：筑路选线问题欲修建连结n个城市的铁路，已知i城与j城之间的铁路造价为Cij。设计
一个线路图，使总造价最低。
解析：选线问题的数学模型是在连通加权图上求权最小的连通生成子图。显然，权最小的连通生成子图是一个生成树，即求取连通加权图上的权最小的生成树，这就归纳为最小生成树问题。这个问题可由克罗斯克尔(Kruskal)算法解决。
思路：从“边”着手选最小生成树。步骤：设G为由m个节点组成的连通赋权图。
(1)先把G中所有的边按权值大小由小到大从头摆列，并取权最小的一条边为树T中的边。即选
e1E，使得w(e1)＝min。(2)从剩下的边中按(1)中的摆列取下一条边。若该边与前面已取进T中的边组成一个回路，则舍弃该边，不然也把它取进T中。若e1，e2，，ei已经选好，则从E－{e1，e2，，ei}中采用ei＋1，使得G[{e1，e2，，ei，ei+1}]中无圈，且w(ei+1)=min。
(3)重复步骤(2)，直到T中有m－1条边为止。则T为G的最小生成树。
优选
