图论导引PDF电子书下载

第一章 绪论 1

基本概念 1

顶点数、边数与次数间的关系：1—13 3

鸽笼原理 7

具有n个顶点的完全图的边数：11 8

关于补图问题：16即14 10

在连通图中，顶点数、边数与次数间的关系：18—22 15

有关路与回路的一些简单的问题：23与24 17

最长路方法 18

连通图的两个性质：25与26 19

练习、问题 19

第二章 树与林 22

在树中，顶点数与边数间的关系：5与6（1—4为此准备） 23

在化学中的应用：7与8 24

在树中的路：9 26

林（10为此准备） 28

生成树的特征：11 29

基本回路、基本回路组的特征：17 30

图的生成林 32

图的秩与零度：18（13—15为此准备） 32

建立无回路网络的经济的方式；三种方法 33

寻求生成树，使之分别有极小值与极大值 35

生成树在计算电网络中的应用 40

两个基尔霍夫定律 40

练习、问题 44

第三章 沿着图的边的路线 48

哥尼斯堡（K？nigsberg）七桥问题：4 50

开的与闭的边列 52

开的与闭的欧拉线分别存在的恰当条件：6与7（5为此准备） 54

与有向图有关的基本概念 55

有向路、回路与边列 56

利用有向图来描述通行问题 57

通行条件，强连通图 58

桥与回路的关系：12与13 60

给无桥连通图以定向，使之成为强连通图：18（10与14为此准备） 61

从极大和极小出发的方法 61

在有向图中存在闭欧拉线的恰当条件：19（15为此准备） 63

应用于无向图：20 63

关于无限图的注 65

在迷宫里 67

两项走迷宫的规则 68

走展览厅的迴廊 71

随意欧拉图的结构：23与24（21、22为此准备） 73

练习、问题 75

第四章 覆盖一个图中顶点的路线 79

十二面体游戏：1 79

哈密尔顿回路，哈密尔顿路 80

使哈密尔顿回路与路分别不存在的条件：3，割点 80

应用—在棋盘上跳马：4与5（图99） 81

十二面体游戏的最后的分析（6与7为此准备） 86

使长度超过定值的回路存在的次数条件：13即8 91

使哈密尔顿回路与哈密尔顿路分别存在的次数条件：14（9为此准备）、15（10—12为此准备）、以及16 92

有向哈密尔顿回路与路 99

界面是三角形的多面体上的哈密尔顿回路 99

具有哈密尔顿路的竞赛图：18（17为此准备） 101

使有向哈密尔顿回路与有向哈密尔顿路分别存在的条件：19—22 102

关于无限图的哈密尔顿路的注 103

练习、问题 103

第五章 匹配问题因子 106

组织一项循环赛 106

完全图作为1－因子的积：1（“组织一项循环赛”为此作准备） 108

k－因子，正则图 108

独立边集、极大独立边集 108

偶次正则图是2－因子的积：13（3、5、10—12为此准备） 110

完全图作为哈密尔顿回路的积（图135） 113

双图的特征：14与15 114

双图（4、6及7为此准备） 114

正则双图作为1－因子的积：18（8、9、16及17为此准备） 117

覆盖顶点集的边，结婚问题：19（4、6及17为此准备） 118

交错路方法 120

寻求双图中极大独立边集的算法（匈牙利方法）：20（19的一个应用为此准备） 122

覆盖顶点集、极小覆盖顶点集 123

对于双图，iemax=cvmin：22 123

独立顶点集、极大独立顶点集 127

覆盖边集、极小覆盖边集 127

对于无孤立顶点的双图，ivmax=cemin:30 129

使大于定值的独立边数存在的次数条件：31（25为此准备） 129

使在双图中存在哈密尔顿回路的次数条件：32与33（26为此准备） 130

双图的1－因子存在的恰当条件：34（27为此准备） 133

任意图存在1－因子的恰当条件：35 133

应用于无桥的3－正则图：36—41 134

不能分解为几个因子之积的正则图：42（图149及154） 138

练习、问题 138

第六章 极值极图 142

几类极值问题 142

一些初等组合定理：4—8（1—3为此准备） 144

定义拉姆舍（Ramsey）数n（m,k）的三种方式 147

拉姆舍定理的一个特殊情况：22；拉姆舍数的估计与几个准确值：10、12、15、16、18、19、23及24（11、13、14、17、19、20及21为此准备） 154

更一般的拉姆舍数 157

借助于无有向回路图的结构来解一个拉姆舍型极值问题．在数论 157

中的一个应用：25、28及注2 157

更深入的拉姆舍型问题的一些特殊情况：26、27、29及30 158

存在三角形的次数与边数条件：38—40（17及31—35为此准备） 167

存在具有k个顶点的完全子图的次数与边数条件：43与44（36—42为此准备） 172

命题43在几何中的一个应用：49（45—48为此准备） 176

cvmin、边数与顶点数间的关系：53与54（50—52为此准备） 180

当ivmax固定或有界时，存在三角形（或小于定值的奇长度的回路） 182

的次数与边数条件：55、62—66（56—61为此准备） 182

图的块的概念（67为此准备） 194

使长度超过定值的路存在的次数条件：70（68为此准备） 196

使长度超过定值的路或回路存在的边数条件：71及72（69、70为此准备） 197

存在顶点不相交回路的边数条件：80（73、75及76为此准备） 202

存在边不相重回路的边数条件：81（74、77—79为此准备） 205

练习、问题 206

第七章 练习与问题的解答 211

引文索引 267

文献目录 269

内容索引 273