图论报告(可以直接交作业)

1、精选优质文档-倾情为你奉上重庆邮电学院研究生堂下考试答卷 2011-2012学年第1学期考试科目 图论及其算法 姓 名 王金拓 年 级 2011级 学 号 S 专 业 通信与信息系统 2011年12 月 12日图论及其应用 姓名：王金拓 学号：S摘要：在现实生活中，存在着许许多多的问题都用到了图论的知识去解决。随着科技的进步，对于一些过去较为难处理的事情也变得容易。树的遍历搜索也得到了较为广泛的应用。关键字：图论、树的遍历、实际问题Abstract:In the morden society,so many questions need to be dealed with by Graph T

2、heory.With the technology more and more advanced, the more intractable in the past for many things is easier. Traversal of the search tree has also been more widely used.Key word: Graph Theory. Traversal of the search tree.fact question一、引言图论的起源是在18世纪30年代，当时出现一个非常有趣的问题引起了欧洲数学家的浓厚兴趣，这个问题要求遍历普鲁士的哥尼斯堡七

3、桥中的每一座桥恰好一次后回到出发点。也就是所说的，著名的七桥问题。欧拉也证明了这是一个不可能完成的问题。随后，欧拉在报纸上发表了著名的论文依据几何位置的解题方法，这是图论领域当中的真真正正的第一篇论文，它是标志着图论的诞生的重要拐点。实际上，图论的真正发展始于20世纪五六十年代之间，是一门既年代古老而又年轻的学科项目。图论中有着趣味性。但是，严格的来讲它是组合数学当中的一个较为重要分支。图论看起来只有研究点和线的学问，但是，实际中，其应用领域非常的广阔，不仅仅是局限在数学和计算机的学科之中。其中还包括了社会学、交通中管理应用、电信同信领域等等。总之，图论这门学科具有下面几个特点：图论中蕴含了非

4、常丰富的想法、漂亮的图形以及巧妙的证明；涉及的问题多且广泛，问题外表简单朴素,本质上却十分复杂深刻；解决实际问题的方法丰富多彩，非常灵活,经常是有着一种问题一种解法。从上面三个特点就能够看出来，图论与其它的数学分支不同。此学科即不像群论、拓扑等等学科那样有着一套较为完整的理论体系和有着解决问题的较为系统方法。而且图论所研究的内容非常广泛。例如，图当中的连通性、遍历性、图中的着色以及图的极值问题，还有图的可平面性等等性质。二、图论的相关理论及其应用1 相关知识背景：伴随着大学中教学的逐步体制改革，越来越多的大学中实行的是学分制。由于在学分制度，学生需要选修定量的课，达到修完规定的学分的目标，即可

5、毕业了。在此中的有一部分课程是必修课，以此来培养专业素质的根基。在必修课程中，还分为基础课，和专业课。在基础课的学习中，独立于其他课程，一定得先修这些课程；而另一些是专业课的学习课程，必须在学完作为它的基础的先修课程而后，进行学习。这些必要条件决定了课程之间的先者与后者的关系。所以，每一个专业的学生们在选必修课程时，一定要考虑到课程之间的先者与后者关系。这个研究选课问题具有着极其重要的现实意义。所以，我选择了这个题目进行讨论。2 图论相关知识：设G =(V，E)为简单有向图。其中，V是顶点的有穷非空集合，而E是所有有向边的集合。在上述关系中，若< Vi，Vj>E,则< Vi，

6、Vj>表示从顶点Vi到顶点Vj的一条有向边， 且称Vi是有向边< Vi，Vj>的初始端点， Vj是有向边< Vi，Vj>的终结端点。而且，称Vi是Vj的先驱，Vj则是Vi的后继。顶点Vi的度是和Vi相关的边的数目之和；以顶点Vi为初始点的有向边的数目总和，称为Vi的出度；以顶点Vi做为终结端点的有向边的数目总和，称为Vi的入度。有向图无向图 图1定义：设G=(V，E)是有限有向简单图，若存在顶点集V上的一种标顺序，得到一个顶点序列v1,v2,vi,vj,vn,使得对于任意的j> i，顶点vj一定不是顶点vi的先驱，则称该顶点序列为拓扑有序序列。V1V2V3V

7、4V5图2如上图所示，此定点序列V1,V2,V3,V4,V5就为图1的拓扑有序序列定理1：有限有向图G存在拓扑有序序列的必要条件是G中至少存在一个顶点，其入度为0.。定理2：有限有向图G存在拓扑有序序列当且仅当G中无回路。有回路无回路 图3推论：G是有向树或森林当且仅当有向图G存在拓扑有序序列。3 模型建立：课程与课程之间先者与后者的关系的抽象，我们要利用图论中有向无回路图的相关知识，其中的拓扑序列与树的深度优先搜索与广度优先搜索有着一定的相似性。把课程与课程之间先者与后者关系转化成为有向无回路图中的有向边。这样就可以解决了问题。其构造有向无回路图的方法是：图中的顶点表示课程,有向边表示课程之

8、间的先者与后者关系；若课程x是课程y的先决条件，则图中出现从顶点x到顶点y的有向边<x，y>.选课问题的抽象借助有向无回路图，我们可把选课问题抽象为在有向无回路图中寻找拓扑有序序列。实行学分制的各个院系，在按排教学计划时，必须考虑到课程之间的领先关系，首先把该专业必修课程之间的依靠关系抽象为有向无回路图，然后从有向无回路图中找到多个拓扑有序序列。通过把课程之间领先关系转化为有向无回路图，进而把选课问题转化为在有向无回路图中寻找拓扑有序序列问题，从而成功地解决了高校学生的选课问题。三、总结经过在重庆邮电大学有关图论这门课程的一学期的学习中，已经对图论的相关知识有了一定的了解与掌握。从图论这本教材的第一章的图论的基本概念中，路和连通图的概念贯穿了正本书。而二分图和关于图的矩阵的表示也为后面的一些算法做了重要的铺垫。欧拉图和哈密顿图的概念与其算法的时间复杂性在实际中也有着重要的应用。其中的最短路径问题涉及到了旅行推销员问题和中国投递员这个话题。本文应用到了有关树的概念和一些性质。其中的拓扑序列与树的深度优先搜索与广度优先搜索有着一定的相似性。这些领域包括计算机科图论的应用十分广泛，如果我们在学习的过程中能打下坚实的基础，就有能力将图论的思想应用到纷乱复杂的现实问题中去。在通过图论的相关知识解决实际问题可以节约时间，资源，路程等等。四、参考文献