图论算法应用【图论的应用】

数学与统计学院

图论论文

课程名称 图论及其应用

题 目 图论中的应用

姓 名 邵雪莲

学 号 [1**********]19

专 业 数学与应用数学10级1班

图论的应用

摘要：

图论从诞生至今已近300年，但很多问题一直没有很好地解决。随着计算机科学的发展，图论又重新成为了人们研究讨论的热点，图形是一种描述和解决问题直观有效的手段，这里给出图论在现实生活中的一些应用。

引言：

虽然最早的图论问题追溯1736年(哥尼斯堡七桥间题) ，而且在19世纪关于图论的许多重要结论已得出。但是直到20世纪20年代图论才引起广大学者的注意并得以广泛接受和传播。

图论即形象地用一些点以及点与点之间的连线构成的图或网络来表示具体问题。利用图与网络的特点来解决系统中的问题，比用线性规划等其他模型来求解往往要简单、有效得多。图论就是研究图和网络模型特点、性质和方法的理论。图论在许多领域, 诸如物理、化学、运筹学、计算机科学、信息论、控制论、网络理论、社会科学以及经济管理等各方面都有广泛的应用, 它已经广泛地应用于实际生活、生产和科学研究中。

1首先：图论可以解决一些

看似很难实际上却很简单的

问题：

例一：一个部门中有25

人，

由于纠纷而使得关系十分紧张，是否可便每个人与5个人相处融洽? 则可以建立一个图的模型，最基本的问题是如何描述它—什么是结点，什么是边? 在本问题中，没有太多的选择，只有人和纠纷。我们可试着用结点来代表人。用边来代表图中结点之间的关系，这是很常见的。在这里结点之间的关系是“关系是否融洽”，因此，若两个结点(人) 关系融洽，那么就在它们之间加上一条边。现在假设每个人与其他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 是有向边的集合. 若∈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 的有向边.选课问题的抽象借助有向无回路图, 我们可把选课问题抽象为在有向无回路图中寻找拓扑有序序列. 实行学分制的各个院系, 在按排教学计划时, 必须考虑到课程之间的领先关系, 首先把该专业必修课程之间的依靠关系抽象为有向无回路图, 然后从有向无回路图中找到多个拓扑有序序列。通过把课程之间领先关系转化为有向无回路图, 进而把选课问题转化为在有向无回路图中寻找拓扑有序序列

问题, 从而成功地解决了高校学生的选课问题。

二、图论在单词接龙中的应用

背景：

有这样一个古老的数学问题。假设有许多张卡片, 每张卡片上都写着一个英文单词, 现在要把这些卡片按照一定的顺序连成串。这个顺序要求每张卡片(第一张卡片可以除外) 上的单词的首字母恰好是前一张卡片上的单词的尾字母, 并且要求每张卡片只能用一次, 简单地说就是“单词接龙”。有一些单词组通过适当的组合是可以完成接龙的, 例如, “teach ”, “teeth ”, “yet ”, “happy ”。但是某些单词组却不具备这样的性质, 比如“ok ”, “old ”, “deep ”, “king ”。问题的关键是能否找出一种科学的方法快速、准确地判断一组单词是否可以按照上述规则完成接龙呢? 可以运用图论中的欧拉定理建立了数学模型, 来求解该问题。对任意一组单词, 可以判断出它们能否完成接龙。 图论知识：

定义：通过图G 的每条边一次且仅一次的回路称为欧拉回路。存在欧拉回路的图, 称为欧拉图。

定理1：无向连通图G 是欧拉图G 不含奇数度的结点(即G 的所有结点的度均为偶数) 。

定理2：一个连通(弱连通: 如果不考虑有向图中边的方向所得到的无向图是连通图，则有向图称为弱连通图。) 有向图具有欧拉回路的充要条件是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] Liu C L.离散数学. 刘振宏译. 北京:人民邮电出版社,1992.

[3] 周德民. 离散数学教程. 开封:河南大学出版社,1995.

[4] 卜月华. 图论及其应用. 东南大学出版社,2000

[5] 洪帆. 离散数学基础. 第2版. 武汉:华中理工大学出版社,2002.

[6] 严蔚敏, 吴伟民. 数据结构. 北京:清华大学出版社,1997.