图论的应用

数学与统计学院图论论文课程名称图论及其应用题目图论中的应用姓名邵雪莲学号2010120101119专业数学与应用数学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是有向边的集合.若vi,vj∈E,则vi,vj表示从顶点vi到顶点vj的一条有向边,且称vi是有向边vi,vj的初始点,vj是有向边vi,vj的终结点,vi是vj的先驱,vj是vi的后继.顶点vi的度是和vi相关的边的数目;以顶点vi为初始点的有向边的数目称为vi的出度;以顶点vi为终结点的有向边的数目称为vi的入度。定义：设G=(V,E)是有限有向简单图,若存在顶点集V上的一种标顺序,得到一个顶点序列{v1,v2,…vi,…vj,…vn},使得对于任意的ji,顶点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的每条边一次且仅一次的回路称为欧拉回路。存在欧拉回路的图,称为欧拉图。定理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