图论的应用Word文件下载.docx
- 文档编号:8600378
- 上传时间:2023-05-12
- 格式:DOCX
- 页数:8
- 大小:120.81KB
图论的应用Word文件下载.docx
《图论的应用Word文件下载.docx》由会员分享,可在线阅读,更多相关《图论的应用Word文件下载.docx(8页珍藏版)》请在冰点文库上搜索。
在本问题中,没有太多的选择,只有人和纠纷。
我们可试着用结点来代表人。
用边来代表图中结点之间的关系,这是很常见的。
在这里结点之间的关系是“关系是否融洽”,因此,若两个结点(人)关系融洽,那么就在它们之间加上一条边。
现在假设每个人与其他5个人关系融洽。
在图一上显示出我们所描述的图的一部分,小张与小王、小李、小赵、小黄和小吴关系融洽,再没有其他人。
25个人均是这种情况。
这是否可能?
在图论中,一个重要的推论:
在任意图中,具有奇数度的结点个数必为偶数。
现在出现了矛盾:
有25(奇数)个具有5(奇数)度的结点。
因此,该间题是不可能实现的。
例二、一个国际会议,有a,b,c,d,e,f,g等7个人.已知下列事实:
a会讲英语;
b会讲英语和汉语;
c会讲英语、意大利语和俄语;
d会讲日语和汉语;
e会讲德语和意大利语;
f会讲法语、日语和俄语;
g会讲法语和德语。
试问这7个人应如何排座位,才能使每个人都能和他身边的人交谈?
则可以建立一个图的模型,确定结点和边。
这里有“人和语言”,那么我们用结点来代表人,于是结点集合v={a、b、c、d、e、f、g}。
对于任意的两点,若有共同语言,就在它们之间连一条无向边,可得边集E,图G=(V、E),如图二:
如何排座位使每个人都能和他身边的人交谈?
问题转化为在图G中找到一条哈密顿回路的问题(哈密顿回路即是通过每个结点一次且仅一次的回路)。
而abdfgeca即是图中的一条哈密顿回路,照此顺序排座位即可。
2下对实际生活中的具体问题进行的分析:
一、图论在高校选课中的应用
背景:
随着高校教学体制改革,越来越多的高校实行了学分制.在学分制度下,学生只要选修一定量的课程,修完规定的学分,即可毕业.其中有一部分课程是必修课,是培养专业素质的根基.在必修课程中,有些是基础课,它们独立于其他课程,必须先修;
而另一些是后续课程,必须在学完作为它的基础的先修课程以后,才能开始.这些先决条件决定了课程之间的领先关系.因此,每个专业的学生在选修必修课程时,必需考虑到课程之间的领先关系.研究选课问题具有重要的现实意义。
图论知识:
设G=(V,E)是简单有向图,其V是顶点的有穷非空集合,E是有向边的集合.若<
vi,vj>
∈E,则<
表示从顶点vi到顶点vj的一条有向边,且称vi是有向边<
的初始点,vj是有向边<
的终结点,vi是vj的先驱,vj是vi的后继.顶点vi的度是和vi相关的边的数目;
以顶点vi为初始点的有向边的数目称为vi的出度;
以顶点vi为终结点的有向边的数目称为vi的入度。
定义:
设G=(V,E)是有限有向简单图,若存在顶点集V上的一种标顺序,得到一个顶点序列{v1,v2,…vi,…vj,…vn},使得对于任意的j>
i,顶点vj一定不是顶点vi的先驱,则称该顶点序列为拓扑有序序列.
定理1:
有限有向图G存在拓扑有序序列的必要条件是G中至少存在一个顶点,其入度为0.
定理2:
有限有向图G存在拓扑有序序列当且仅当G中无回路.
推论:
G是有向树或森林当且仅当有向图G存在拓扑有序序列.
模型建立:
课程之间领先关系的抽象我们利用图论中有向无回路图的有关知识,把课程之间领先关系转化为有向无回路图中的有向边.其构造有向无回路图的方法是:
图中的顶点表示课程,有向边表示课程之间的领先关系;
若课程x是课程y的先决条件,则图中出现从顶点x到顶点y的有向边<
x,y>
.选课问题的抽象借助有向无回路图,我们可把选课问题抽象为在有向无回路图中寻找拓扑有序序列.实行学分制的各个院系,在按排教学计划时,必须考虑到课程之间的领先关系,首先把该专业必修课程之间的依靠关系抽象为有向无回路图,然后从有向无回路图中找到多个拓扑有序序列。
通过把课程之间领先关系转化为有向无回路图,进而把选课问题转化为在有向无回路图中寻找拓扑有序序列问题,从而成功地解决了高校学生的选课问题。
二、图论在单词接龙中的应用
有这样一个古老的数学问题。
假设有许多张卡片,每张卡片上都写着一个英文单词,现在要把这些卡片按照一定的顺序连成串。
这个顺序要求每张卡片(第一张卡片可以除外)上的单词的首字母恰好是前一张卡片上的单词的尾字母,并且要求每张卡片只能用一次,简单地说就是“单词接龙”。
有一些单词组通过适当的组合是可以完成接龙的,例如,“teach”,“teeth”,“yet”,“happy”。
但是某些单词组却不具备这样的性质,比如“ok”,“old”,“deep”,“king”。
问题的关键是能否找出一种科学的方法快速、准确地判断一组单词是否可以按照上述规则完成接龙呢?
可以运用图论中的欧拉定理建立了数学模型,来求解该问题。
对任意一组单词,可以判断出它们能否完成接龙。
通过图G的每条边一次且仅一次的回路称为欧拉回路。
存在欧拉回路的图,称为欧拉图。
无向连通图G是欧拉图G不含奇数度的结点(即G的所有结点的度均为偶数)。
一个连通(弱连通:
如果不考虑有向图中边的方向所得到的无向图是连通图,则有向图称为弱连通图。
)有向图具有欧拉回路的充要条件是G的每一个结点的入度和出度相等。
具有欧拉路的充要条件是除起点和终点外,每个结点的入度等于出度。
对于起点,其出度比入度多1,对于终点,其出度比入度少1。
假设不区分字母的大小写,可以把所有的英文字母看成是26个节点,把每一个单词看作是一条有向边,即弧。
这样,弧头就是单词的首字母,弧尾就是单词的尾字母,且弧头、弧尾必然都在A~Z这26个点当中。
一组单词就可以构成一个节点数有限的有向图,模型建立起来了,而判断单词能否完成接龙的问题也就转化成了一个图论问题,即判断一个有向图中是否存在欧拉回路或者欧拉路。
而且由于图的点数最多为26个,若经过合理地设计,算法的复杂度可降到常数级。
可以对定理做一个简单地应用。
“teeth”,“teach”,“happy”,“yet”这4个单词可以完成接龙,即teeth—happy—yet—teach,它们构成的有向图如图3所示。
“old”,“ok”,“king”,“deep”这4个单词无法完成接龙,它们构成的有向图如图4所示。
这是观察的结果,可以再从图论的角度证明之。
若能一笔把这些单词连起来,则所有单词构成的有向图中最少存在着一条欧拉路。
当然,也可能是欧拉回路。
图3是连通的有向图,它没有欧拉回路,但存在欧拉路。
图3中T点的入度为2,出度为1,出入度相差为1;
H点的出度为2,入度为1,出入度相差为1;
Y点的入度为1,出度为1,出入度相等。
因此,图3是满足定理2的“除两个结点外,每个结点的入度等于出度。
对于这两个结点,一个结点的出度比入度多1,另一个结点的出度比入度少1”这个充要条件的,故存在欧拉路,可以完成接龙。
再看图4,其中没有回路,且O点的入度为2,出度为0,出入度之差为2,因此不可能有欧拉路,故不能完成接龙。
图论的正确应用大大降低了单词接龙求解的复杂度。
三、图论在邮政中的应用
纵观这些年我国邮政事业,其发展远远落后于经济增长的需求,突出表现在邮政运输能力的薄弱上,邮政运输具有全程全网,联合作业的特点,要求各部分邮路都能做到环环相和,并和邮件处理环节相配合,以最快的速度传递信息载体,所以在组建邮运网这项复杂的系统工程中,不仅要科学地组织邮件运输,还要组织好与邮件运输有紧密联系并相互交叉的处理作业环节。
图论中的图是由点及点之间的连线构成的,反观世界中某些对象之间的某个特定的关系。
用点表示所研究的对象,用点与点之间的连线这两个对象之间有特定的关系。
在实际问题时不仅要表示两个对象之间有无关系,还要这两个对象之间的数量,如距离、时间、费用称之为权,则图连同边上的权称为赋权图。
如果对图G=(V,E)的任何两个顶点u和v,G中存在一条(u-v)的路,则称G为连通图。
如果没有规定方向,连通图中只各点,且总长最短的问题即为最小数问题。
如规定了方向时则称为最短路问题,对于连接两个城市的所有公路连接形成的整个网络来说,两个城市之间的最大通行能力即为最大流问题。
所谓最大流问题就是在容量网络中,寻找流量最大的可行流.
定义1设G=(V,)为有向图,在V中指定一点称为发点(记为vs),和另一点称为收点(记为vt),其余点叫做中间点.对每一条边vivj∈E,对应一个非负实数Cij,称为它的容量.这样的G称为容量网络,简称网络,记作G=(V,E,C).
定义2网络G=(V,E,C)中任一条边vivj有流量fij,称集合f={fij}为网络G上的一个流.满足下述条件的流f称为可行流:
①(限制条件)对每一边vivj,有0≤fij≤Cij;
②(平衡条件)对于中间点vk有∑fik=∑fkj,即中间点vk的输入量=输出量.如果f是可行流,则对收、发点vt、vs有∑fsi=∑fjt=Wf,
即从vs点发出的物质总量=vt点输入的量.Wf称为网络流f的总流量.
上述概念可以这样来理解,如G是一个运输网络,则发点vs表示发送站,收点vt表示接收站,中间点vk表示中间转运站,可行流fij表示某条运输线上通过的运输量,容量Cij表示某条运输线能承担的最大运输量,Wf表示运输总量.可行流总是存在的.比如所有边的流量fij=0就是一个可行流(称为零流).
从图论的观点出发,最小载集直接影响网络的运输能力,要想提高邮运的能力,首先应考虑改善最小截集中各条弧的容量,即各段邮路上运能,提高它们的通过能力。
另一方面,一旦最小截集中弧的通过能力被降低,就会使总的输送量减少。
下面具体应用“最大流算法”对一局部邮政网进行优化。
两个邮局V1和V2发往T1,T2,T3三地的邮件需经V3和V4两个经转局其中“O”中的数字为该局的最大处理能力,弧上所标的权值为该线路的最大运输能力。
现欲计算此邮运网的最大运输能力,并对结果进行分析,改善网中的薄弱环节,提高该网的最大运能,如图5。
这个问题属于多收点、多发点的网络最大流问题。
首先,虚拟一发点Vs和一收Vt点,将该问题转化为一个收点和发点,如图6所示:
其中弧(Vs,V1)的容量取所有以V1为起始点的弧的容量之和(或任一大于这个数的值),这里应等于20;
同样,弧(Vs,V2)的容量取作18+8=26,弧(t1,Vt),(t2,Vt),(t3,Vt)的容量分别取作12,22,17。
同时,由于V3和V4两经转局有处理能力的限制,这里将V3点转换为V3′和V3″两没有任何处理能力的点,(V3′,V3″)的容量为30;
同样转化为V4,得到了一个顶点无容量约束的网络,如图7所示。
根据最大流量法,对上图进行标号,找出增广链,并调整,直至无法进行为止。
结果如图8。
由此可得该网络的最大通过能力为40。
从图(5—8)不难看出,V3局的处理能力还有空余。
具体表现在弧(V3′,V3″)的流量小于容量,V4局的处理能力全部投入使用,并且能力严重不足;
邮路(V2,V4),(V4,V2)等还未达到满载,在空载现象,这和我们国家现阶段的情况是不相适应的。
要提高整个网络的通信能力消除部分空载现象和瓶颈环节,就必须提高邮路(V1,V3)和(V2,V3)的最大运输能力。
提高V4局的处理能力。
通过调查分析,V1—V3和V2—V3间主要依靠干线邮路的火车运邮;
V1,V3间的公路情况良好的。
同时由于V4的处理能力不足。
当V4局的邮件量大时,V局就会发生“堵塞”现象。
在物质投入一定的情况下,可在邮运高峰期加开V2—V3局之间达的运邮汽车班次,提高这一段邮路的局步运输能力,使V3局的处理能力能够得到进一步利用。
V4局的处理能力较差是由于该局的规模过小,机械设备缺乏,邮政工作人员基本上停留于手工作业。
针对这种情况,可给该局配置自动分捡机、悬挂输送机,叉车等一系列机械设备,增添一定面积的厂房,并对一部分工作人员进行培训,正确、高效、科学地使用生产设备,以期达到最大工作效率。
总结:
图论是组合数学的一个分支,一般的做法是用边来代表结点之间的联系。
凡有二元关系的系统,图论均可提供一种数学模型,因而它在许多科学领域和现实生活中具有越来越重要的作用。
本文不仅讨论了两个简单的图论实际应用问题,还具体分析了
(1)把高校必修课程之间的领先关系抽象为有向图,把选课问题抽象为在有向图中寻找拓扑有序序列问题,从而成功地解决了高校的选课问题.
(2)“单词接龙”的求解问题,运用图论中的欧拉定理建立了数学模型,该算法较之传统的穷举法明显地降低了复杂度。
(3)把图论的方法与邮政的实际情况结合起来,通过建立数学模型,将复杂的邮政问题转化为网络结构图,并运用最大流算法,对邮政运输网络进行分析,以达到优化邮政通信网,提高邮政经济效益和社会效益的目的。
实例结果表明,图论模型能直观和定量地描述具体问题中各环节之间的关系,使问题皆可得到简化,这为研究解决实际问题提供了一种更直观更简单的新方法.上述几例,可以看出图论的应用范围非常广泛。
图论方法在实际生活中的广泛应用,不仅能实现高效、高质解决问题,而且能加强对事件过程的全面控制和管理,降低成本,并进行有效的管理和决策分析。
另外只需确定结点和边各代表什么,建立图的模型,运用图论的理论和方法,许多离散的问题都可以得到解决。
从上面的例子我们可以看出,图论的应用十分广泛,如果我们在学习的过程中能打下坚实的基础,就有能力将图论的思想应用到纷乱复杂的现实问题中去。
参考文献:
[1]运筹学教材编写组·
运筹学·
清华大学出版社,1990
[2]LiuCL.离散数学.刘振宏译.北京:
人民邮电出版社,1992.
[3]周德民.离散数学教程.开封:
河南大学出版社,1995.
[4]卜月华.图论及其应用.东南大学出版社,2000
[5]洪帆.离散数学基础.第2版.武汉:
华中理工大学出版社,2002.
[6]严蔚敏,吴伟民.数据结构.北京:
清华大学出版社,1997.
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 应用