图论与网络最优化算法

出版时间：2009-10  出版社：重庆大学出版社  作者：龚劬 编  页数：215  
Tag标签：无  

前言

　　图论与网络最优化算法是一门提供离散数学模型的应用数学学科。随着计算机在社会中作用的变大，其应用日益广泛，应用遍及系统工程、电工学、交通运输、城市规划、生产管理、经济、通信、计算机等各个领域，人工智能、模式识别、计算机操作系统、数据结构等都涉及图论。　　本教材的学习主要有以下4个方面的作用：　　1.思维的体操。其中含有广泛的数学思想和数学方法，诸如优化、分类、数形结合、转化的思想、分解的思想、归纳、演绎和逆推等。这是其他工科数学所无法比拟的，对培养我们的数学机敏性与成熟性大有益处。　　2.算法设计者的翅膀。图论算法是算法设计与分析中的重要组成部分，其中包含常用的算法设计基本方法，如搜索技术、分支定界法、回溯法、贪婪法及各种启发式算法，算法的时间复杂性分析，近似算法的近似程度分析也融入其中。　　3.综合应用能力形成的催化剂。书中几乎每章末都有关于图论理论和算法在实际中的各种应用，也含有一些具有一定灵活性和创造性的应用案例，配有大量颇具启发性和趣味性的习题。图论与代数、运筹学密切相关，概率统计与网络交叉有活动网络，这些都有助于我们综合运用数学能力的提高。图论中的图具有最复杂的非线性数据结构，如果将其中的算法编程实现，编程能力可上一个新的台阶。　　4.描述和解决离散问题的有利工具。在工农业生产、交通运输、通信和电力领域经常能看到许多网络，如河道网、灌溉网、管道网、公路网、铁路网、电话线网、计算机通信网及输电线网等。还有许多看不见的网络，各种关系网，如状态转移关系、事物的相互冲突关系、工序的时间先后次序关系等，这些网络都可归结为图论的研究对象——图。其中存在大量问题，如生产计划、投资计划和设备更新等问题也可以转化为网络优化的问题，这些都可借助于图论这个工具来加以解决。

内容概要

本书共分9章：图与网络的基本概念、树及其算法、连通性、路径算法、匹配、行遍性问题、平面图、图的着色及网络流问题。其中包含较丰富的实际应用案例与算例，每章末均附有较多难易程度不同的习题，另外还附有少量涉及网络建模与计算的大型综合应用题。    本书是一本理论与应用相结合的基础教材，可作为高等工科院校系统工程、管理工程、自动控制、通信与计算机科学、城市规划等专业高年级本科生或研究生的教材和教学参考书，也可供有关专业的科研人员自学。

书籍目录

第一章  图与网络的基本概念  §1  绪论  §2  一些基本概念  §3  图的矩阵表示  §4  图在计算机中的存储  §5  计算复杂性与算法  习题1第二章  树  §1  路径与连通  §2  有向图的连通  §3  图的搜索  §4  树及其性质  §5  生成树算法  §6  有向树  习题2第三章  连通性  §1  连通度  §2  割边、割集、割点  §3  块与块划分  §4  可靠网络的设计  习题3第四章  路径算法  §1  最短路径问题  §2  最短路径问题的一些扩展  §3  最优路径  §4  关键路径  §5  最短路径算法的应用  习题4第五章  匹配  §1  匹配的概念  §2  匹配基本定理  §3  二部图的最大基数匹配  §4  二部图的最大权匹配  §5  一般图的最大权匹配  §6  一般图的最大权匹配  §7  匹配的应用  习题5第六章  行遍性问题  §1  欧拉图  §2  中国邮递员问题  §3  有向欧拉图  §4  中国邮递员问题的应用与推广  §5  哈米尔顿图  §6  有向哈米尔顿图  §7  哈米尔顿图的寻迹  §8  流动推销员问题  §9  TSP的近似算法  §10  TPS的分枝定界法  §11  旅行推销员问题的应用  习题6第七章  平面图  §1  平面图的概念  §2  欧拉公式  §3  平面图的对偶图  §4  库拉托夫斯基定理  §5  可平面性算法  §6  图的交叉和厚度  习题7第八章  图的着色  §1  边色数  §2  时间表问题  §3  支配集与独立集  §4  支配数、覆盖数和独立数的计算  §5  支配集与独立集的应用  §6  点色数  §7  色多项式  §8  色数的应用和算法  习题8第九章  网络流问题  §1  流与截集  §2  最大流最小截集定理  §3  ford和fulkcrson标记法  §4  Dinits法  §5  最大流问题的应用与推广  §6  最小费用流  §7  有向图的中国邮递员问题  习题9参考文献

