图论在化学中的应用

2024-06-01

图论在化学中的应用（共3篇）

图论在化学中的应用篇1

龙源期刊网 http://.cn

图论在道路建设中的应用

作者：张可波郑大斌

来源：《科技创新导报》2012年第03期

摘要：在修建道路的过程中，如何既保证各地之间运输的需求又节约资源。这就是我们需要解决的问题。本文从当前我国经济已经进入到了一个以资源节约．提高效率为主的时代的前提出发。利用图论中的相关理论。较好地解决了道路网的量优化修建问题．井对这一类问题的解决提供一种新的思路。

关键词；道路建设最优化

最小生成树Dijkstra算法 Greedy算法

图论在化学中的应用篇2

1、图论的提出

图论是今年来比较活跃的数学分支之一,它研究的对象是图,我们致力所讨论的图并不是几何学中图形,而是客观世界某些具体事物间的联系的一个数学抽象,用顶点代表事物,用边表示各事物间的二元关系,我们就把相应的顶点连成一条边,这种由顶点及连接这些顶点的边所组成的图就是我们图论中所研究的图。一个图就是一个二元组,其中V是非空的顶点集合,E是边集合,而每条边总是与两个顶点关联。

2、图论的发展

图论起源于十八世纪普鲁士的哥尼斯堡,1736年欧拉关于哥尼斯堡的七桥问题的论文被公认为图论的首篇奠基性的论文,20世纪后,图论的应用参透到许多其他学科领域,如物理,化学,信息学,运筹学,博弈学,计算机网络,社会学,语言学,以及集合论,矩阵论等。从20世纪50年代以后,由于生产管理,交通运输,军事,计算机网络等方面的提出的实际问题的需要,特别是许多离散性问题的出现,以及有了大型计算机,而使复杂问题的求解成为可能,图论及其应用的研究得到了飞速的发展,终于成长为数学科学中一门独立的学科。

3、图论的应用

目前,图已经用来作为许多与对象的离散安排有关问题的模型,比如计算机科学、运筹学、通讯科学、电网络分析、量子物理、结构化学、建筑学、经济学、语言学、生物学、社会学、遗传学、法律学、人类学、家系学和定理证明等。

在计算机科学中,利用图的单向树和有序树作为一种数据结构,可用于分析算法的好坏;在编码理论和程序设计中,利用图的霍夫曼树可以得到解决;利用最小树的概念及算法可以解决数据存放的问题;利用线图结构可处理数据管理系统。

运筹学中许多问题如最短路径、人员配置、生产计划和投资安排等可归结为二元关系的问题。比如用图的点表示某种货物可以储藏或装船的实际位置,从一处到另一处的一条有向边和记在这条边上的一个正数代表一条运输货物的水道和它的能力,这个能力给出同时可以通过的最大允许数目。

图与通讯网有极其相似之处,因而用图论方法解决通讯网络问题很自然。通过图可以研究通讯网络的结构性质、布线设计、控制方法以及阻塞的可能性等问题。

许多经济问题如税率涨落、供求关系引起商品流通动态特性的变化等都可用图来描拟并加以研究。

在心理学研究中,用点代表人,而人与人之间的关系比如爱、恨、交往和支配,用边表示,可以得到较好的研究。

4、图论在数学竞赛中的应用

学习图论可以锻炼学生的组合思维能力,提高运用数学工具描述和解决实际问题的能力。同时,图论对于考察青少年的智力水平提高分析问题与解决问题的能力大有益处,因此在一些国内外著名的数学竞赛中常常有一些与图论有关的试题。为了帮助参加数学竞赛的学生加深对数学竞赛中图论方法的理解。下面我们分析几个数学竞赛试题,看看怎样应用图论知识解决数学竞赛试题。

4.1、相互认识与比赛次数问题

定义和定理引入:

定义:

图:有若干个不同的顶点与连结其中某些顶点的边所组成的图形,其中顶点的个数称为阶。

相邻:若图中的两个顶点之间有边相邻,则称这两点相邻;如果顶点是一个边的端点,则称这个点是与这条边是相邻的。

环:有些顶点本身也是有边相连的,这样的边称为环。

平行边或重边:若两顶点之间有K(K≥2)条边相连,则称这些边为平行边或重边。

