图论算法及其MATLAB实现2025|PDF|Epub|mobi|kindle电子书版本百度云盘下载

图论算法及其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