图论教学（精选9篇）
图论教学 篇1
摘要：该文介绍了课题组在图论及其应用课程的教学改革、教材建设和网站建设等方面的建设思路和方法。在图论及其应用课程的教学改革方面,论文从分类教学、探究方式学习教学等方面进行了阐述;在教材建设方面,提出了凸显具有较强课程体系、突出研究前沿、注重学科交叉渗透、强化学科应用等特点的教材编写思路。
关键词：图论,教学改革,课程建设,分类教学
图论及其应用是现代数学的一个重要分支,在自然科学、社会科学、机械工程中有重要的意义,生活中的大量事物之间可用图来描述,如交通图、规划图、调度图、关系图等。图论的发展历经大体上可以划分为三个阶段[1]:第一阶段是萌芽阶段,大约是从1736年到十九世纪中叶,欧拉提出的哥尼斯堡的七桥问题是最具代表性的工作;第二阶段是发展阶段,大约从十九世纪中叶到二十世纪中叶,图论相关问题得到研究者关注,如1852年的四色问题和1856年的汉密尔顿问题;第三阶段是二十世纪中叶到现在,大量的生活中的问题如生产管理、交通运输、通信、计算机等领域提出了一系列图论问题[1]。特别是现代生活中,计算机的普及使得复杂问题的求解成为可能,图论及其求解思想渗透到自然学科的各个领域,如运筹学、IT科学、控制论、社会科学和经济学等不同领域。图论越来越受到研究者广泛的重视,并得到包含数学家在内的各个学科研究者的广泛关注,各种国际学术交流活动十分活跃。
由于图论的可视化数据结构可以对自然科学和社会科学中许多问题进行描述和建模,越来越多的高校把它单独作为一门课程来开设,特别是研究生教育的大规模发展,图论及其应用这门课程在很多工科高校中得到重视。当前,国内许多高校已为信息与计算科学、计算机科学与技术、信息工程、控制与管理科学等学科的研究生开设了图论课程[2]。我校通信类、计算机类、自动化类、经管类、物理类、系统科学类等学科的研究生培养方案把《图论及其应用》作为学位课来开设。教学规模逐年扩大,每年有近600人愿意修这门课程,而大约有400人成功选课,受益面非常广泛。由于图论课程具有基本理论严谨、系统性强、高度抽象、方法灵活、强调算法、证明方法奇特等特点,而且研究内容广泛且解决问题的方法千变万化。这些都给教学带来一定的困难,如不加以探讨和改进,势必影响这门课程的教学效果。因此,必需对图论课的教学进行探讨。我们从在图论的教学内容、教学形式、教材建设等方面积极探索与实践,逐步形成了一套适合本科生或研究生学习的教学方法和教学模式。下面简单介绍这些方法,希望能够与同行共勉。
1 图论课程的教学现状和存在问题
当前,图论课程教学虽然取得了长足的进步,基本能够适应学生对课程基本知识的需求。但是,在课程建设、教材建设、信息化建设、师资队伍建设等方面相对比较滞后,特别是作为以信息学科为特色的教学研究型大学的本科生的选修课,也是我校研究生教育的一门公共基础课,该课程的教学存在一些问题。
1.1 教学内容陈旧
当前,我校图论课程或离散数学的图论部分的教学内容重理论、轻应用。图论课程有概念多、公式复杂和定理难证明、难理解等问题,在一定程度上造成教学难,证明抽象度高,学生难以理解,学生不能真正理解图论思想,更谈不上灵活运用图论知识来解决各种实际问题。多数授课方式都是采用先讲概念,然后用大部分时间来讲解定理及其证明,这主要源于图论的任课教师多数都是数学教师的缘故。但这种以概念定理为主的教学方式对图论这门的课程来说不太适合,它会使学生感到图论的学习非常枯燥。其次,评价学生图论课程学习的好坏,仍然是以传统的笔试为主,试题主要以例题或习题为样题。而我校相关专业的研究生学习图论这门课主要是通过图论中各种算法的学习来培养自己的编程能力或提高解决问题的能力。在教学内容上,我校图论课程的教学侧重于图论知识体系介绍和定理证明,对图论前沿的研究型课题的介绍相对较少,没有很好的激发学生学习后的创新思考。
1.2 图论教学没有很好地体现学科之间的渗透思想
图论课程是在不同学科发展基础上衍生形成的,它在很大程度上具有学科交叉、相互渗透的特点,因此图论的产生和发展得益于各学科的交叉与渗透以及各个学科对图的需求,如“树”就是来源于化学、电子学和纯数学[3,4]。图论提供的理论和方法应用于不同学科,特别是我校的计算机学科和通信学科。各学科的发展和需求又为图论提供新的概念、新的课题、新的研究方法和新的研究目标,推进图论的理论发展。但目前来讲,由于教师专业方向的限制,我们的教学主要围绕图论的基本数学理论,缺乏内容上的交叉和渗透,使得教学有些枯燥乏味,有的学生是为了应付学分而选课。
1.3 图论教学改革缺乏创新
当前,我校研究生教育发展迅速,专业对图论课程知识的需求日益凸显,图论课程的重要性得以提高。但是由于师资队伍发展相对较慢,而且对任课教师的专业要求较高,整个教师队伍的教学方法还有待优化,教师授课基本沿袭本科的教学模式,即“理论+证明+例子”的传统教学模式,它不利于调动学生学习积极性,也不能体现这门课程的应用性和学科交叉性,教材上的例题有些陈旧,且形式固化,很少能够与研究生的专业问题结合起来,几乎没有体现专业的需求和差异。
鉴于上述这些问题,图论的教学改革迫在眉睫。学校高度重视“图论及其应用”和“离散数学”课程的建设,设立专项的研究生创新计划,以重点项目的形式对“图论及其应用”课程进行专项建设,希望获得阶段性和实质性的结果,推动图论及其应用课程的教学改革,提高本科和研究生的教育教学质量。
2 图论教学改革的思考与探索
针对我校图论教学中存在的诸多问题,我们成立了专门的课题组,对该课程进行重点建设,在教学改革、教材建设、网站建设等方面进行了思考和探索。
2.1 教学改革
“图论及其应用”作为研究生后续课程如“算法分析与设计”、“算法复杂性分析”、“运筹与控制”、“信号分析”、“人工智能”、“网络优化”等的先修课程,也作为本科专业高年级的选修课,其重要性也是不言而喻的,很多研究生导师也要求学生选择这门课程。针对我校《图论及其应用》这门课程中概念比较多、论证方法独特而又千变万化的特征,再加上课时短(48学时),而且选修的学生遍及全校几乎所有的研究生专业和不同学科和层次(本科阶段有的同学没有学过),这些都给教学带来相当的困难,对这门公共基础课进行教学改革是我校研究生教学改革的重要方向。课题组在以下几方面试行教学改革尝试。
2.1.1 摸清学生底细,求同存异
作为一门研究生一年级的公共基础课,面对不同层次和专业(学科)的学生,求同存异是我们必然的选择。“求同”有两个方面的意思:一是尽管学生们各自情况不同,但要选修这门课应有一个基本的公共要求,这就是要求学生掌握图论中的基本概念和结论以及基本方法。二是摸清学生选修该课程的共同兴趣,为解决第一个问题,我们将在课堂教学上把主要精力放在基本概念的讲解上和透析上,着重在于方法的剖析和应用。为此,我们在教学中注重引入大量的实例使同学们首先弄清这些基本概念和图论中常用的基本方法,适当补充一些如狼羊过河、邮递员问题、作色问题等有趣味的问题,增加课程的科普性和应用性。同时,对一些难度较大的定理证明采用具体图例,讲清论证方法的基本思路和一些可能会使学生感到困难的关键地方。“存异”是力争保留同学们对图论这门课程知识需求的不同。在讲课时,我们将图论的知识点剖析后,收集和整理出这个知识点在不同学科中的应用,给学生抛出来,让他们根据自己的专业在课下去深究。如讲到最优二叉树时,我们可以引出通信的编码问题,让通信方向的学生自己去完善。因此,课堂上着重讲解使学生普遍感兴趣的应用,而专业性较强的应用,指出方向,让学生自己查阅文献去理解和学习。
2.1.2 针对专业需求,分类授课
由于我校研究生《图论及其应用》课程是公共基础课程,不同专业的需求和基础不同,为此,课题组试图分专业授课,增强授课的针对性,提高学生的学习质量,做到有的放矢。具体思路是,通过前几届学生选课情况的调查,并调研相关学院分管研究生教学的领导和部分代表性的研究生导师,了解相关学院和专业对《图论及其应用》课程的基本要求和专业要求。然后根据专业需求的不同,我们课题组将进行分组备课和分组教学,对基本的图论知识进行整体讲解,对不同专业需求的内容进行分组教学,最简单的操作方法是让学生尽可能根据专业需求和研究需求选课,我们课题组将公布不同教师的教学倾向和特点以及专业背景,让学生充分了解我们的意图,让图论课既有基础知识的学习,由于专业需求的深入教学,着力提高研究生教学质量。另外,我们试图开展专题讲座和讨论会的方式,来解答和讨论同学们提出的问题。对个别同学可以采用答疑、提供参考文献等方法来满足他们的求知渴望。
2.1.3 从接受学习到探究学习
教师如何将图论及其应用课程传统的接受学习方式转变为探究学习方式,从而提高学生的积极性,提高教学效率,是本课题组的尝试研究的一个重要内容。所谓接受学习[6]是以听讲和练习为主要方式的学习方式,以突出教学的结果为标志。在接受学习中,学习的主要内容是以定型的形式呈现给学习者的。因此接受学习是本科阶段的普遍教学方法,对于研究生来讲,面对知识总量不断增加,知识更新日益加快的当今社会,仅仅掌握一些基本的知识是远远不够的,因此,用这种学习方法为研究生教学无法实现研究生创新能力培养的目标。所谓探究学习指的是学生构建知识体系,形成科学研究方法的各种活动[6]。因此,在研究生的图论及其应用课程的教学过程中,引导学生探究学习的是本课题的重点。课题组试图研究《图论及其应用》的探究学习教学模式,旨在培养研究生的创新意识、应用知识的迁移能力、对待事实证据的科学态度、对科学探究所需要的多种能力。
2.2 教材建设
教材建设是课程建设的重要工作。课题组认为当前的教材虽然内容丰富,但有的内容过于理论化,有的内容体系复杂,对我校相关专业不太合适,有的内容过于简单,在一定程度上不能满足我校研究生教学的需求。为此,既要考虑到我校研究生的专业需求,又要结合研究生具有求知欲望强烈、勇于钻研的特点,同时兼顾各学科学生修课需要,我们正在组织编写一本深度和广度适中且具有我校特色的研究生“图论及其应用”课教材。课题组在为本科生多年开设离散数学和为研究生开设图论及其应用的教学实践基础上,试图编写“图论及其应用”新教材。该教材有以下几个特点。
2.2.1 突出现代特色,推出学科前沿课题
我们根据图论的本质和发展趋势,特别是信息学科的发展趋势和最新研究动态,重新编写教材,力争引进与我校学科相关的图论最新进展,强调图论在信息科学中的应用,特别结合通信背景、计算机背景、控制与自动化背景、光信息背景等介绍相关图的新理论,如Petri网与网络流的内容,增加哈弗曼编码及其应用的内容。从而引入学生去深入研究和讨论,激发学生的创新欲望和求知欲。
2.2.2 各学科的交叉和渗透
课题组通过多年的教学和调研发现目前的《图论及其应用》教材主要介绍图论在数学其他领域(如组合数学、矩阵论、拓扑学、群论、运筹学等)的应用,对信息学科中的应用介绍相对较少。本课题将在新的教材中除了介绍图论的基本理论和方法外,重点增加介绍图论在电子学、信息处理、管理科学、控制理论和计算机科学等方面的应用。并力争增加图论与其他数学分支的相互交叉和相互渗透上做一些介绍。借助于同构概念把图与群联系在一起,增加学科之间的渗透。
2.2.3 弱化证明,注重应用分析
图论来源于实践又服务于实践。从这个意义上讲我们将在《图论及其应用》教材中把理论和应用放在重要同等的位置。按照“定义一定理一应用”的编写模式,每章节的前一部分是定义和理论部分,紧接着介绍知识的应用部分,主要是应用图论的知识解决具体的问题。对于专业性很强的应用,如通信方向、计算机或控制方向的问题,我们在章末给出阅读指南;对图论在计算机科学应用方面感兴趣的同学可参阅《图论与算法分析》等等。这样将使学生在学习中结合自己的专业有的放矢地学习和讨论。另外,弱化定理证明,着重分析图论算法的思想,重点在于这些图论算法的程序实现和应用。
2.3 网站建设
为了展示图论课程的相关信息,我们进行图论及其应用课程的网站建设,建设成适合我校研究生教学的课程网站,试图通过网站传递课程的性质和目的,将授课计划、考试大纲、应用实例、案例分析等问题在网站上展示出来,同时把很多先关的参考文献和最新的研究论文放在网站,共同学们下载学习。完善网站内容,把网站建成课程的展示窗口,同时将网站也建成老师与学生的交流平台。为将该课程建设市级优质课程打下基础。
3 结束语
总之,图论课程的教学改革蕴含着丰富的内容,包括教学思想、教学方法、教学手段、课程建设和网站建设等。对图论的教学并没有固定的模式可循,在教学过程中,教师要转变教学观念,“以教师为主导、以学生为主体”,因材施教,以提高学生素质为根本宗旨,把握学科教育的本质和目的,以培养学生的创新精神、学习能力和实践能力为重点,采取各种有效手段和措施,充分挖掘学生的创造力和潜力,培养学生严谨、认真、规范的科学态度,使学生能利用所学的知识和掌握的技能去解决实际问题。
致谢:特别感谢重庆邮电大学研究生教育创新计划资助项目(No.Y201110)、重庆市研究生教育改革研究项目(No.yjg123103)、重庆市高等教育教学改革研究()和重庆市高等教育教学改革研究重点项目(3)的支持!
参考文献
[1]徐俊明.图论及其应用课程建设探索[J].教育与现代化,1997(2):41-46.
[2]黄晓学,苗正科.从七桥问题看图论的本原思想与文化内涵[J].数学教育学报,2008,17(4):22-25.
[3]图论课程教学改革的探索与实践[J].中国教育创新导刊,2010(26):53.
[4]谢政,戴丽,陈挚.关于图论课教学的思考[J].数学理论与应用,2005,25(4):139-140.
[5]刘广军,刘信生,陈祥恩.对图论课堂教学的探讨[J].周口师范学院学报,2009,26(2):46-48.
[6]杨朝凤.基于接受学习与探究学习的图论教学设计与实践[J].保山师专学报,2007,26(2):30-32.
图论教学 篇2
图论在道路建设中的应用
作者：张可波 郑大斌
来源：《科技创新导报》2012年第03期
摘要：在修建道路的过程中，如何既保证各地之间运输的需求又节约资源。这就是我们需要解决的问题。本文从当前我国经济已经进入到了一个以资源节约．提高效率为主的时代的前提出发。利用图论中的相关理论。较好地解决了道路网的量优化修建问题．井对这一类问题的解决提供一种新的思路。
关键词；道路建设 最优化
基于图论的图像分割软件设计 篇3
关键词：图像分割；图论；最小割；MFC
中图分类号：TP18 文献标识码：A 文章编号：1009-3044（2016）20-0183-02
1 概述
图像分割是计算机视觉中最基本最重要的研究内容之一，对图像处理、图像分析和图像理解起着关键性的作用。所谓图像分割是指根据图像的某个特定属性将图像划分为若干个互不交叠的区域，并从中提取目标的过程[1]。
图像分割的定义[2]：
2算法原理
2.1图论的基本概述
图论（Graph Theory）是数学的一个分支，它以图为研究对象。图论中的图是由点和连接两点的线所构成，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应的两个事物之间具有的某种关系[3]。
基于图论的图像分析指将待处理的图像映射为带权的无向连通图G=（V，E，W），节点集V是图I中所有像素点的集合，边集E表示连接两个邻接顶点的边的集合，W表示每条边权值的集合，边的权值反映了该边的两个顶点的差异或相似度。
权值集合W的构建是图像分割成功的关键，好的相似度度量函数需要体现出两个节点在顏色、亮度、距离等方面的相似程度。常用的相似度度量函数有特征空间的欧氏距离：
作为相似度的度量函数，前者的优点是直观且计算简单，后者的优点是与实际情况更加接近，但是运算量较大[4]。
2.2最小割/最大流方法
基于图论的分割方法是将整幅图像映射为图，图的顶点和图中像素一一对应，根据一定的割集准则将图划分为两个子图，使得子图之间的相似性最小，而子图内的相似性最大[5]。图割示意图如图1所示：
使得代价函数最小的划分即为图像的最佳分割，也即图的最小割。
最小割/最大流方法主要包括两大类[6]：推进重标记（Push relabel）方法和增广路径（Augmenting paths）方法。推进重标记法易于并行实现，通常采用GPU加速实现来提高效率。基于增广路径的方法通过标号不断生长一棵树，直到找不到关于可行流的增广路径为止。该类方法的计算复杂性和网络的节点数和边数无关，而与边上的权值有关。
3软件系统设计
3.1设计思路
3.2软件测试及结果
单击选择图像按钮读入待分割图像，根据图像中目标的形状选择交互方式，单击分割按钮运行分割程序，矩形交互和圆形交互分割结果分别如图3和图4所示：
从上图可以看出，分割结果图像边缘比较光滑，所设计软件操作简便且具有较好的分割效果。
4 结论
基于图论的分割方法可以将图像的全局分割与局部信息处理相结合，可减少由于图像离散化造成的误差，从而可获得良好的分割结果。本系统具有如下技术特点：（1）将原始图像，交互图像和分割后图像显示在同一界面上，运算结果形象直观，便于用户观察；（2）界面简洁，操作简单，运行效率和分割精度较高。
参考文献：
[1] 章毓晋. 图像分割[M].北京：科学出版社， 2000.
[2] 罗希平， 田捷， 诸葛婴，等. 图像分割方法综述[J]. 模式识别与人工智能， 1999（3）：300-312.
[3] 张建梅， 孙志田， 余秀萍. 基于图论的图像分割算法仿真研究[J]. 计算机仿真， 2011， 28（12）： 268-271.
[4] 杨帆，廖庆敏. 基于图论的图像分割算法的分析与研究[J]. 电视技术， 2006 （7）： 80-83.
[5] Sarkar S， Soundararajan P. Supervised learning of large perceptual organization： Graph spectral partitioning and learning automata[J]. Pattern Analysis and Machine Intelligence， IEEE Transactions on， 2000， 22（5）： 504-525.
数学建模在《图论》教学中的作用 篇4
数学模型是一种模拟，是用数学符号、数学式子、程序、图形等对实际问题本质属性的抽象而又简洁的刻画，它或能解释某些客观现象，或能预测未来的发展规律，或能为控制某一现象的发展提供某种意义下的最优策略或较好策略。数学模型一般并非现实问题的直接翻版，它的建立常常既需要人们对现实问题深入细微地观察和分析，又需要人们灵活巧妙地利用各种数学知识。这种应用知识从实际问题中抽象、提炼出数学模型的过程就称为数学建模。
数学建模所利用的方法基本上是方程、分析、统计、运筹、图论等常用数学工具，多数都要用到计算机进行数值计算和做图，有时还用到计算机模拟。因此，在大学《图论》课程教学活动中，教师如果能随时随处将数学建模思想和方法引入到教学内容中，使学生了解《图论》的相关概念、定理产生的历史背景，让学生在学习《图论》时，体会到图论知识与现实问题联系的紧密性以及应用的广泛性，这样才有利于激发学生的学习兴趣，帮助学生对图论知识的理解与吸收。
二、《图论》中的数学建模思想
自18世纪欧拉对哥尼斯堡七桥问题的研究以来，图论得到了深入而广泛的发展，已成为一门应用数学课程，在自然科学、社会科学、机械工程中均有重要的意义。由于《图论》课程概念多、公式复杂、定理难证明和难理解等特点，在一定程度上造成教学难，证明抽象度高，学生难以理解。学生不能真正理解图论思想，更谈不上灵活运用图论知识来解决各种实际问题，从而使学生感到《图论》的学习非常困难与枯燥。虽然《图论》课程中概念、定理比较多，初学者不易掌握，但是图论的概念和定理大多是从实际问题中抽象出来的，所以在教学中注重介绍各种概念和理论的实际背景，引导学生学习图论思想，探究图论的发展规律，从而将更好地帮助学生理解和掌握这些概念和理论。如何从实际问题中抽象出图论的相关理论，数学建模正是联系数学理论与实际的一座桥梁，是数学应用于科学和社会的一个很好的途径，是解决实际问题的强有力的工具。在图论某些定理证明的教学过程中可以适当地融入数学建模的思想与方法，把定理的结论看作一个特定的模型，需要去建立它。于是，当把定理的条件看作是模型的假设，可根据预先设置的问题情景，引导学生发现定理的结论，从而定理证明的方法也随之显现。
例1.设G=(V,E）为任意无向图，V={v1,v2,...,vn}，|E|=m，证明所有顶点的度数和等于2m，并且奇点个数为偶数。
证明该结论之前，首先任意选取若干个学生，让他们随机互相握手，并记下每个人的握手次数和每两人之间握手的次数，由此可得每个人握手次数总和是每两人之间握手次数的2倍，以及握过奇数次手的人数一定是偶数。互动之后介绍该定理称之为握手定理，从互动过程中可以建立定理结论的模型，并且证明的思路也就显而易见了。
三、数学建模提高学生学习《图论》的兴趣和应用意识
由于教学课时的限制，将数学建模的思想方法融入《图论》课程教学时，不能专门地让学生学习建模，只能通过一些简单的模型给学生介绍数学建模的思想及方法。《图论》是现代数学的一个重要分支，在自然科学、社会科学、机械工程中有重要的意义，其求解思想渗透到自然学科的各个领域。图论中的图是由若干个给定的顶点及若干条连接两个顶点的边所构成的图形。这种图形通常用来描述某些事物之间的某种特定关系：用顶点代表事物，用连接两个顶点的边表示相应两个事物间具有这种关系。这种图提供了一个很自然的数据结构，可以对自然科学和社会科学领域中的许多问题进行恰当的描述或建模。因此，可以通过设计一些与《图论》课程相关的课外建模活动，选择符合学生实际并贴近生活的一些图论问题，启迪学生的论文查阅意识和能力，指导学生阅读相关论文，最后以解题报告或小论文的形式提交他们的结果。
例2.有甲、乙、丙、丁、戊、己六名运动员报名参加A、B、C、D、E、F六个项目的比赛。表1中打“√”的是各运动员报名参加的比赛项目。如何安排六个项目的比赛顺序，使得每名运动员都不连续地参加两项比赛。
求解该问题时，可以先选取六名同学模拟一下实际问题，使学生理解该问题的实际背景，根据实际模拟情况，找出一种符合要求的比赛安排。再引导学生探究该问题与图论的联系，确定该问题的图论模型，从而帮助学生寻找解决该问题的答案。在该问题中，若把比赛项目作为研究对象，用点表示，如果两个项目有同一名运动员参加，在代表这两个项目的点之间连一条线。如图1：在该图中只要找出一个点的序列，使依次排列的两个点不相邻，即能做到每名运动员不会连续地参加两项比赛。例如A、C、B、F、E、D就是满足要求的一种安排方法。
通过课内外的数学建模思想及方法的渗透，有助于激发学生的创造性思维，唤醒学生进行创造性工作的意识，因为建模本身就是一项创造性思维活动，它不仅有一定的理论性，还有较强的实践性。结合课外数学建模活动的开展，增强学生应用数学的意识，运用所学的图论知识去参与解决实际问题的全过程。训练学生运用图论知识建立数学模型，解决实际问题的技能和技巧，是培养学生应用数学知识解决实际问题的重要途径。同时使学生体会到图论知识与现实问题联系的紧密性以及应用的广泛性，从而激发学生研究数学建模的兴趣，提高他们运用图论知识解决实际问题的能力，充分感受到图论的生机与活力，也进一步深入体会到了学习《图论》的重要性。在建模过程中也充分调动了学生应用图论知识分析和解决实际问题的积极性和主动性，学生充满了把图论知识和方法应用到实际问题之中去的渴望，使学生对以往数学课程教学中常见的枯燥、难懂、脱离实际的感受得到切实的改变，从而使《图论》课程的教学效果得到了明显提高。
四、结语
《图论》是一门既有趣又有较大难度的课程。传统的以概念、定理为主的教学模式使学生在学习《图论》的过程中感到非常困难与枯燥，很难调动学生学习的积极性，也无法体现该门课程的应用性。在《图论》课程教学中融入数学建模的思想和方法，提高了学生学习《图论》的兴趣。通过数学建模的方法，理论与实际相结合，使得枯燥的图论问题变得通俗易懂，既增强了学生的新奇感，激发了学生的求知欲，又能从中受到启迪，充分调动了学生主动地参与意识和自觉学习的积极性，极大地提高了学生的学习效率，培养了学生应用数学的意识。
摘要：在《图论》课程的教学过程中,根据教学内容适当引入数学建模的思想、方法,激发学生学习《图论》的兴趣,提高学生应用所学知识分析、解决实际问题的能力。
关键词：数学建模,《图论》,应用
参考文献
[1]王树禾.图论[M].北京:科学出版社,2004.
图论的起源和发展 篇5
关键词：团论,染色体,四色猜想
图论是组合数学的—个分支, 与其他的数学分支, 如群论、矩阵论、概率论、拓扑学、数值分析等有着密切的联系 (参见文献[1]) 。图论中以图为研究对象, 图形中我们用点表示对象, 两点之间的连线表示对象之间的某种特定的关系。事实上, 任何一个包含了某种二元关系的系统都可以用图形来模拟, 而且它具有形象直观的特点。由于我们感兴趣的是两对象之间是否有某种特定关系, 所以图形中两点间连接与否尤为重要, 而图形的位置、大小、形状及连接线的曲直长短则无关紧要。
20世纪后, 图论的应用渗透到许多其他学科领域。从20世纪50年代以后, 由于计算机的迅速发展, 有力地推动了图论的发展, 使图论成为数学领域中发展最快的分支之一。
一、图论的起源
图论是一个古老的但又十分活跃的数学学科, 也是一门很有实用价值的学科, 它在自然科学、社会科学等各领域均有很多应用。近年来它受计算机科学蓬勃发展的刺激, 发展极其迅速。应用范围不断拓广, 已渗透到诸如语言学、逻辑学、物理学、化学、电讯工程、计算机科学以及数学的其它分支中。
1736年是图论的历史元年。这一年, 欧拉 (L·Euler) 研究了哥尼斯堡城 (Königsberg) 的七桥问题, 发表了图论的首篇论文。欧拉也因此被称为图论之父。
古老而美丽的哥尼斯堡城濒临蓝色的波罗的海, 是著名的哲学家康德 (Immanuel Kant) 的出生地, 城中有一条普莱格尔 (Pregel) 河, 河的两条支流在这里汇合, 然后横穿全城, 流入大海。河水把城市分成4块, 于是, 人们建造了7座各具特色的桥, 把哥尼斯堡城连成一体, 如图1.1 (a) 所示。
早在18世纪, 这些形态各异的小桥吸引了众多的游客, 游人在陶醉于美丽风光的同时, 不知不觉间, 脚下的桥触发了人们的灵感, 一个有趣的问题在居民中传开。
谁能够从两岸A, B或两个小岛C, D中任一个地方出发一次走遍所有的7座桥, 而且每座桥都只通过一次?这个问题似乎不难, 谁都乐意用这个问题来测试一下自己的智力。可是, 谁也没有找到一条这样的路线。这个问题极大的刺激了德意志人的好奇心, 许多人热衷于解决这个问题, 然而始终未能成功。“七桥问题”难住了哥尼斯堡城的所有居民。哥尼斯堡城也因“七桥问题”而出了名。这就是数学史上著名的七桥问题。
问题看来不复杂, 但谁也解决不了, 也说不出其所以然来。1736年, 当时著名的数学家欧拉仔细研究了这个问题, 他将上述四块陆地与七座桥间的关系用一个抽象图形来描述 (见图1.1 (b) ) , 其中A、B、C、D分别用四个点来表示, 而陆地之间有桥相连者则用连接两个点的连线来表示, 这样, 上述的哥尼斯堡七桥问题就变成了由点和边所组成的如下问题:
试求从图中的任一点出发, 通过每条边一次, 最后返回到该点, 这样的路径是否存在?于是问题就变得简洁明了多了, 同时也更一般、更深刻。这样一来, 七桥问题就转变为图论中的一个一笔画问题。即能不能一笔不重复的画出图1.1 (b) 中的这个图形。
原先人们是要求找出一条不重复的路线, 欧拉想, 成千上万的人都失败了, 这样的路线也许根本不存在。于是, 欧拉接下来着手判断:这样不重复的路线究竟存不存在?由于这么改变了一下提问的角度, 欧拉抓住了问题的实质。最后, 欧拉认真考虑了一笔画图形的结构特征。
欧拉发现, 凡是能用一笔画成的图形, 都有这样一个特点:每当用笔画一条线进入中间的一个点时, 还必须画一条线离开这个点。否则, 整个图形就不可能用一笔画出。也就是说, 单独考察图中的任何一点 (起点和终点除外) , 这个点都应该与偶数条线相连;如果起点与终点重合, 那么, 连这个点也应该与偶数条线相连。
在七桥问题的几何图中, A、B、D三点分别与3条线相连, C点与5条线相连。连线都是奇数条。因此, 欧拉断定:一笔画出这个图形是不可能的。也就是说, 不重复地通过7座桥的路线是根本不存在的!天才的欧拉只用了一步就证明了这个难题, 从这里我们也可以看到图论的威力有多么的强大!
欧拉对七桥问题的研究, 是拓扑学研究的先声。
1750年, 欧拉又发现了一个有趣的的现象。欧拉得到了后人以他的名字命名的“多面体欧拉公式”。正4面体有4个顶点、6条棱, 它的面数加顶点数减去棱数等于2;正6面体有8个顶点、12条棱, 它的面数加顶点数减去棱数也等于2。接着, 欧拉又考察了正12面体、正24面体, 发现都有相同的结论。于是继续深入研究这个问题, 终于发现了一个著名的定理:
这个公式证明了多面体只有正四面体、正六面体、正八面体、正十二面体、正二十面体五种。这个定理成为拓扑学的第一个定理, 这个公式被认为开启了数学史上新的一页, 促成了拓扑学的发展。
二、图论的发展
从19世纪中叶开始, 图论进入第二个发展阶段。这一时期图论问题大量出现, 诸如关于地图染色的四色问题、由“周游世界”游戏发展起来的哈密顿 (W.Hamilton) 问题等。
图的染色问题一直是图论研究的焦点问题。最早记载染色问题的是英国伦敦大学 (University of London) 的数学教授德·摩根 (D.Morgan) 。
1852年, 一位刚从伦敦大学毕业的学生费南西斯·古色利 (F.Guthrie) 在研究英国地图时想到了一个奇怪的问题。这个问题被称为世界近代三大数学难题之一, 这就是著名的“四色猜想”。问题的起源是这样的:
古色利望着挂在墙上的英国地图发呆, 他边数着英国的行政区域, 边查找它们的位置, 同时还注意各区域的地图着色, 看着看着他突然发现, 该地图仅用四种不同的颜色便可以将地图中相邻的区域分开。古色利无法解释这一现象, 于是他写信给仍在大学读书的弟弟, 让他向该校有名的数学家德·摩根请教。摩根首先注意到:区分地图上的不同区域少于四种颜色不行。但遗憾的是摩根本人也未能解决这个问题。于是向自己的好友、著名数学家哈密顿爵士请教。哈密顿接到摩根的信后, 对四色问题进行论证。但直到1865年哈密顿逝世, 问题也没有能够解决。
1878年, 英国数学家凯莱 (Cayley) 在伦敦数学年会上正式提出该问题——平面或球面上的地图仅需四种颜色可以将任何相邻的两区域分开——且征求解答, 人称“四色猜想”的问题便引起了世界数学界的重视。许多一流的数学家纷纷参加了四色猜想的大会战。1878—1880年, 著名的律师兼数学家肯普 (Kempe) 和泰勒 (Taylor) 两人分别提交了证明四色猜想的论文, 宣布证明了四色定理, 大家都认为四色猜想从此也就解决了。但是数学家赫伍德 (Hedwood) 仍然花费毕生精力致力于四色研究, 前后整整60年, 终于在1890年发表文章指出肯普证明中的错误, 不过, 赫伍德却成功地运用肯普的方法证明了五色定理, 即一张地图能够用五种或者更少的颜色染色。不久, 加拿大数学家托特 (Tóth) 又举出反例, 否定了泰勒的证明。后来, 越来越多的数学家虽然对此绞尽脑汁, 但仍一无所获。于是, 人们开始认识到, 这个貌似简单容易的题目, 其实是一个可以与费尔马猜想相媲美的难题。
进入20世纪, 科学家们对四色猜想的证明基本上是按照肯普的想法在进行, 并陆续有所进展。1913年, 伯克霍夫 (Birkhoff) 在肯普的基础上引进了一些新技巧;1939年, 美国数学家富兰克林 (Franklin) 证明了22个以下区域都可以用四色着色。随后又有人给出了更多区域的情形, 直到1976年初, 人们还是仅能对区域数是96的地图主色的四色猜想给出证明, 但这些对区域数是自然数的情形来讲还远远不够。
1976年6月, 美国伊利诺斯大学的黑肯 (W.Haken) 和阿佩尔 (Appel) , 经过四年的艰苦工作, 在两台不同的电子计算机的帮助下, 用了1200个小时, 作了100亿次的判断, 终于完成了四色猜想的证明。四色猜想的计算机证明轰动的世界, 该证明不仅解决了一个历史一百多年的难题, 而且有可能成为数学史上亿系列新思维的起点。不过也有不少数学家并不满足于计算机取得的成果, 他们还在寻找一种简洁明快的书面证明方法。
在哈密顿的周游世界问题中, 他用一个正十二面体 (具有十二个五边形的面和二十个顶点) 的二十个顶点表示世界上的二十座大城市, 见图l.2。提出的问题是要求游戏者找一条沿十二面体的棱通过每个顶点恰好一次的闭路。图1.3所示的a, b, …s, t, a表示出了这样的一条闭路。由于运筹学、计算机科学和编码理论中的很多问题都可以转化为哈密顿问题, 从而哈密顿问题引起广泛的关注和研究。
我们看到, 正是上述那些似乎没有多大意义的游戏的抽象与论证的方法, 开创了图论科学的研究。遗憾的是, 由于当时社会生产落后, 对图论知识的要求甚寡, 这一学科的发展颇为迟缓, 甚至处于停滞状态。两百年以后, 即1936年, 匈牙利著名图论学家柯尼系 (König) 发表《有限图与无限图理论》, 这是图论的第一部专著, 它总结了图论二百年的主要成果, 是图论的重要里程碑。此后的五十多年, 图论经历了一场爆炸性的发展, 终于成长为数学科学中一门独立的学科。它的主要分支有图论、超图理论、极值图论、算法图论、网络图论和随机图论等。近二十年来, 图论在科学界可以说是异军突起, 活跃非常。
参考文献
[1]卜月华.图论及其应用.福建:东南大学出版社, 2002.
[2]卢开澄.图论及其应用.北京:清华大学出版社, 1984.
[3]王树禾.图论及其算法.北京:中国科技大学出版社, 1999.
[4]邹庭容.数学文化欣赏.武汉:武汉大学出版社, 2007.
浅谈图论中两个重要的通路 篇6
“Euler通路”和“Hamilton回路”是两个意义不同的通路. 一个图具有“Euler通路”是指这个图里存在着这样一条通路,他经过图的每条边一次并且只经过一次; “Hamilton通路”是指它经过图上各顶点一次并且仅仅一次,那么这种通路就叫“Hamilton通路”.
“Hamilton通路”强调图上的“各顶点”一次并且仅仅一次,“Euler通路”强调的是图上“各边”要经过一次并且仅仅一次.“Hamilton通路”并不要求经过图的每条边,“Euler通路”却必然要经过图上的各顶点并且容许重复经过. 需要注意的是: 一个图有“Euler通路”,但不一定有“Hamilton通路”.
一般来讲一个图的“Euler通路”和“Hamilton通路”是不重合的,但在特殊类型的图中它们是重合的,例如: 多边形图. 实际应用当中,判断一个图是否具有“Euler环游”和“Hamilton回路”就显得特别重要,以下内容我们介绍如何判断“Euler环游”和“Hamilton回路”.
关于图的奇顶点个数,还有一个简单常用的定理,也是Euler先发现并证明的,通常认为它是图论中最早出现的一个定理: 对于任意的图G,奇顶点的个数一定是偶数.
现在我们回头来看“七桥问题”,我们把七桥转化为点与边的关系,我们发现图中含有奇点,所以该问题不含有Euler回路,因为图中含有奇点的个数不止两个,所以也没有Euler通路,所以七桥问题的答案是否定的.
一、直接找———( 环游路线)
对于前面所说的世界环游问题,我们采用“直接求解”的方法. 也就是从图的某一个顶点开始,采用一步步试探的方法,来找到图的Hamilton回路. 如果找到了一条,解就得出来了; 如果找不到,就可能没有解.
二、充分条件
定理1有n个顶点的图( n≥2) ,如果它的任意两个顶点度数的和大于或等于n - 1,那么它有一条Hamilton通路.
定理2有n个顶点的图( n≥3) ,如果它有任意两个顶点度数的和大于 或等于n,那么它一 定有一条Hamilton回路.
例: 某厂生产由6种不同颜色的纱织成的双色布,已知花布品种中,每种颜色至少分别和其他3种不同的颜色搭配,要求证明: 可以挑出3种双色布,它们恰好含有6种不同的颜色.
我们现在把它转化为一个图论问题,让每种颜色对应一个顶点,这样就有6个顶点: a、b、c、d、e、f,哪两种颜色搭配织成一种双色布,我们就在这两种颜色对应的顶点之间连一条边,因此在这个图里,一条边代表一种双色布,它们所对应的两条边没有相同的顶点. 要找到含有6种不同颜色的3种双色布,就变成要在图上找到三条彼此没有公共顶点的边,如果图上恰好有一条经过6个顶点各一次的Hamilton通路或回路,那么这样3条彼此没有公共顶点的边总是存在的,在这个图里3条实线边或3条虚线边都满足这个条件.
三、交错标记法
对于一种特殊类型的问题,我们也将采用一种特殊的方法———“交错标记法”来判断它是否有Hamilton通路或回路.
例: 判断是否具有Hamilton通路.
我们的某一个顶点最上面的一个顶点标记上A,然后给和它相邻的各顶点标记上B,依次类推,直到所有的顶点都标记上了A或B为止.
由于16个顶点交错标记了A和B,所以,如果图上存在Hamilton通路的话,它必然要交错地走过顶点A和顶点B,也就是说如果走到了A点的话,下一步无论沿着哪条边走只能走到B点,如果从B点出发,无论怎样走只能走到A点. 在这条Hamilton通路上只能交错地出现顶点A、B、A、B……而不可能连续地出现两个A或两个B. 要想把这16个顶点都走到且不重复,无论怎么安排都至少有两个A挨在一起,但是在图上的任何一条通路都不可能连续经过2个A点的,于是可以看出在图上是不可能存在Hamilton通路的.
在解决这个问题时,我们所采用的就是“交错标记法”:先给图的顶点交错标记上两种不同的符号,再根据在这类图里可能有Hamilton通路所具备的必要条件,就是通路上不能连续地出现同一种符号,来判断这个图是否可能具有Hamilton通路.
摘要：图论是一门应用广泛和内容丰富的数学分支,其应用渗透到各大领域,例如:物理、化学、信息和运筹学等.本文重点介绍“Euler通路”和“Hamilton回路”的联系和区别,以及如何判断“Euler环游”和“Hamilton”回路.
光网络通信中的图论问题 篇7
光网络技术开拓了波分复用 (WDM) 和波长选路 (WR) 两个主要技术。光网络使得网络节点吞吐量和传输容量带来了巨大的飞跃。光网络的能力超过传统网络几个数量级, 通过多种网络为成千上万的用户提供互连服务。
波分复用技术是新一代的超高速的光缆技术, 所谓波分复用, 就是在单一光纤内同步传输多个不同波长的光波, 让数据传输速度和容量获得倍增, 它充分利用单模光纤的低损耗区的巨大带宽资源, 采用合波器, 在发送端将不同规定波长的光载波进行合并, 然后传人单模光纤。在接收部分再由分波器将不同波长的光载波分开的复用方式, 由于不同波长的载波是相互独立的, 所以双向传输问题, 迎刃而解。根据不同的波分复用器 (分波器, 合波器) 可以复用不同数量的波长。空分复用技术 (SDM) 是将单模光纤分割成并行的信道, 使用单一波长传输信息。
所谓全光网, 是指从源节点到目标用户节点之间的数据传输与交换的整个过程均在光域内进行, 即端到端的完全的光路中间没有电信号的介入。
全光网可使通信网具备更强的可管理性、灵活性。它具有如下以往传统通信网和现行的光通信系统所不具备的优点[1]。
(1) 抗干扰能力强。全光网通过波长选择器来实现路由选择, 即以波长来选择路由, 信号的传输全在光域中进行, 信号速率、格式等仅受限于接收端和发射端, 因此全光信息不受任何干扰。
(2) 全光网不仅可以与现有的通信网络兼容, 而且还可以支持未来的宽带综合业务数字网以及网络的升级。
(3) 全光网络具备可扩展性, 即新节点的加入并不会影响原来网络结构和原有各节点设备。网络可同时扩展用户、容量、种类。
(4) 全光网还具备可重构性, 可以根据通信容量的需求, 实现恢复、建立、拆除除光波长连接, 即动态地改变网络结构, 可为突发业务提供临时连接, 从而充分利用网络资源。
(5) 由于全光网比现有的网络多了一个光网络层, 而光网络层中的许多光波器件是无源器件, 因而可靠性高, 而维护费用降低。
在波长选路全光网络中, 单播是由源节点到目标节点的光路实现。光路上任何节点或边仅出现一次, 因而单播选路是很简单的。组播是由源节点到目标节点的光树实现, 该光树是以源节点为根生成所有目标节点的Steiner树。
1 路由和波长分配问题
路由和波长分配问题是全光网研究中的重要问题之一, 简称RWA问题。对于单播连接的RWA问题, 就是在需求矩阵中选择通路和波长的最佳组合, 使得建立的连接数最大, 但没有两个连接在公共边上波长相同, 这已经证明是NP完全的。对于组播连接的RWA问题, 人们在给出不同的假设和模型的基础上, 也展开了大量的研究工作。
设G= (V, E) 是对称有向图表示全光网络, 其中|V|=n。Puv表示节点u到节点v的有向通路。节点u到节点v的最短距离记为d (u, v) 。
需求集合U={ (s, d) |s是源节点, d是目标节点}, 它是单播连接的集合。集合U的路由R是有向通路的集合, 记作R={Puv|u=s, v=d}, 其中 (s, d) ∈U。
定义1: (冲突图) 路由R的冲突图G R= (VR, ER) 的交图。GR的顶点对应着R中的元素, 两个顶点是邻接当且仅当对应的通路至少有一条公共的弧。
二元组 (G, U) 中G= (V, E) 是对称有向图, U是上面所述的单播需求集合。
定义2: (RWA问题) 对 (G, U) 的RWA问题就是寻找U的路由R并分配波长λ给每一 (s, d) ∈U, 使得R中没有两条通路的公共弧有相同的波长。
若将不同的波长用不同的颜色表示, 那么RWA问题就是在冲突图中寻找路由R和顶点着色。
设χ (G, U, R) 是图GR与U, R对应的着色数。χ (G, U) =minRχ (G, U, R) 也就是说, χ (G, U, R) 表示给定的路由R的波长的最少数量。χ (G, U) 表示对所有路由的波长的最少数量。
定义3: (阻塞) 路由R上的弧阻塞是指R上包含该弧的连接的数目。路由R的阻塞是指R上所有弧阻塞的最大值, 记作φ (G, U R) 。网络阻塞是所有路由阻塞的最小值, 记作φ (G, U) =minRφ (G, U, R) 。
在文[2]中, 证明了如下有趣的结果:
(2) 对一般情况下的φ (G, U) , 寻找 (G, U) 是NP完全问题。
下面关于最少波长数量和阻塞的问题仍待解决:
公开问题1:对任一对称有向图是否存在路由R使得χ (G, U, R) =χ (G, U) , φ (G, U, R) φ= (G, U) 。
2 广播图
广播是网络上信息的传播过程。在这个过程中, 一个结点将信息传给所有其它结点。图G中某结点s的广播时间t (s) 是完成以s为源结点的广播所需要的最少单位时间数。图G的广播时间t (G) 是指G中结点广播时间的最大值。
下面结论已经出现在文[3]中:
缩短广播时间的方法是寻找数目尽可能多且弧不公共的生成树。而且这些树的最大深度尽可能小。这就产生了如下问题:
公开问题2:给定有向图G= (V, E) , 找出以给定顶点为根的生成树的最大数目, 并且深度尽可能的小。
文[3]证明了这个问题是NP完全的。
3 结语
本文综述RWA问题及网络广播时间问题, 这些问题最终是转化为图论问题进行研究的。由于问题属于NP完全的, 目前还没有有效算法解决。一些启发式算法将在光网络研究中扮演重要角色。
摘要：本文综述RWA问题及网络广播时间问题, 这些问题最终是转化为图论问题进行研究的.介绍一些理论成果以及尚未解决的公开问题。
关键词：光网络,RWA问题,广播图
参考文献
[1]李颖, 王银莲, 张玉起.浅谈全光网络技术及其发展前景[J].今日科苑, 2007 (14) .
[2]B.Beauquier, J-C.Bermond, L.Gargano, etal.Graph problems arisingfrom wavelength routing in all opticalnetworks[EB/OL].http://hal.ar-chives-ouvertes.fr/docs/.
DNA计算在图论中的应用 篇8
自从Adleman博士于1994年开创性地用DNA计算实现了7个顶点的有向图的哈密尔顿问题以来, 国际上DNA计算在图论应用的研究领域中, 主要集中在对哈密顿图问题、图着色问题和图顶点的最小覆盖问题的求解上。继Adleman之后1998年, Roweis给出一种基于Sticke模型的解决集合最小覆盖问题的方法。2000年, Head等又用基于质粒的DNA计算求解了图的最大团问题。同年, Faulhammer等人对骑士周游问题用DNA计算进行了求解[1]。2004年, Zuwairie Ibrahim等人提出了一种求解最短有向路问题的一种DNA算法。2006年, Aili Han和Daming Zhu提出了解决旅行者问题的一种新的DNA编码方法[2]。
电子计算机在解决图与组合优化中的NP-问题是非常的困难, 特别是规模特别大时几乎是不可能的。DNA计算机将具有以下几个方面的突出优点: (l) 具有高度的并行性, 运算速度快。 (2) DNA作为信息的载体其贮存的容量非常之大。 (3) DNA计算机所消耗能量极小。 (4) DNA分子的资源丰富[3]。这些决定了DNA计算在解决非线性复杂问题、NP完全问题时具有其他计算模式所无法比拟的优势。
2. DNA计算的基本原理
DNA计算的本质就是利用大量不同的核酸分子杂交, 产生类似于某种数学过程的一种组合的结果, 并根据限定条件对其进行筛选的。单链DNA可看作由符号A、C、G、T组成的串, 同电子计算机中编码0和1一样, 可表示成4字母的集合来译码信息。特定的酶可充当“软件”来完成所需的各种信息处理工作[4]。
DNA计算的基本思想是:利用DNA分子的双螺旋结构和碱基互补配对的性质, 将所要处理的问题编码成特定的DNA分子, 在生物酶的作用下, 生成各种数据池;然后利用现代分子生物技术如聚合酶链反应、聚合重叠放大技术、超声波降解、分子纯化、电泳、磁珠分离等手段破获运算结果;最后通过测序或其它方法解读计算结果。DNA计算的核心问题是将经过编码后的DNA链作为输入, 在试管内或其它载体上经过一定时间完成控制的生物化学反应, 以此来完成运算, 使得从反应后的产物中能得到全部的解空间。
3. DNA计算在图论中的应用
3.1 最小生成树问题
文中我们考虑的图是连通赋权简单图。若图是连通的无向图或强连通的有向图, 则从图中任意一个顶点出发遍历图中的所有顶点, 这个过程中经过的边所构成的子图称为原图的生成树。所以最小生成树可描述为:在连通图G的所有生成树中, 代价 (生成树各边权值之和) 最小的生成树称为最小生成树[5]。最小生成树可简记为MST。
下面讨论求解最小生成树问题的算法。根据最小支撑树的定义, 我们可以将最小支撑树的算法简单概括如下:针对图G, 从空树T开始, 往集合T中逐条选择权最小的边 (始终保持边数=顶点数-1) , 直到无法再扩展为止。具体步骤如下:
步骤一:从E中选取一条最小权的边, 记为el=[v1, vZ], E={e1};记n=2, Vn={vl, vZ}。
步骤二:如果n=|G|, 则T= (Vn, En-1) 是最小支撑树;否则执行步骤3。
步骤三:从[Vn, V-Vn]中选一条权最小的边 ([Vn, V-Vn]表示连接顶点Vn, V-Vn的边) 记为en-1=[Vn-1, Vn], Vn+1=Vn∪{vn}, En=En-1∪{en-1}, 把n换成n+1, 转入第2步。
我们来介绍上面提到的算法所对应的分子操作步骤:
步骤一:对图的顶点、边以及边的权进行DNA编码:对于图G的任意顶点vi, 用长度为20的寡聚核苷片断表示 (即它包含20个碱基) , 并记为Ni (i=1, 2, …, n) 。然后利用Ni构造n个探针, 并分别记为Q1, Q2, ……, Qn。对于图G的边eij由三个部分表示:第一部分是寡聚核着酸片断Ni的碱基的补链所构成的寡聚核苷酸片断;第二部分是寡聚核苷酸片断Nj的碱基的补链所构成的寡聚核苷酸片断。第三部分是长度为[30*wij/D+0.5] (wij为边eij的权, D=max{wij}) 的寡聚核苷酸片断;下面通过例子解释编码问题。
根据图1, 可得到, D=max{1, 5, 4, 4, 2, 3, 6, 5, 7}=7。因此根据上面的公式, 可以得到对应于边权w12, w23, w34, w45, w15, w26, w36, w46, w56, 编码的寡聚核苷酸片断的长度分别为:26, 22, 30, 13, 5, 9, 22, 18, 18。由于篇幅所限, 我们这里就只拿e12, e23, 举例。顶点1, 2, 3的编码如下:
N1:TCGGTAATGCTAGCTGGAGA
N2:TATAGGCCATGCGATCGGTA
N3:CGTTAAGCAGTACGAGTCAG
根据编码规则, 得到e12, e23的编码为:
注意:寡聚核普苷片断Nij中带下划线的部分为边的权值长度。
然后将等量边eij (l≤i
步骤二:从试管B中取出部分溶液进行琼脂糖浆凝胶电泳, 跑在最前端的就是最短的DNA链, 该DNA链对应的一定是图G的权最小的边。提取出这些DNA链并用PCI进行扩增和纯化来增加它的纯度。
步骤三:对第二步的产物进行测序并记录这条边。不妨记这条边为e12=v1v2, 同时记V1={v1, v2}。如果V1=V (G) , 则停止;如果V1V (G) , 那么利用探针Q1, Q2将含有顶点v1及含有顶点v2的边e12从试管B中分离出来, 然后再分别利用探针Q1, Q2将含有顶点v1及含有顶点v2分离出来建立新的试管, 仍然记为B, 转入第2步。
按此操作, 最多经过n-1步, 就可以找到图G的最小生成树, 而且在生物操作中, 用电泳代替了权值的比较, 更加适合于寻找比较复杂的图的最小生成树。
3.2 哈密顿路径问题
哈密顿路径又称为哈密顿回路, 是指一个图中, 从图的一个顶点出发, 沿着图中的边 (各顶点连线) , 经过所有顶点且只经过一次, 最终又回到起点, 这条回路就称为哈密顿路径。在一个赋权图中的所有哈密顿路径中, 所经各边权值之和最小的哈密顿路径称为最短哈密顿路径, 也称为最短哈密顿回路[6]。哈密顿路径问题是一个NP-完全问题。本节阐述了利用DNA计算的方法找出无向赋权图中的所有哈密顿路径并找出最短的哈密顿路径的算法。
在1994年Adleman博士用DNA计算首次实现了7个顶点的有向图的哈密尔顿问题。这里采取一种与Adleman博士不同的编码方式。Adleman博士当时采用DNA链的长短的编码方式来代表权值的不同。这种编码方式随着问题规模的增长DNA链的结构也会随之不稳定, 在实际中的可行性也随之降低。文中采用通过链中G, C含量的不同来代表不同的权值。对于权值较高的边使其具有高的GC含量;因为GC配对是形成三个共价键其解链温度大于AT形成的二个共价键的结合。并且与Adleman博士在1994年所做的实验不同的是, 这里解决的是无向图。在算法里将无向边作为两条有向边进行处理。
下面讨论求解无向赋权图中的哈密顿路径问题的算法。哈密顿求解的问题可形式的表示为:给定无向赋权图G= (V, E, W) , V表示图的顶点, E表示图的边, W表示图各边的权值。设图中, |V|=n, 即V (G) ={V0, V1, V2……Vn-1}, 如果存在为V0为起始点以Vn-1为终点的一条包含图p个顶点一次且仅一次的路, 则称这条路为为以V0为起始点以Vn-1为终点的一条Hamilion路。可以将求解无向赋权图中的哈密顿路径问题的算法简单概括如下:随即产生图G的所有路径, 从中找出含有n个顶点的的路径。并从这些路径中找出经过图G所有顶点 (V (G) ={V0, V1, V2……Vn-1}) 且只经过一次的路径。再从中得到权值最小的路径。具体步骤如下:
步骤一:随即产生图G中的所有路径, 记为P。
步骤二:从P中找出含有n个顶点的所有路径, 记为P1。
步骤三:从P1中找出经过所有顶点V (G) ={V0, V1, V2……Vn-1}且只经过一次的所有路径, 这些路径既是图G所有的哈密顿路径, 记为P2。
步骤四:从P2中找到其中权值最小的一条路径, 这条路径既是图G的最短哈密顿路径。
我们来介绍上面提到的算法所对应的分子操作步骤
步骤一:首先对图中所有的顶点V (G) 和所有的边E (G) 进行编码。Vj=Vj’Vj”用20bps的寡居核苷酸表示, 。Vj’代表顶点Vj的前端的10个寡居核苷酸, Vj”代表顶点Vj的前端的10个寡居核苷酸。边eij由顶点Vi的后10个寡居核苷酸Vi”, 权值w和Vj的后10个寡居核苷酸Vj’表示。其中w通过边编码的CG含量不同来代表它的大小, 并根据实际情况选定边编码的长度。
下面通过例子解释编码问题。
根据图2, 用20bps长度的DNA链表示图的边, 并且通过代表各边的DNA链中的CG含量来区分权值的大小。图中有6种不同的权值, 为了在后续试验中比较容易区别出不同的权值, 这里可以领GC含量各相差4。各边的GC含量分别为:0, 4, 8, 12, 16, 20。无向图的边可以看成有向边, 只不过入度和出度不同。由于篇幅所限, 我们这里就只拿e01, e10, e12, 举例。顶点V0, V1, V2编码如下:
注:单下划线表示顶点Vj的前10个寡居核苷酸Vj’, 双下划线表示顶点Vj的前10个寡居核苷酸Vj“。
根据编码规则, 得到e01, e10, e12的编码为:
注:黑色下划线表示边的权值。
按照上面的编码方法生成所有顶点和边的补链, 并加上连接酶和缓冲液加入试管中。使之得到充分的复制。DNA分子大量冗余的特点保证了一定能得到所有可能性的路径。
步骤二:在步骤一得基础上, 利用V1和Vn-1构造探针Q1和Qn-1。并且以这两个探针为引物进行PCR反应。这样试管中以V1为起始点以Vn-1为终点的路径的到大量的复制。
步骤三:对于步骤二生成的产物, 进行凝胶、层析和多次的纯化的到长度在制定区间的分子 (这个区间保证得到所有经过n个顶点的路径) 。
步骤四:利用V1, V2……Vn-1构造探针Q1, Q2……Qn-1。在第三步的基础上, 以Q1, Q2……Qn-1为引物, 用磁珠分离的方式进行过滤。最终剩下的就是图G中的所有哈密顿路径。
步骤五:在步骤四的基础上, 以边权的编码作为引物, 进行PCR扩增。同时对试管溶液进行缓慢的加热。使GC含量较低的路径得到较大几率的扩增, 并进行多次循环的PCR扩增。
步骤六:对步骤五得到的试管溶液进行凝胶电脉得到浓度最高的DNA链。这条DNA链既是图G的最短哈密顿路径。
4. DNA计算在图论中存在的问题
DNA计算在图论应用的领域中还存在一些尚待解决的问题。第一, 图论中权编码的问题, 编码不够合理会直接影响到整个算法的性能。第二, 如何对算法进行设计和优化以降低算法的空间复杂度。第三, 操作的规模和次数问题, 操作规模过于庞大直接影响到算法的精确性和计算时间。
参考文献
[1]韩爱丽.赋权图上优化问题的DNA计算方法研究.中国博士学位论文全文数据库.2008
[2]YuseiTsuboi, Zuwairie Ibrahim.Algorithm of graph isomorphism with three dimensional DNA graph structures.International Journal of Hybrid Intelligent Systems.2005
[3]刘永现.赋权图的DNA计算模型.中国硕士学位论文全文数据库.2008
[4]殷志祥, 张佳秀.图论中的DNA计算模型.系统工程与电子技术.2007
[5]韩世芬.基于DNA计算的遗传算法解决最小生成树问题.鄂州大学学报.2008
[6]崔光照, 张勋才, 王延峰.DNA计算中编码序列的优化设计方案.计算机应用研究.2007
[7]周康, 殷燕芳, 李玉华等.编码的模型分析.华中科技大学学报自然科学版.2007
[8]许进, 强小利, 方刚等.一种图顶点着色DNA计算机模型.科学通报.2006
[9]朱翔鸥, 刘文斌, 孙川.DNA计算编码研究及其算法.电子学报.2006
[10]Satoshi Nakamoto, Kazuhiko.An Error-Resilient Encoding with Fewer DNA Strands for Graph Problems on DNA Computing.Electronics and Communications in Japan.2005
污水管段设计流量的图论解析 篇9
1 图论原理和排水管网有向图
图论是数学理论的一个分支,是研究事物之间关联关系的理论,事物之间的关联关系又称拓扑关系。将图论引入到给水排水管网模型的分析与计算中来,称之为管网图论。图论中的图由顶点和边组成,在管网图中分别称为节点和管段。依照常理,将污水管网中流量和坡度不变的一段管道称为设计管段。当略去管网的构造和水力特征,仅仅考虑节点和管段之间的关联关系时,给水排水管网模型即称为管网图。设计管段即管网图中的管段,管段的两个端点称为节点。所以管网图论是研究节点和管段关联关系的理论,其研究对象是管网模型图。
在城市污水管网系统中,管道中的污水总是从上游管道流向下游管道,管道由小到大,呈现出树枝状结构,整个管网可以抽象为由若干有向树构成的有向图。如同给水管网一样,可应用图论的方法将污水管网表示为由管段和节点构成的管网模型图,如图1。
另外,管网模型假定管段是管线和泵站等简化后的抽象形式,它只能输送水量,而不允许改变水量,即管段上不允许有流量输入或输出,但管段中可以改变水的能量,如具有水头损失,有压力变化等。节点是管线交叉点、端点或大流量出入点的抽象形式,只能传递能量,不能改变水的能量,即节点上水的能量(水头值)是惟一的,但节点可以有流量的输入或输出,如用水的输出、排水的收集或水量调节等[1,2]。
2 污水管网结构分析
污水在管道中总是从上游节点流向下游节点,从上游管道流向下游管道,污水管网图的这种拓扑特性即为树,树梢为管网起端节点(叶节点),树枝代表污水管段,树枝沿途收集本段的污水;各树枝之间由内节点相连,有相同内结点的管段为关联管段,内节点既是其上游关联管段的下游节点,又是其下游关联管段的上游节点。树的方向为污水流向,由叶到枝,再到根,根节点就是污水处理厂,如图2。
3 管段设计流量计算
污水包括居民生活污水、工业废水、工业企业生活与淋浴污水、公共建筑污水等四大类。为了降低污水管道设计计算的难度,假定工业废水、工业企业内职工淋浴生活污水、公共建筑污水均属于集中流量;同时,假定各类污水的最高时流量同时出现,即在最高时状态下这几项流量值可以直接累加。
在管网模型中,管段只能输送水量,不允许改变水量;节点只能传递能量,不允许改变能量;将污水管网系统中管段沿线收集的污水量折算到管段的起端节点。由于污水管段是不含回路的树,比给水管网的环回路相对较简单,—般不必列方程组,而是直接利用质量与能量守恒原理列出一元方程进行计算。所以,污水管段流量的计算要依托节点流量连续性方程,应用图论中节点与管段的拓扑特性,从计算节点流量上寻找突破口。
3.1 节点流量
由图2可知,内节点既是污水转输节点,同时也可能是集中流量的汇入点。按照流量计算原则,每一节点流量包括两部分:(1)集中流量:集中在该节点进入管网的工矿企业及公共建筑排水量;(2)沿线流量:该节点下游关联管段上沿途收集的居民生活污水量。
3.2 管段设计流量
为了简化各元素的相互关系,利用一元方程求解,可用逆推法计算污水管段的流量,即从上游叶节点管段开始,依次向下游进行,直到根节点管段。管段流量计算公式可以从以下两方面来寻求,一方面,从图2上看,在满足管网连续性条件下,对于每一设计管段,管段流量等于该管段上游所有节点的节点流量(包括本段上的上游节点)之和;另一方面,从管网系统中各管段的功能来看,管段流量又包括两个部分:上游转输流量和本段沿线生活污水量。
管段流量可以定义为集中流量和生活污水量两个部分之和。其中集中流量是上游管段中从工业企业或其它大型公共建筑流入的污水量,可以独立地用最高时流量进行统计计算。对于居民生活污水量,为了保证连续性条件,在节点流量分配时只能按生活污水的平均日流量进行分配,再求出每条管段的最高时生活污水量(以便于和集中流量进行加和统计进而求解管段设计流量),因此,应先计算每条管段的平均日生活污水量总和(本段流量+转输流量),同时依托所求各条管段的平均日生活污水量总和,确定各管段的居民生活污水总变化系数Kz,再求解最高时管段居民生活污水量。
综上所述,可以得到任意一条污水管的设计流量(L/s)的计算公式:Q=q1+Kzq2
式中q1为上游管段(包括本段上的上游节点)中全部集中流量之和;q2为上游管段及本段所承担的平均日生活污水量总和;Kz为各管段的污水总变化系数。
4 结束语
文献[1]中将管段流量定义为三部分,本段流量、转输流量和集中流量,但没有明确指出前两项是平均日生活污水量,从管网系统中各管段的使用功能来看,转输流量可能包含集中流量和上游的生活污水量;文献[2]中定义管段流量公式时将q2定义为各管段输送的居民生活污水平均日流量,没有明确指出此流量数值与所求计算管段的关联关系。
引入图论的关联关系来求解污水管段流量,可以充分体现出给水管道和排水管道在计算原理上的统一,系统地明确了公式中各个物理量的界限,使计算思路更加明朗化,便于理解记忆。
参考文献
[1]孙慧修.排水工程上册(第四版)[M].北京:中国建筑工业出版社,1999.