度:图G中与顶点V相邻的边数(约定环算做两条边)称为G中点V的度,记做d(v);若点V的度数为奇数,则称V为图G的奇顶点;若点V的度数为偶数,则称为图G的偶顶点;

简单图:如果图G中没有环,也没有平行边,则称图G为简单图。

定理1:设G是n阶图,则G中n个顶点的度之和等于边数的两倍。

即d(V1)+d(V2)+A+d(Vn)=2e.(其中e为边数)

定理2:对于任意的图G,奇顶点的个数一定是偶数。

例1:某会议有1991个人参加,已知他们每个人都至少和其中的一个人认识,证明:必有一个人至少和其他的两个人认识。

分析:我们可以用一个顶点表示一个人,两个人认识的则在相应的顶点间用边相连,则在这个1991阶的图中,由题意我们可以知道若每个人仅认识一个人的话,则1度的顶点个数为奇数。即d (V1)+d(V2)+A+d(V1991)≥1991。而有定理1知道,左端和必为偶数,即有d(V1)+d(V2)+A+d(V1991)≥1992。所以知道,必有一点的度数2,所以必有一个人至少认识其他的两个人。

例2:有2n(n≥2)个人在一起聚会,若每个人至少同其中n个人认识,证明:从这2n个人中总可以找出4个人来,这4个人可以围着圆桌坐下,使得每个人旁边都是他认识的人。

分析:我们用2rn个点表示2n个人,如果两个人认识,就在相应的两点间连一个条边,这样得到一个简单图G。我们要证的就是在图G中任一顶点Vi,有d(Vi)≥4,既证明G中必有四边形存在。由题意知,G中两个不相邻的点v1,v2,则有d(v1)+d(v2)≥2n,G中除v1、v2外只有2n-2个顶点,因此其中至少有两个点(记为v3,v4)与v1、v2相邻,于是v1、v2、v3、V4构成四边形。因此,可以知道总可以从2n个人中找出4个人来,使这四个人围着圆桌坐下,并且每个人旁边都是他认识的人。

例3:某地区网球俱乐部的20名成员举行14场单打比赛,每人至少上场一次。证明:必有六场比赛,其中12个参赛者各不相同。(美国数学奥林匹克试题,1989年)

分析:我们用20个点v1、v2、……、v20代表20名成员,两名选手比赛过,则在相应的顶点间连一条边,则可得到图G。由题意可知,图G中有14条边,并且有d(vi)≥1,i=1,2,……,20。由定理1,d(v1)+d(v2)+……+d(v20)=2×14=28。

在每个顶点vi处抹去d(vi)-1条边,由于一条边可能同时被两个端点抹去,所以抹去的边最多是(d(v1)-1)+(d(v2)-1)+L+(v20)-1)=28-20=8(条),故所抹去这些边后所得的图F中至少还有148=6条边,且图F中每个顶点的度至多为1。从而这6条边所相邻的12个人是各不相同的,即这6条边所对应的6场比赛的参赛者各不相同。

例4:某足球邀请赛有十六个城市参加,每市派出甲、乙两个队。根据比赛规则,每两个队之间至多赛一场,且同一城市的两队之间不进行比赛。比赛若干天后进行统计,发现除A市甲队外,其他各队已比赛过的场数个不相同,问A市乙队已赛过多少场?请证明你的结论。(全国高中数学联赛,1985年)

分析:将32个队用32个顶点v、v0、v1、v2、……、v30表示。其中v表示A市甲队。若两队已经赛过就在他们相应的顶点间连一条边,得到图G。在G中,d(vi)≤30,i=0,1,……,30。且当i≠j时,d(vi)≠d(vi)。故除点v外,其他顶点的度分别为0,1,2,……,30。不防设d(vi)=i(i=0,1,2,……,30)。对顶点v30来说,它只和顶点v0不相邻,v30与v0是同一城市的两队,在G中去掉顶点v0和v30及与它们相邻的边,得到图F,在图F中除点v外,各顶点的度仍不同,且都减小1,同样道理,可得v29与v1是同一城市的,依次推出v28与v2,……,v16与v14是同一城市的。于是v15与v是同一城市的,即v15是A市乙队,他已赛了15场。

