图论算法及其MATLAB实现

图书标准信息

• 作者 王海英 著
• 出版社 北京航空航天大学出版社
• 出版时间 2010-02
• 版次 1
• ISBN 9787811249408
• 定价 24.00元
• 装帧 平装
• 开本 16开
• 纸张 胶版纸
• 页数 154页
• 字数 262千字
• 正文语种 简体中文

【内容简介】

　　《图论算法及其MATLAB实现》系统介绍了图论重要算法的思想及其MATLAB实现。全书分为相对独立的9章，每章都是解决一类问题的算法思想及其MATLAB实现，首先介绍有关基础知识，然后给出相关著名实际问题及解决此问题的算法思想，最后给出MATLAB实现。第1章主要介绍图论的基础知识，同时也给出了可达矩阵的计算，以及关联矩阵和邻接矩阵的相互转换等重要算法及其MATLAB实现；第2～8章分别介绍最短路、连通图、树、Euler图和Hamilton图、匹配、网络中的流、最小费用流等相关问题，而且均给出了有关问题的解决算法及其MATLAB实现；第9章主要介绍染色问题，本章不仅介绍了几种传统的染色思想，而且还给出了当今研究领域中非常活跃的非传统染色思想，并分别给出其MATLAB实现。
　　《图论算法及其MATLAB实现》可供数学、计算机科学、工程科学等学科中相关专业的大学生、研究生阅读，也可供相关专业研究人员参考。

【目录】

第1章图论的基础知识
1.1图论的起源
1.2著名的图论学者——欧拉
1.3图
1.4特殊图类
1.5有向图
1.6图的矩阵表示
1.6.1邻接矩阵
1.6.2关联矩阵
1.7图论的基本性质和定理
1.8计算有向图的可达矩阵的算法及其MATLAB实现
1.9关联矩阵和邻接矩阵的相互转换算法及其MATLAB实现
习题一

第2章最短路
2.1路
2.2最短路问题
2.3求连通图最短距离矩阵的算法及其MATLAB实现
2.4求两点间最短路的Dijkstra算法及其MATLAB实现
2.4.1Dijkstra算法
2.4.2Dijkstra算法的MATLAB实现
2.5求两点间最短路的改进的Dijkstra算法及其MATLAB实现
2.5.1Dijkstra矩阵算法Ⅰ
2.5.2Dijkstra矩阵算法Ⅱ
2.6求两点间最短路的WarshallFloyd算法及其MATLAB实现
2.6.1Floyd算法的基本思想
2.6.2Floyd算法的基本步骤
2.6.3WarshallFloyd算法的MATLAB实现
2.7求任意两点间最短路的算法及其MATLAB实现
2.8求从一固定点到其他所有点最短路的算法及其MATLAB实现
2.9求必须通过指定两个点的最短路的算法及其MATLAB实现
2.10求图的两顶点间最短路与次短路的算法及其MATLAB实现
2.11求最大可靠路的算法及其MATLAB实现
2.11求最大期望容量路的算法及其MATLAB实现
习题二

第3章连通图
3.1判断图的连通性算法及其MATLAB实现
3.2连通图的中心和加权中心的算法及其MATLAB实现
3.3连通无向图一般中心的算法及其MATLAB实现
习题三

第4章树
4.1树及其性质
4.2割点、割边、割集
4.3二元树与Huffman树
4.3.1有序二元树
4.3.2Huffman树
4.4求Huffman树及其MATLAB实现
4.5广度优先搜索算法及其MATLAB实现
4.6深度优先搜索算法及其MATLAB实现
4.7求割点算法及其MATLAB实现
4.8生成树及其个数
4.9求无向图的生成树算法及其MATLAB实现
4.10求有向图的生成树算法及其MATLAB实现
4.11求有向连通图的外向树与内向树数目的算法及其MATLAB实现
4.12最小生成树问题
4.13求最小生成树的Kruskal算法及其MATLAB实现
4.13.1Kruskal算法的基本思想
4.13.2Kruskal算法的MATLAB实现
4.14求最小生成树的Prim算法及其MATLAB实现
4.14.1Prim算法的基本思想
4.14.2Prim算法的MATLAB实现
习题四

第5章Euler图和Hamilton图
5.1Euler图
5.2“一笔画”问题及其理论
5.3中国邮递员问题
5.4Fleury算法及其MATLAB实现
5.4.1Fleury算法的步骤
5.4.2Fleury算法的MATLAB实现
5.5Hamilton图
5.6旅行售货员问题
5.7改良圈算法及其MATLAB实现
习题五

第6章匹配问题及其算法
6.1问题起源——婚配问题
6.2二分图的有关知识
6.3匹配、完美匹配、最大匹配
6.4匹配的基本定理
6.5应用案例——Bernolli-Euler错放信笺问题
6.6寻求图的一个较大基数匹配算法及其MATLAB实现
6.7人员分配问题
6.8匈牙利算法及其MATLAB实现
6.8.1匈牙利算法基本步骤
6.8.2匈牙利算法的MATLAB实现
6.8.3案例及其MATLAB实现
6.9最优分配问题
6.10Kuhn-Munkres算法及其MATLAB实现
6.10.Kuhn-Munkres算法的基本思想
6.10.2利用可行顶点标记求最佳匹配的Kuhn-Munkras算法步骤
6.10.3Kuhn-Munkres算法的MATLAB实现
6.10.4简单实验
习题六

第7章网络流的算法
7.1网络、流和割
7.1.1网络和流
7.1.2割
7.2网络的最大流问题
7.3最大流最小割定理
7.4Ford-Fulkerson标号算法及其MATLAB实现
7.4.1Ford-Fulkerson标号算法的基本步骤
7.4.2Ford-Fulkerson标号算法的MATLAB实现
7.4.3案例及其MATLAB实现
7.51Dinic算法及其MATLAB实现
7.5.1Dinic算法的基本思想
7.5.2Dinic算法的MATLAB实现
7.5.3案例及其MATLAB实现
7.6容量有上下界的网络及其相关算法
7.7有供需约束的流及其相关算法
习题七

第8章最小费用流及Busacker-Gowan迭代算法
8.1最小费用流问题
8.2Busacker-Gowan迭代算法及其MATLAB实现
8.2.1Busacker-Gowan迭代法
8.2.2Busacker-Gowan迭代法的MATLAB实现
8.2.3案例及其MATLAB实现
习题八

第9章图的染色
9.1染色问题起源
9.2顶点染色及其算法的MATLAB实现
9.2.1顶点染色以及顶点色数
9.2.2应用案例：贮藏问题
9.2.3顶点染色算法的MATLAB实现
9.3边染色算法及其MATLAB实现
9.3.1边染色以及边色数
9.3.2应用案例：排课问题
9.3.3边染色算法的MATLAB实现
9.4全染色算法及其MATLAB实现
9.4.1全染色以及全色数
9.4.2全染色算法与案例
9.5均匀全染色算法及其MATLAB实现
9.5.1均匀全染色以及均匀全色数
9.5.2均匀全染色算法的MATLAB实现与案例
9.6邻点可区别全染色算法及其MATLAB实现
习题九
参考文献