章节摘录

　　利用图论的方法解决实际问题时，通常要借助于计算机。怎样把图的数据存储到计算机里是一个首先要解决的问题，一般是根据具体的图以及将要做的运算来选择适当的存储结构，下面介绍几种常用的存储结构。　　1.4.1邻接矩阵　　用邻接矩阵表示图，较容易判定两个顶点之间是否有边相连，也容易求出各顶点的次数。邻接矩阵可用二维数组来表示，如果是无向图，由于对称性，仅需存人上三角矩阵。　　邻接矩阵的主要缺点是占用的空间较大，要占用O（n2）空间（n为图的顶点数），而且用直接法将邻接矩阵初始化也将占用较多的时间，因而很难改进算法的时间复杂性与空间复杂性的量级。　　对无重边的图，其邻接矩阵是（0，1）矩阵，一种有效的改进方法是用二进制位向量来表示一个邻接矩阵的行（或列），有的编程语言提供了“位操作”运算，如“与”“或”“非”和“异或”等。因此，可以把一个机器字看成不是一个“数”，而是每一位是互相独立的向量，这样的机器字是一个二进制的位向量，用来表示邻接矩阵的行（或列），若对其进行位操作，运算速度要快得多。位向量的数据结构也有缺点，当行的元素数目大于计算机字长时，要用两个以上的机器字联合表示，运算就不方便了。　　1.4.2关联矩阵　　用关联矩阵表示图，能迅速指出与某一顶点v关联的是哪些边，而且还可指出某条边关联的是哪两个顶点，对于有风吹草动图还能区分出入次和出次。关联矩阵一般是用一个二维数组Mnm来表示，这需要很大的存储空间，如存入一个100个顶点、500条边的图，则需近50K的内存，而其中很多元素是零。特别是稀疏矩阵，空间的浪费相当大。不过如果空间不紧张，这种存储方式还是可取的，因为它可获得时间高效的算法，空间的损失可从时间的获益得到补偿，但是空间不够，可采用比较紧凑的数据结构，然后通过运算，转换成关联矩阵，当然，有时当关联矩阵是（0，1）矩阵时，也可用二进制位向量来表示关联矩阵的行（或列）。

编辑推荐

　　图论与网络最优化算法是一门提供离散数学模型的应用数学学科。随着计算机在社会中作用的变大，其应用日益广泛，应用遍及系统工程、电工学、交通运输、城市规划、生产管理、经济、通信、计算机等各个领域，人工智能、模式识别、计算机操作系统、数据结构等都涉及图论。　　本书则主要向你介绍了图与网络的基本概念、树及其算法、连通性、路径算法、匹配、行遍性问题、平面图、图的着色及网络流问题。其中包含较丰富的实际应用案例与算例。

用户评论 (总计6条)

•   “图论与网络最优化算法”是一本很现代的书，它与现代的科技紧密结合，它把离散数学特别是图论的知识与网络紧密结合，在工程技术和国民经济中都可找到其应用。
•   该教材深入浅出，难易适中，便于我们学习
•   很不错的书。印刷排版都很不错。很喜欢呢。。。。
•   老师写的教材。。。。。
•   例子不多，内容很杂，基本概念讲解不是很透彻，如果只是要求对图论和网络最优化有个初步了解看看还行
•   这边看起来比较费劲，不过还行吧……