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

重庆邮电学院研究生堂下考试答卷

2011-2012学年第1学期

考试科目 图论及其算法

姓 名 王金拓

年 级 2011级

学 号 S110101143

专 业 通信与信息系统

2011年12 月 12日

图论及其应用

姓名：王金拓

学号：S110101143

摘要：在现实生活中，存在着许许多多的问题都用到了图论的知识去解决。随着科技的进步，对于一些过去较为难处理的事情也变得容易。树的遍历搜索也得到了较为广泛的应用。 关键字：图论、树的遍历、实际问题

Abstract:In the morden society,so many questions need to be dealed with by Graph Theory.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年代，当时出现一个非常有趣的问题引起了欧洲数学家的浓厚兴趣，这个问题要求遍历普鲁士的哥尼斯堡七桥中的每一座桥恰好一次后回到出发点。也就是所说的，著名的七桥问题。欧拉也证明了这是一个不可能完成的问题。随后，欧拉在报纸上发表了著名的论文——《依据几何位置的解题方法》，这是图论领域当中的真真正正的第一篇论文，它是标志着图论的诞生的重要拐点。实际上，图论的真正发展始于20世纪五六十年代之间，是一门既年代古老而又年轻的学科项目。图论中有着趣味性。但是，严格的来讲它是组合数学当中的一个较为重要分支。图论看起来只有研究点和线的学问，但是，实际中，其应用领域非常的广阔，不仅仅是局限在数学和计算机的学科之中。其中还包括了社会学、交通中管理应用、电信同信领域等等。总之，图论这门学科具有下面几个特点：

①图论中蕴含了非常丰富的想法、漂亮的图形以及巧妙的证明； ②涉及的问题多且广泛，问题外表简单朴素,本质上却十分复杂深刻； ③解决实际问题的方法丰富多彩，非常灵活,经常是有着一种问题一种解法。

从上面三个特点就能够看出来，图论与其它的数学分支不同。此学科即不像群论、拓扑等等学科那样有着一套较为完整的理论体系和有着解决问题的较为系统方法。而且图论所研究的内容非常广泛。例如，图当中的连通性、遍历性、图中的着色以及图的极值问题，还有图的可平面性等等性质。

二、图论的相关理论及其应用

1 相关知识背景：

伴随着大学中教学的逐步体制改革，越来越多的大学中实行的是学分制。由于在学分制度，学生需要选修定量的课，达到修完规定的学分的目标，即可毕业了。在此中的有一部分课程是必修课，以此来培养专业素质的根基。在必修课程中，还分为基础课，和专业课。在基础课的学习中，独立于其他课程，一定得先修这些课程；而另一些是专业课的学习课程，必须在学完作为它的基础的先修课程而后，进行学习。这些必要条件决定了课程之间的先者与后者的关系。所以，每一个专业的学生们在选必修课程时，一定要考虑到课程之间的先者与后者关

系。这个研究选课问题具有着极其重要的现实意义。所以，我选择了这个题目进行讨论。

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的入度。

有向图 无向图

图1

定义：设G=(V，E)是有限有向简单图，若存在顶点集V上的一种标顺序，得到一个顶点序列{v1,v2,…vi,…vj,…vn},使得对于任意的j> i，顶点vj一定不是顶点vi的先驱，则称该顶点序列为拓扑有序序列。