图论算法理论、实现及应用

《图论算法理论、实现及应用》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、图论算法理论、实现及应用王桂平、王衍、任嘉辰编著内容提要本书系统地介绍了图论算法理论，并选取经典的ACM/ICPC竞赛题目为例题阐述图论算法思想，侧重于图论算法的程序实现及应用。本书第1章介绍图论基本概念和图的两种存储表示方法：邻接矩阵和邻接表，第2～9章分别讨论图的遍历与活动网络，树与生成树问题，最短路径问题，可行遍性问题，网络流问题，点支配集、点覆盖集、点独立集、边覆盖集、边独立集（匹配），图的连通性问题，平面图与图的着色问题等等。本书可以作为高等院校计算机（或相关专业）图论等相关课程的主教材，也可作为ACM/ICPC竞赛的辅导教材。前言①一、图论研究及图论教学图

2、论（GraphTheory）是数学的一个分支，它以图为研究对象。图论中的图是由若干个给定的顶点、及若干条连接两个顶点的边所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用顶点代表事物，用连接两个顶点的边表示相应两个事物间具有这种关系。这种图提供了一个很自然的数据结构，可以对自然科学和社会科学中许多领域的问题进行恰当的描述或建模，因此图论研究越来越得到这些领域的专家和学者的重视。图论最早的研究源于瑞士数学家莱昂哈德·欧拉（LeonhardEuler,1707～1783），他在1736年成功地解决了哥尼斯堡（Königsberg）七桥问题，从而开创了图论的研

3、究。哥尼斯堡七桥问题。东普鲁士哥尼斯堡市（今俄罗斯加里宁格勒）有一条布格（Pregel）河，如图1(a)所示。布格河横贯哥尼斯堡城区，它有两条支流，在这两条支流之间夹着一块岛形地带，这里是城市的繁华地区。全城分为北、东、南、岛四个区，各区之间共有七座桥梁联系着。人们长期生活在河畔、岛上，来往于七桥之间。有人提出这样一个问题：能不能一次走遍所有的七座桥，而每座桥只准经过一次？问题提出后，很多人对此很感兴趣，纷纷进行试验，但在相当长的时间里，始终未能解决。图1七桥问题欧拉在1736年解决了这个问题，他将这个问题抽象为一个图论问题：把每一块陆地用一个顶点来代替，将每一座桥用

4、连接相应两个顶点的一条边来代替，从而得到一个图（如图1(b)所示）。欧拉证明了这个问题没有解（详见本书5.1节），并且推广了这个问题，给出了“对于一个给定的图，能否用某种方式走遍所有的边、且没有重复”的判定法则。这项工作使欧拉成为图论及拓扑学的创始人。在此后的两百多年时间里，图论的研究从萌芽阶段，逐渐发展成为数学的一个新分支。特别是从20世纪初期开始，在生产管理、交通运输、计算机和通讯网络等方面涌现了许多离散性问题，这极大地促进了图论的发展。20世纪70年代以后，由于高性能计算机的出现，使大规模的图论问题的求解成为可能。现在，图论理论广泛应用在运筹学、计算机科学、电子

5、学、信息论、控制论、网络理论、经济管理等领域。由于图论的重要性，越来越多的大学将图论单独作为一门课程来开设，把它作为数学、计算①本文中关于图论课程教学改革的一些思想，已经发表在《计算机教育》2009年第20期上，论文题目为《计算机专业图论课程教学改革探索》，即参考文献[20](获得《计算机教育》杂志社举办的“英特尔杯”2009年全国计算机教育优秀论文评比二等奖)。i图论算法理论、实现及应用机科学、电子学、管理学等专业本科生和研究生的必修课或选修课。很多其他课程的内容也都涉及到图论知识，如离散数学、运筹学、拓扑学等。介绍图论理论的教材逐渐增多，其中也不乏优秀的教材，如文

6、献[1]～[7]。这些课程和教材或者是侧重于完整的图论知识体系介绍、以及复杂的图论定理的数学证明，或者是侧重于从应用数学的角度研究图论在各领域的应用。另外，为了实现用计算机程序求解各种应用问题，计算机科学家抽象出许多数据结构，如栈、队列、堆、树及二叉树、图等，其中图是最重要的数据结构之一，也是应用得最广的数据结构之一。数据结构课程是专门研究这些数据结构的描述、实现及应用的课程。数据结构课程讲到图论部分时，侧重于图结构的描述、图结构的存储、少量基本的图论算法的实现等等。许多学生（特别是计算机专业的学生）在学习图论时，都不满足于图论算法的手工和草稿纸演算，迫切地想知道如何

7、用程序实现图论中的算法，以及如何将这些算法思想用来求解实际问题。①据作者调查统计，市面上侧重于用程序实现图论算法、并通过例题阐述图论算法思想及其应用的教材少之又少。本教材希望能弥补这一缺憾。所以本书立足于图论算法理论和思想的描述及程序实现，并以大量的ACM/ICPC竞赛题目来阐述图论算法思想在求解这些题目中的应用。接下来简要地介绍ACM/ICPC程序设计竞赛。二、ACM/ICPC程序设计竞赛1.ACM/ICPCACM/ICPC（ACMInternationalCollegiateProgrammingContest，国际大学生程序设计竞赛）是由美国计