图论算法及其MATLAB实现PDF电子书下载

第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 Dijkstra算法的MATLAB实现 16

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

2.5.1 Dijkstra矩阵算法Ⅰ 18

2.5.2 Dijkstra矩阵算法Ⅱ 18

2.6求两点间最短路的Warshall-Floyd算法及其MATLAB实现 21

2.6.1 Floyd算法的基本思想 22

2.6.2 Floyd算法的基本步骤 22

2.6.3 Warshall-Floyd算法的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应用案例——Bernolli-Euler错放信笺问题 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 Kuhn-Munkres算法及其MATLAB实现 101

6.10.1 Kuhn - Munkres算法的基本思想 101

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

6.10.3 Kuhn - Munkres算法的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 Ford-Fulkerson标号算法及其MATLAB实现 111

7.4.1 Ford-Fulkerson标号算法的基本步骤 111

7.4.2 Ford - Fulkerson标号算法的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案例及其MATLAB实现 118

7.6容量有上下界的网络及其相关算法 121

7.7有供需约束的流及其相关算法 123

习题七 125

第8章 最小费用流及Busacker - Gowan迭代算法 126

8.1最小费用流问题 126

8.2 Busacker-Gowan迭代算法及其MATLAB实现 127

8.2.1 Busacker-Gowan迭代法 127

8.2.2 Busacker - Gowan迭代法的MATLAB实现 128

8.2.3案例及其MATLAB实现 130

习题八 132

第9章 图的染色 133

9.1染色问题起源 133

9.2顶点染色及其算法的MATLAB实现 134

9.2.1顶点染色以及顶点色数 134

9.2.2应用案例：贮藏问题 135

9.2.3顶点染色算法的MATLAB实现 135

9.3边染色算法及其MATLAB实现 137

9.3.1边染色以及边色数 137

9.3.2应用案例：排课问题 138

9.3.3边染色算法的MATLAB实现 138

9.4全染色算法及其MATLAB实现 141

9.4.1全染色以及全色数 141

9.4.2全染色算法与案例 141

9.5均匀全染色算法及其MATLAB实现 144

9.5.1均匀全染色以及均匀全色数 144

9.5.2均匀全染色算法的MATLAB实现与案例 144

9.6邻点可区别全染色算法及其MATLAB实现 149

习题九 152

参考文献 153