《图论导引》

第一章绪论1

基本概念1

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

鸽笼原理7

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

关于补图问题：16即1410

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

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

最长路方法18

连通图的两个性质：25与2619

练习、问题19

第二章树与林22

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

在化学中的应用：7与824

在树中的路：926

林（10为此准备）28

生成树的特征：1129

基本回路、基本回路组的特征：1730

图的生成林32

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

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

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

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

两个基尔霍夫定律40

练习、问题44

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

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

开的与闭的边列52

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

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

有向路、回路与边列56

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

通行条件，强连通图58

桥与回路的关系：12与1360

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

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

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

应用于无向图：2063

关于无限图的注65

在迷宫里67

两项走迷宫的规则68

走展览厅的迴廊71

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

练习、问题75

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

十二面体游戏：179

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

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

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

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

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

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

有向哈密尔顿回路与路99

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

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

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

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

练习、问题103

第五章匹配问题因子106

组织一项循环赛106

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

k－因子，正则图108

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

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

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

双图的特征：14与15114

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

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

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

交错路方法120

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

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

对于双图，iemax=cvmin：22123

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

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

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

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

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

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

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

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

不能分解为几个因子之积的正则图：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及注2157

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

存在三角形的次数与边数条件：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