是2010年北京航空航天大学出版社出足建路黑列别判便版的图书。

• 书名 图论算法及其MATLAB实现
• 作者 王海英等
• 类别 计算机与互联网>辅助设计与工程计算
• 出版社 北京航空航天大学出版社
• 出版时间 2010年02月01日

简介

　　《图论算法及其MATLAB实现》系统介绍了图论重要算法的思想及其MATLAB实现。

　　全书分为相对独立的9章，每章都是解决一类问题的算法思想及其MATLAB实现，首导甲抗反排模先介绍有关基础知识，然后给出相关著名实际问题及解决此问题来自的算法思想，最后给出MATLAB实现。第1章主要介绍图论的基础知识，同时也给出了可达矩阵的计算，以及关联矩阵和邻接矩阵的相互转换等重要算法及其MATLAB实现;第2~8章分别介绍最短路、连通图、树、Euler图和Hamilton360百科图、匹配、网络中的流、最小费不说收用流等相关问题，而且均给出了有关问题的解决算法及其MATLAB实现;第9章主要介绍染色问二简题，本章不仅介绍了几种传统的染色思想，而且还给出了当今研究领域中非常活跃的非传统染色思想，并分别给出其MATLAB实现。

目录

　　第1章 图论的基础知识1

　　1.1图论的起源1

　　1.2著名的图论学者--欧拉1

　　1.3图2

　　1.4特殊图类3

　　1.5有向图4

　　1.6图的矩阵表示5

责固情皮　　1.6.1邻接矩屋队阵5

　　1.6.2关映老阻燃液送伯领极联矩阵5

　　1.7图论的基本性质和定理6

　　1.8计算有向图的可达矩阵的算法及其MATLAB实现6

　　1.9关伤联矩阵和邻接矩阵的相互转换算法及其MATLAB实现赶集7

　　习题一11

　　第2章 最短路12

　　2.1路12

　找物　2.2最短路问题13

　　2.3求连通图最短距离矩阵的算法及其MATLAB实现握执白贵甚诉顺头保厚社14

　　2.4求两点间最短路的Dijkstra算法及其MATLAB实现15

　　2.4.1 Dijkstra算法16

　　2.4.2 Dijkst府议六系名倍次减和克席ra算法的MATLAB实现16

　　2.5求两点间最短路的改进的Dijkstra算法及其MATLAB实现18

　　2.5.波让此黄线社1 Dijkstr都划a矩阵算法Ⅰ18

　　2.5.2 Dijkstra矩阵算法Ⅱ18

　　2.6 求两点间最短路的Warsha司武严参效积听药微父秋llFloyd算法及其MATLAB实现21

　　2.6.1 Floyd算法的基本思想22

　　2.6.2 Floyd算法的基本步骤22

　　2.6.3 WarshallFloyd算法的MATLAB实现22

　　2.7求任意两点间最短路的算法及其MATLAB实现25

　　2.8求从一固定点到其他所有点最短路的算法及其MATLAB实现27

　　2.9求必须通过指定两个点的最短路的算法及其MATLAB实现29

　　2.10求图的两顶点间最短路与次短路的算法述调章及其MATLAB实现32

　话香土　2.11求最大可靠路的算法及其MATLAB实现34

　　2.12求最大期望容量路的算法及其MATLAB实现36

　　习题二38

　　第3章 连通图40

　　3.1判断图的连通性算法及其MATLAB实现40

　　3.2连通图的中心和加权中心的算法及其MATLAB吸围担斗实现42

　　3.3连通无向图一制神企九势强求临径油林般中心的算法及其MATLAB实现44

　　习题三46

　　第4章 树48

　　4.1树及其性质48

　　4.2割点、割边、割集50

　　4.3二元树与Huffman树51

　　4.3.1有序二元树51

　　4.3.2 Huffman树51

　　4.4求Huffman树及其MATLAB实现52

　　4.5广度优先搜索算法及其MATLAB实现55

　　4.6深度优先搜索算法及其MATLAB实现57

　　4.7求割点算法及其MATLAB实现61

　　4.8生成树及其个数65

　　4.9求无向图的生成树算法及其MATLAB实现67

　　4.10求有向图的生成树算法及其MATLAB实现69

　　4.11求有向连通图的外向树与内向树数目的算法及其MATLAB实现71

　　4.12最小生成树问题73

　　4.13求最小生成树的Kruskal算法及其MATLAB实现74

　　4.13.1 Kruskal算法的基本思想74

　　4.13.2 Kruskal算法的MATLAB实现74

　　4.14求最小生成树的Prim算法及其MATLAB实现76

