图论的应用计算机技术与科学毕业论文
学 生 毕 业 设 计(论 文)
课题名称图 论 的 应 用姓 名学 号0609302-18院 系数学与计算科学系专 业信息与计算科学指导教师
5 月5日
目录
摘要.....................................................1
关键词...................................................1
Abstract.................................................1
Key words................................................1
引言.....................................................2
1.图论的发展 .............................................. 3
2. 图论的基本理论知识 ......................................4
2.1 拓扑序列.............................................4
2.2 欧拉回路.............................................4
2.3 最大流 .............................................5
3. 运用图论对实际生活中的具体问题进行分析...................5
3.1 图论在高校选课中的应用...............................5
3.2 图论在单词接龙中的应用...............................6
3.3 图论在邮政中的应用...................................7
4. 总结 ..................................................9
参考文献.................................................9
致谢.....................................................10
图论的应用
摘要:
图论从诞生至今已有200多年的历史,但很多问题一直没有很好地解决。随着计算机科学的发展,图论又重新成为了人们研究讨论的热点。图形是一种描述和解决问题直观有效的手段,这里给出图论在现实生活中的一些应用。
关键字:图论;拓扑有序序列;欧拉;最大流;
On Graph Theory and Its Application
Liu Xiao-yi
Abstract:
From the birth of graph theory has been 200 years of history, but has not been a good lot of problems to solve. With the development of computer science, graph theory has again become a hot topic that people study. Graph is a visual description and effective means to solve the problem, here is given graph theory in real life some of the application.
Key words:Graph Theory;Ordered sequence of topological ;Euler; Maximum flow;
X人,用集合中的结点来代表工作。用边来代表图Y中结点之间的关系,在这里结点之间的关系是“人能否胜任工作”因此 若某人能胜任工点作,那么就在两个结点之间加上一条边。由于销售需要2人,所以用2个结S1和S2表示。如此得到二分图(I)给出了最大匹配,很容易看出每一项工作都有人来负责。
再例如一个部门中有25人,由于纠纷而使得关系十分紧张,是否可便每个人与5个人相处融洽?则可以建立一个图的模型,最基本的问题是如何描述它—什么是结点,什么是边?在本问题中,没有太多的选择,只有人和纠纷。我们可试着用结点来代表人。用边来代表图中结