没有合适的资源?快使用搜索试试~ 我知道了~
首页图论算法理论、实现及应用 高清带书签pdf
本书系统地介绍了图论算法理论,并选取经典的ACM/ICPC竞赛题目为例题阐述图论算法思想,侧重于图论算法的程序实现及应用。本书第1章介绍图论基本概念和图的两种存储表示方法:邻接矩阵和邻接表,第2~9章分别讨论图的遍历与活动网络,树与生成树问题,最短路径问题,可行遍性问题,网络流问题,点支配集、点覆盖集、点独立集、边覆盖集、边独立集(匹配),图的连通性问题,平面图与图的着色问题等。本书可 以作为高等院校计算机(或相关专业)图论等相关课程的主教材,也可作为ACM/ICPC竞赛的辅导教材。 基本信息 书 名:图论算法理论、实现及应用 著作责任者:王桂平 王 衍 任嘉辰 标准书号:ISBN 978-7-301-17578-1/TP·1122 出 版 者:北京大学出版社 定 价:54.00元
资源详情
资源评论
资源推荐
图论算法理论、实现及应用
王桂平、王 衍、任嘉辰 编著
内容提要
本书系统地介绍了图论算法理论,并选取经典的 ACM/ICPC 竞赛题目为例题阐述图论算法思
想,侧重于图论算法的程序实现及应用。本书第 1 章介绍图论基本概念和图的两种存储表示方法:
邻接矩阵和邻接表,第 2~9 章分别讨论图的遍历与活动网络,树与生成树问题,最短路径问题,
可行遍性问题,网络流问题,点支配集、点覆盖集、点独立集、边覆盖集、边独立集(匹配),图
的连通性问题,平面图与图的着色问题等等。本书可以作为高等院校计算机(或相关专业)图论
等相关课程的主教材,也可作为 ACM/ICPC 竞赛的辅导教材。
i
前 言
一、图论研究及图论教学
①
图论(Graph Theory)是数学的一个分支,它以图为研究对象。图论中的图是由若干个给定的
顶点、及若干条连接两个顶点的边所构成的图形,这种图形通常用来描述某些事物之间的某种特
定关系,用顶点代表事物,用连接两个顶点的边表示相应两个事物间具有这种关系。这种图提供
了一个很自然的数据结构,可以对自然科学和社会科学中许多领域的问题进行恰当的描述或建模,
因此图论研究越来越得到这些领域的专家和学者的重视。
图论最早的研究源于瑞士数学家莱昂哈德·欧拉(Leonhard Euler, 1707~1783),他在 1736
年成功地解决了哥尼斯堡(Königsberg)七桥问题,从而开创了图论的研究。
哥尼斯堡七桥问题。东普鲁士哥尼斯堡市(今俄罗斯加里宁格勒)有一条布格(Pregel)河,
如图 1(a)所示。布格河横贯哥尼斯堡城区,它有两条支流,在这两条支流之间夹着一块岛形地带,
这里是城市的繁华地区。全城分为北、东、南、岛四个区,各区之间共有七座桥梁联系着。
人们长期生活在河畔、岛上,来往于七桥之间。有人提出这样一个问题:能不能一次走遍所
有的七座桥,而每座桥只准经过一次?问题提出后,很多人对此很感兴趣,纷纷进行试验,但在
相当长的时间里,始终未能解决。
图 1 七桥问题
欧拉在 1736 年解决了这个问题,他将这个问题抽象为一个图论问题:把每一块陆地用一个顶
点来代替,将每一座桥用连接相应两个顶点的一条边来代替,从而得到一个图(如图 1(b)所示)。
欧拉证明了这个问题没有解(详见本书 5.1 节),并且推广了这个问题,给出了“对于一个给定的
图,能否用某种方式走遍所有的边、且没有重复”的判定法则。这项工作使欧拉成为图论及拓扑
学的创始人。
在此后的两百多年时间里,图论的研究从萌芽阶段,逐渐发展成为数学的一个新分支。特别
是从 20 世纪初期开始,在生产管理、交通运输、计算机和通讯网络等方面涌现了许多离散性问题,
这极大地促进了图论的发展。20 世纪 70 年代以后,由于高性能计算机的出现,使大规模的图论
问题的求解成为可能。现在,图论理论广泛应用在运筹学、计算机科学、电子学、信息论、控制
论、网络理论、经济管理等领域。
由于图论的重要性,越来越多的大学将图论单独作为一门课程来开设,把它作为数学、计算
①
本文中关于图论课程教学改革的一些思想,已经发表在《计算机教育》2009 年第 20 期上,论文题目为《计算机专业
图论课程教学改革探索》,即参考文献[20](获得《计算机教育》杂志社举办的“英特尔杯”2009 年全国计算机教育优
秀论文评比二等奖)。
图论算法理论、实现及应用
- ii -
机科学、电子学、管理学等专业本科生和研究生的必修课或选修课。很多其他课程的内容也都涉
及到图论知识,如离散数学、运筹学、拓扑学等。介绍图论理论的教材逐渐增多,其中也不乏优
秀的教材,如文献[1]~[7]。这些课程和教材或者是侧重于完整的图论知识体系介绍、以及复杂的
图论定理的数学证明,或者是侧重于从应用数学的角度研究图论在各领域的应用。
另外,为了实现用计算机程序求解各种应用问题,计算机科学家抽象出许多数据结构,如栈、
队列、堆、树及二叉树、图等,其中图是最重要的数据结构之一,也是应用得最广的数据结构之
一。数据结构课程是专门研究这些数据结构的描述、实现及应用的课程。数据结构课程讲到图论
部分时,侧重于图结构的描述、图结构的存储、少量基本的图论算法的实现等等。
许多学生(特别是计算机专业的学生)在学习图论时,都不满足于图论算法的手工和草稿纸
演算,迫切地想知道如何用程序实现图论中的算法,以及如何将这些算法思想用来求解实际问题。
据作者调查统计
①
,市面上侧重于用程序实现图论算法、并通过例题阐述图论算法思想及其应用
的教材少之又少。本教材希望能弥补这一缺憾。所以本书立足于图论算法理论和思想的描述及程
序实现,并以大量的ACM/ICPC竞赛题目来阐述图论算法思想在求解这些题目中的应用。接下来
简要地介绍ACM/ICPC程序设计竞赛。
二、ACM/ICPC 程序设计竞赛
1. ACM/ICPC
ACM/ICPC(ACM International Collegiate Programming Contest,国际大学生程序设计竞赛)
是由美国计算机协会 ACM(Association for Computing Machinery)主办的,世界上公认的规模最
大、水平最高的国际大学生程序设计竞赛,其目的旨在使大学生运用计算机来充分展示自己分析
问题和解决问题的能力。该项竞赛从 1977 年第一次举办世界总决赛以来,至今已连续举办 30 多
届了。该项竞赛一直受到国际各知名大学的重视,并受到全世界各著名计算机公司的高度关注。
ACM/ICPC 竞赛分区域预赛和总决赛两个阶段进行,各预赛区第一名自动获得参加世界总决
赛的资格。世界总决赛安排在每年的 3~4 月举行,而区域预赛安排在上一年的 9~12 月在各大洲
举行。
ACM/ICPC 竞赛以组队方式进行比赛,每支队伍由不超过 3 名队员组成,比赛时每支队伍只
能使用一台计算机。在 5 个小时的比赛时间里,参赛队伍要解答 6~10 道指定的题目。排名时,首
先根据解题数目来排名,如果多支队伍解题数量相同,则根据队伍的总用时进行排名(用时越少,
排名越靠前)。每支队伍的总用时为每道解答正确的题目的用时总和。每道解答正确的题目的用时
为从比赛开始计时到该题目解答被判定为正确的时间,其间每一次错误的提交运行将被加罚 20 分
钟时间。最终未正确解答的题目不记入总时间,其提交也不加罚时间。
ACM/ICPC 竞赛在公平竞争的前提下,提供了一个让大学生充分展示用计算机解决问题的能
力与才华的平台。ACM/ICPC 竞赛鼓励创造性和团队协作精神,鼓励在编写程序时的开拓与创新,
它考验参赛选手在承受相当大的压力下所表现出来的非凡能力。竞赛所触发的大学生的竞争意识
为加速培养计算机人才提供了最好的动力。竞赛中对解决问题的苛刻要求和标准使得大学生对解
决问题的深度和广度展开最大程度的追求,也为计算机科学的研究和发展作了一个最好的导向。
2. 在线评判网站
随着 ACM/ICPC 程序设计竞赛的推广,各种程序在线评判(Online Judge,简写为 OJ)网站
也应运而生,这为程序设计爱好者提供了一种新的程序实践方法:在线程序实践。
①
作者对互动出版网站(www.china-pub.com)和卓越亚马逊网站(www.amazon.cn)上列出的全部图论相关书目及目
录进行了仔细的分析,从而得出的结论。
前言
- iii -
在线程序实践是指由 OJ 网站提供题目,用户在线提交程序,OJ 网站的在线评判系统实时评
判并反馈评判结果。这些题目一般具有较强的趣味性和挑战性,评判过程和结果也公正及时,因
此能引起用户的极大兴趣。
用户在解题时编写的解答程序通过网页提交给在线评判系统称为提交运行,每一次提交运行
会被判为正确或者错误,判决结果会及时显示在网页上。
用户从评判系统收到的反馈信息包括:
"Accepted" — 程序通过评判!
"Compile Error" — 程序编译出错。
"Time Limit Exceeded" — 程序运行超过该题的时间上限还没有得到输出结果。
"Memory Limit Exceeded" — 内存使用量超过题目里规定的上限。
"Output Limit Exceeded" — 输出数据量过大(可能是因为陷入死循环了)。
"Presentation Error" — 输出格式不对,可检查空格、空行等等细节。
"Run Time Error" — 程序运行过程中出现非正常中断,如数组越界等。
"Wrong Answer" — 用户程序的输出错误。
等等。
用户可以根据 OJ 系统反馈回来的评判结果反复修改程序,直到最终收获 Accept(程序正确)。
这个过程不仅能培养用户独立分析问题、解决问题的能力,而且每成功解决一道题目都能给用户
带来极大的成就感。
三、本书安排
本书共分 9 章,每章内容安排如下:
第 1 章介绍图论的一些基本概念,以及图的两种重要存储表示方法:邻接矩阵和邻接表,并
初步讨论了存储方式对图论算法复杂度的影响。
第 2 章讨论了图的遍历,遍历是很多图论算法的基础。本章介绍了两种重要的遍历方法:深
度优先搜索和广度优先搜索,并对这两种遍历算法的思想、程序实现、算法复杂度作了详细的分
析和讨论。本章还讨论了活动网络,包括 AOV 网络与拓扑排序问题、AOE 网络和关键路径问题。
第 3 章讨论树与生成树问题,主要介绍求无向连通图最小生成树的三个算法:克鲁斯卡尔
(Kruskal)算法、Boruvka 算法和普里姆(Prim)算法,并对这三个算法的思想、程序实现、算
法复杂度作了详细的分析和讨论。另外,本章还讨论了判断生成树是否唯一的方法。
第 4 章讨论了有向网(或无向网)中一个典型的问题:最短路径问题。本章介绍了求解最短
路径问题的 4 个算法:Dijkstra 算法、Bellman-Ford 算法、SPFA 算法和 Floyd 算法,这 4 个算法分
别适用于有向网(或无向网)中各边权值的取值的不同情形及问题求解的不同需要。本章着重对
这 4 个算法的思想、递推过程、算法复杂度作了详细的讨论,并对这 4 个算法作了详细的对比分
析。本章还介绍了求最短路径的算法思想在求解差分约束系统中的应用。
第 5 章讨论了可行遍性问题,包括欧拉回路、汉密尔顿回路以及中国邮递员问题。前两个概
念容易混淆,欧拉回路要求经过每条边一次且仅一次并回到出发点,而汉密尔顿回路要求经过每
个顶点一次且仅一次并回到出发点。本章介绍这相关概念及定理,并讨论这两种回路及中国邮递
员问题的求解方法和应用。
第 6 章讨论了网络流问题。许多系统包含了流量问题,例如,公路系统中有车辆流,控制系
统中有信息流,供水系统中有水流,金融系统中有现金流等等。从问题求解的需求出发,网络流
问题可以分为:网络最大流,流量有上下界的网络的最大流和最小流,最小费用最大流,流量有
剩余481页未读,继续阅读
shuangde800
- 粉丝: 1040
- 资源: 14
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- RTL8188FU-Linux-v5.7.4.2-36687.20200602.tar(20765).gz
- c++校园超市商品信息管理系统课程设计说明书(含源代码) (2).pdf
- 建筑供配电系统相关课件.pptx
- 企业管理规章制度及管理模式.doc
- vb打开摄像头.doc
- 云计算-可信计算中认证协议改进方案.pdf
- [详细完整版]单片机编程4.ppt
- c语言常用算法.pdf
- c++经典程序代码大全.pdf
- 单片机数字时钟资料.doc
- 11项目管理前沿1.0.pptx
- 基于ssm的“魅力”繁峙宣传网站的设计与实现论文.doc
- 智慧交通综合解决方案.pptx
- 建筑防潮设计-PowerPointPresentati.pptx
- SPC统计过程控制程序.pptx
- SPC统计方法基础知识.pptx
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功
评论30