图的方法PDF电子书下载

第1章 图的基本概念 1

1.1图的概念 1

1.1.1哥尼斯堡（K？nigsberg）七桥问题 1

1.1.2图的概念 3

1.1.3子图与补图 5

1.1.4图与逻辑结构 7

习题1.1 9

1.2结点的度数 10

1.2.1结点的度数 10

1.2.2完全图 14

习题1.2 15

1.3图的连通性 16

1.3.1路径与回路 16

1.3.2无向图与有向图的连通性 18

习题1.3 22

1.4图的矩阵表示 23

1.4.1图的邻接矩阵 23

1.4.2有向图的可达矩阵 25

1.4.3赋权图的邻接矩阵 27

习题1.4 29

复习题 31

第2章 树 34

2.1无向树 34

2.1.1无向树的性质 34

2.1.2生成树 36

2.1.3最小生成树 37

习题2.1 39

2.2有向树 41

2.2.1有向树 41

2.2.2根树 41

2.2.3有序树 43

习题2.2 47

2.3二叉树的应用 48

2.3.1二叉树 48

2.3.2前缀码 48

2.3.3最优树与最优树的形成 51

2.3.4遍历二叉树 54

习题2.3 57

复习题 58

第3章 特殊的图 61

3.1欧拉图 61

3.1.1欧拉图的充要条件 61

3.1.2中国邮路问题 65

习题3.1 67

3.2汉密尔顿图 69

3.2.1汉密尔顿图及其充分条件 69

3.2.2货郎担问题 72

习题3.2 75

3.3二分图 75

3.3.1二分图的定义 76

3.3.2匹配 78

3.3.3最大匹配及其求法 79

习题3.3 82

3.4平面图 84

3.4.1平面图的充要条件 84

3.4.2欧拉定理及其推论 86

3.4.3库拉托夫斯基定理 88

3.4.4正多面体 90

习题3.4 93

复习题 95

第4章 图的简单应用 98

4.1图的着色 98

习题4.1 103

4.2最短路 103

4.2.1狄克斯屈拉算法及其执行过程 104

4.2.2最短路问题的应用 107

习题4.2 109

4.3网络应用 109

4.3.1 AOV网与拓扑排序 110

4.3.2 AOE网与关键路径 111

4.3.3网络最大流 116

习题4.3 120

复习题 121

附录 124

附录1数学实验 124

附录2参考答案 128

参考文献 138