通过以上对例题的分析,我们可以知道在用图论知识解决这类问题时,可以把人数化为顶点数,认识或者不认识以及比赛与否都可以用两点之间是否相连即用边来表示。这样就可化为图论的基本知识对问题进行求解。当然,像这类问题,比如握手,参加会议所用的语言数,参加舞会两个人是否跳舞……等等,都可以把它转化,然后求解。

4.2、欧拉图问题(一笔画问题)

定义定理引入:

定义:

欧拉图:从一顶点出发而每边恰好经过一次,有能回到出发的顶点的简单图。

定理5:图G是欧拉图的充要条件是:G是连通的,当且仅当奇顶点的度数等于0时,G是欧拉图。

例8:(七桥问题)18世纪,普鲁士的哥尼斯堡镇上有一个小岛,岛旁边流过一条河的两条支流,7座桥跨在两条支流上。假设A表示岛,B表示河的左岸,C表示右岸,D为两支流间的地区,a,b,c,d,e,f和g分别表示7座桥。问:一个人能否恰好经过每座桥1次,并且最后回到原出发点。

分析:既然岛与陆地是桥梁的连接地点,两岸陆地是桥梁通往的地点,就不妨把4处地点缩小成4个点,并把7座桥表示成7条边,便得到了七桥问题的模拟图,见图(b)。于是七桥问题等价于一笔画出上述图形的问题。A、B、C、D四个地点中任何一个点出发点都有先“出”后“回”,最后以回告终。而桥做为两点间的连接,通过时其中一个顶点肯定经过两次,所以不可能一笔画出。

4.3、平面图问题

定义定理引入:

定义:

平面图:如果一个图能画在平面上,使得它的边仅在端点相交,则称为平面图。

定理6:如果一个连通的平面图G中有v个顶点,e条边,f个面,那么v-e+f=2。

定理7:一个连通的平面简单图G有v(v≥3)个顶点,e条边,则e≤3v-6。

例10:空间中是否存在这样的多面体,它有奇数个面,每个面又都有奇数条边?(北京数学竞赛题,1956年)

分析:如果我们假设存在这样的多面体,则可以将这多面体的面用顶点表示,当且仅当两个面有公共棱时,在相应的顶点间连一边,得到图G。按题意,G中有奇数个奇顶点。也就是说图G的所有度数和是个奇数。由定理1,可知这样的图不存在,故这样的多面体不存在的。

例11:有n个车站组成的公路网,每个站至少有6条公路引出,求证:必有两条公路在平面上相交。

分析:n个车站用n个顶点表示,每两个车站有公路相通,则相应的两个顶点间连一边,得图G,由题意可知,G中每个点的度≥6。若G是平面图,则由于6n≤2e,即。又,所以有e=0。这个矛盾的结论表明G非平面图,所以,至少有两条公路在平面上相交。

5、总结

在研究以某种特定方式相互联系的物体或人之间的相互关系时,图论是一个很有用的工具,在许多的实例中,这些物体可以用一个图的顶点来表示,而它们之间的相互联系可以用顶点之间的连线表示。通过这样的转化,就可以化做有关图论知识应用的例子。这样就可以大大的简化做题过程,并且使学生做题水平得到很大的提高。

摘要：本文主要介绍了图论的提出,发展以及作为一门离散数学模型在解决实际问题中的应用。学习图论可以锻炼学生的思维能力,同时对于提高学生分析问题、解决问题的能力大有益处,因此在一些国内外著名的数学竞赛中,常常有一些与图论有关的试题。文章的目的就是让学生掌握和了解最基本的图论知识,开拓学生数学思维,学会应用图论知识解决问题。

图论在教师排课管理中应用篇3

【关键词】图论教法教师排课管理应用分析

【中图分类号】G715 【文献标识码】A 【文章编号】2095-3089（2016）11-0154-01

一、引言

课表的安排管理问题是学校教学中时间以及地点安排问题，这一问题的解决需要学校的相关教务管理人员花费较大强度的脑力与长时间的安排，是教务系统的核心工作。学生的课表安排需要结合许多因素，如：教室、班级以及上课时间等。因为要将多种因素结合考虑，所以通常情况下相关负责人员只能够手工安排课表。而这种方式在信息技术不断普及的状态下，效率显得十分低下。文章从图论的角度来对课表问题进行分析，提出最佳排课模型以满足实际需要。

二、排课的由来