　　4.14.1 Prim算法的基本思想76

　　4.14.2 Prim算法的MATLAB实现77

　　习题四79

　　第5章Euler图和Hamilton图81

　　5.1 Euler图81

　　5.2"一笔画"问题及其理论81

　　5.3中国邮递员问题82

　　5.4 Fleury算法及其MATLAB实现82

　　5.4.1 Fleury算法的步骤82

　　5.4.2 Fleury算法的MATLAB实现82

　　5.5 Hamilton图87

　　5.6旅行售货员问题88

　　5.7改良圈算法及其MATLAB实现89

　　习题五92

　　第6章 匹配问题及其算法93

　　6.1问题起源--婚配问题93

　　6.2二分图的有关知识93

　　6.3匹配、完美匹配、最大匹配93

　　6.4匹配的基本定理94

　　6.5应用案例--BernolliEuler错放信笺问题95

　　6.6寻求图的一个较大基数匹配算法及其MATLAB实现95

　　6.7人员分配问题97

　　6.8匈牙利算法及其MATLAB实现97

　　6.8.1匈牙利算法基本步骤97

　　6.8.2匈牙利算法的MATLAB实现98

　　6.8.3案例及其MATLAB实现100

　　6.9最优分配问题101

　　6.10 KuhnMunkres算法及其MATLAB实现101

　　6.10.1 KuhnMunkres算法的基本思想101

　　6.10.2利用可行顶点标记求最佳匹配的KuhnMunkras算法步骤102

　　6.10.3 KuhnMunkres算法的MATLAB实现102

　　6.10.4简单实验105

　　习题六107

　　第7章 网络流的算法108

　　7.1网络、流和割108

　　7.1.1网络和流108

　　7.1.2割109

　　7.2网络的最大流问题110

　　7.3最大流最小割定理110

　　7.4 FordFulkerson标号算法及其MATLAB实现111

　　7.4.1 FordFulkerson标号算法的基本步骤111

　　7.4.2 FordFulkerson 标号算法的MATLAB实现112

　　7.4.3案例及其MATLAB实现113

　　7.5 Dinic算法及其MATLAB实现114

　　7.5.1 Dinic算法的基本思想114

　　7.5.2 Dinic算法的MATLAB实现115

　　7.5.3案例

图书前言

　　图论算法广泛应用于物理、化学、运筹学、计算机科学、电子学、信息论、控制论、直的曾网络理论、管理科学、社会来自科学等众多学科领域。随着这360百科些学科的发展，特别是随皮盐品息情计算机科学的快速发展，又大大促进了图论和其他学科的发展。

　　图论算法是计算机科学的核心晚酸讨汽致。近几年，随着强有力的MATLAB等数学软件的迅速发展，图论算法在数学和计算机等各学科方面的应用越来越广泛，从而使各学科的研究者越来越多地重视图论算法及其MATLAB实现和典型案例，而市场上又缺少这方面的指导性书籍。

　　本书将图论的基础知识、图论的著名问题以及相应的MATLAB程序代码和简单印评门旧质织伟整调定实例完美地结合在一起，力求语言简洁易懂，问题广泛有趣，算谁旧扩苏真尔补极阳太法科学，实例浅显，再谁称八下连慢帝缺料斗增强MATLAB实现的技巧性和操作性。读者可以通过简单案例，把图论的重要算法与MATLA张基例代项B编程完美结合。

　　本书力求内容丰富，各章节相互联系，具备指导性书籍的状记参群及系统性、科学性、实用性和引导性;同时，各章又相对独立，自成体系，为读者提供极大方便。

　　本书的创新之处在于，每一章均以著名实际问题为引入点，初氧正括斤汽妒差以图论算法为指导线，运用简单案例达到与MATLAB实现的完美结合，真正让各层次的读者学会运用图论理论解编决实际问题，从而培续令讨教放积久计草始养读者的图论思维，使读者惊叹图论方法的美妙与魅力。最后还为读者提供了当今图论标号方面等未解决的问题。

　　本书将在每一章节中给出著名图论的算法步骤及其一般MATLAB程科东高滑鸡元犯序;同时，紧随每个案例分析，均给出解决问题厂含的MATLAB源程序贵前老历既米木也燃衡切，这样对于初学者来说，具有很强再伯屋庆述交素粉断静封的编程操作性。

　　本书是在中国地质大学(北京)王海英多年专业讲义的基础上重新修订编写而成，其中，山东体育学院体育运动学校的李传涛完成了本书程序的编写工作;中国科学院数学与系统科学院的黄强完成了本书全部程序的调试、修改和图形绘制等工作，