图论与网络最优化算法
点此进入淘宝搜索页搜索分類: 图书,科学与自然,数学,代数、数论、组合理论,
品牌: 龚劬
基本信息·出版社：重庆大学出版社
·页码：215 页
·出版日期：2009年10月
·ISBN：9787562450795
·条形码：9787562450795
·版本：第1版
·装帧：平装
·开本：16
·正文语种：中文
产品信息有问题吗？请帮我们更新产品信息。
内容简介《图论与网络最优化算法》共分9章：图与网络的基本概念、树及其算法、连通性、路径算法、匹配、行遍性问题、平面图、图的着色及网络流问题。其中包含较丰富的实际应用案例与算例，每章末均附有较多难易程度不同的习题，另外还附有少量涉及网络建模与计算的大型综合应用题。
《图论与网络最优化算法》是一本理论与应用相结合的基础教材，可作为高等工科院校系统工程、管理工程、自动控制、通信与计算机科学、城市规划等专业高年级本科生或研究生的教材和教学参考书，也可供有关专业的科研人员自学。
编辑推荐《图论与网络最优化算法》是由重庆大学出版社出版的。
目录
第1章 图与网络的基本概念
1.1 绪论
1.2 一些基本概念
1.3 图的矩阵表示
1.4 图在计算机中的存储
1.5 算法及其计算复杂性
习题1
第2章 树
2.1 路径与连通
2.2 有向图的连通性
2.3 图的搜索
2.4 树及其性质
2.5 生成树算法
2.6 有向树
习题2
第3章 连通性
3.1 连通度
3.2 割边、割集、割点
3.3 块与块划分
3.4 可靠网络的设计
习题3
第4章 路径算法
4.1 最短路径问题
4.2 最短路径问题的一些扩展
4.3 最优路径
4.4 关键路径
4.5 最短路径算法的应用
习题4
第5章 匹配
5.1 匹配的概念
5.2 匹配基本定理、
5.3 二部图的最大匹配
5.4 二部图的最大权匹配
5.5 一般图的最大匹配
5.6 一般图的最大权匹配
5.7 匹配的应用
习题5
第6章 行遍性问题
6.1 欧拉图
6.2 中国邮递员问题
6.3 有向欧拉图
6.4 中国邮递员问题的应用与推广
6.5 哈米尔顿图
6.6 有向哈米尔顿图
6.7 哈米尔顿圈的寻迹
6.8 流动推销员问题
6.9 TSP的近似算法
6.1 0TsP的分枝定界法
6.1 1旅行推销员问题的应用
习题6
第7章 平面图
7.1 平面图的概念
7.2 欧拉公式
7.3 平面图的对偶图
7.4 库拉托夫斯基定理
7.5 可平面性算法
7.6 图的交叉和厚度
习题7
第8章 图的着色
8.1 边色数
8.2 时间表问题
8.3 支配集与独立集
8.4 支配数、覆盖数和独立数的计算
8.5 支配集与独立集的应用
8.6 点色数
8.7 色多项式
8.8 色数的应用和算法
习题8
第9章 网络流问题
9.1 流与截集
9.2 最大流最小截集定理
9.3 ford和fulkerson标记法
9.4 Dinits法
9.5 最大流问题的应用与推广
9.6 最小费用流
9.7 有向图的中国邮递员问题
习题9
参考文献
……[看更多目录]
序言图论与网络最优化算法是一门提供离散数学模型的应用数学学科。随着计算机在社会中作用的变大，其应用日益广泛，应用遍及系统工程、电工学、交通运输、城市规划、生产管理、经济、通信、计算机等各个领域，人工智能、模式识别、计算机操作系统、数据结构等都涉及图论。
本教材的学习主要有以下4个方面的作用：
1.思维的体操。其中含有广泛的数学思想和数学方法，诸如优化、分类、数形结合、转化的思想、分解的思想、归纳、演绎和逆推等。这是其他工科数学所无法比拟的，对培养我们的数学机敏性与成熟性大有益处。
2.算法设计者的翅膀。图论算法是算法设计与分析中的重要组成部分，其中包含常用的算法设计基本方法，如搜索技术、分支定界法、回溯法、贪婪法及各种启发式算法，算法的时间复杂性分析，近似算法的近似程度分析也融入其中。
3.综合应用能力形成的催化剂。书中几乎每章末都有关于图论理论和算法在实际中的各种应用，也含有一些具有一定灵活性和创造性的应用案例，配有大量颇具启发性和趣味性的习题。图论与代数、运筹学密切相关，概率统计与网络交叉有活动网络，这些都有助于我们综合运用数学能力的提高。图论中的图具有最复杂的非线性数据结构，如果将其中的算法编程实现，编程能力可上一个新的台阶。
4.描述和解决离散问题的有利工具。在工农业生产、交通运输、通信和电力领域经常能看到许多网络，如河道网、灌溉网、管道网、公路网、铁路网、电话线网、计算机通信网及输电线网等。还有许多看不见的网络，各种关系网，如状态转移关系、事物的相互冲突关系、工序的时间先后次序关系等，这些网络都可归结为图论的研究对象——图。其中存在大量问题，如生产计划、投资计划和设备更新等问题也可以转化为网络优化的问题，这些都可借助于图论这个工具来加以解决。
文摘插图：
利用图论的方法解决实际问题时，通常要借助于计算机。怎样把图的数据存储到计算机里是一个首先要解决的问题，一般是根据具体的图以及将要做的运算来选择适当的存储结构，下面介绍几种常用的存储结构。
1.4.1邻接矩阵
用邻接矩阵表示图，较容易判定两个顶点之间是否有边相连，也容易求出各顶点的次数。邻接矩阵可用二维数组来表示，如果是无向图，由于对称性，仅需存人上三角矩阵。
邻接矩阵的主要缺点是占用的空间较大，要占用O（n2）空间（n为图的顶点数），而且用直接法将邻接矩阵初始化也将占用较多的时间，因而很难改进算法的时间复杂性与空间复杂性的量级。
对无重边的图，其邻接矩阵是（0，1）矩阵，一种有效的改进方法是用二进制位向量来表示一个邻接矩阵的行（或列），有的编程语言提供了“位操作”运算，如“与”“或”“非”和“异或”等。因此，可以把一个机器字看成不是一个“数”，而是每一位是互相独立的向量，这样的机器字是一个二进制的位向量，用来表示邻接矩阵的行（或列），若对其进行位操作，运算速度要快得多。位向量的数据结构也有缺点，当行的元素数目大于计算机字长时，要用两个以上的机器字联合表示，运算就不方便了。
1.4.2关联矩阵
用关联矩阵表示图，能迅速指出与某一顶点v关联的是哪些边，而且还可指出某条边关联的是哪两个顶点，对于有风吹草动图还能区分出入次和出次。关联矩阵一般是用一个二维数组Mnm来表示，这需要很大的存储空间，如存入一个100个顶点、500条边的图，则需近50K的内存，而其中很多元素是零。特别是稀疏矩阵，空间的浪费相当大。不过如果空间不紧张，这种存储方式还是可取的，因为它可获得时间高效的算法，空间的损失可从时间的获益得到补偿，但是空间不够，可采用比较紧凑的数据结构，然后通过运算，转换成关联矩阵，当然，有时当关联矩阵是（0，1）矩阵时，也可用二进制位向量来表示关联矩阵的行（或列）。