排课是学校教学管理中十分重要而又具有较大难度的一项任务，它指的是给学校设立的老师教学课程的安排提供合适的时间，进而让各个老师的教学时间不会发生冲突，让老师的教学工作顺利开展。在老师的排课管理中，其中主要工作就是合理安排各项资源，例如：教学地点、学科以及时间等方面。通常情况下，是以一个循环周期的方法来适当的调配，让各项资源不会冲突。换种说法，排课是为了让老师与学生的时间以及上课地点进行统一。所以，课表则是排课工作的最终体现，课表算法是为了合理的安排老师与学生时间以及上课地点的统一。

三、传统排课模型算法的不足

为防止老师与学生时间以及上课地点发生冲突，则出现了排课算法。现今大部分的排课算法都是模拟手动排课的操作方法，利用计算机进行编排，老师的排课先按以往的编排习惯来调配老师与学生的时间以及上课地点，等到有问题出现时再进行相应的调控，但新的调整又有较大可能引发新的问题出现，这就无法很好的解决问题，并且没有效率。除此之外，这类算法还无法确保预算出的结论较优。

四、图论在教师排课管理中的应用

在编排课表的过程中，其主要目的是合理的安排老师与学生时间以及上课地点的统一。在这当中，有过多的可能性。因此可以把模型划分为两部分来考虑：一是老师与学生时间上的安排，二是老师与学生上课地点的安排，在进行这两种安排的过程中都可以运用图论方法来运作解决。

1.教师排课管理中时间的安排

教师排课管理中时间的安排其实质是指让教师在指定的时间内去给某个班级上课。在这当中，需要满足以下几个要求：首先，在同一个时间范围内教师只可以给一个班级上课;其次，不同班级在同一时间也只能有一个老师教课。运用图论方法来解决这一问题，如：有N个老师，分别是X1....XN，另外有M个班级，分别是Y1....YN，其中某个老师要教某个班级就要将这两者用线连接起来，若是一个星期之内某个老师给某个班级上了两次课，则用两条线相连，依次增加。使用二部图Z表示，让Z=（W，X，Y），其中W指的是连接老师与班级之间的线。具体如图一所示：

图一

众所周知，同一个顶点的边是相邻边。对每条边用不同颜色上色，一种颜色指代一段时间，拿大学为例，大学课程一般为两课时一节课，一天四节，一星期五天，因此在教师排课管理中边色数应为二十，指代的是二十段时间，一样的颜色指代的是一个时间段是由于相同时间当中每个老师只可以去一个班级教课，不同班级在同一时间也只能有一个老师教课。相邻边指代的是老师或学生是相同的，不能安排在同一时间段内上课，这就要求相邻边不可以使用相同颜色标明。

2.教师排课管理中上课地点的安排

教师排课管理中上课地点的安排其实质是让某个班级在一个时间段内到指定的上课地点上课，在这当中，需要满足以下几个要求：首先，在同一个时间范围内教师只可以给一个班级上课;其次，不同班级在同一时间也只能有一个老师教课。最后，要保证班级的总人数要比教师的容纳量小，确保学生有位置坐。但又不能让教师太大，否则会影响上课效果。运用图论方法来解决这一问题，如：在指定的时间段内，有五个班级X1至X5要安排不同教师上课，这时刚好又有五个教室Y1至Y5可以用，两者之间的关系如图二：

图二

根据不同教室的使用来赋值，设立的权限可以从以下数据看出：

5 5 5 2 1

2 4 4 1 2

0 2 1 0 0

0 0 3 3 3

1 4 4 1 2

其中这些数据中一个数表示的是不同班级分配到不同教室的适合程度，数字越大表示适合程度越高，就可以先行考虑。不过不管如此，到最后都要确保五个班级都要有适合的教室上课。

五、结语

将本文所述的两类方法结合，就能构建一张完整的课表，这样就能保证老师与学生时间以及上课地点能够保证同步。其中运用的实际方法就是图论法，图论运用至教师排课管理中，有助于解决以往排课过程中的困难，打破传统排课方法的局限性，进而防止老师与学生的上课时间发生冲撞，提高教学效率。

参考文献：

[1]吴丈虎，王建德.图论的算法与程序设计[J].北京：清华大学出版社，2013.06.（05）：39-43.