《优美图》

第一章 图的基本知识1

1.1 图的概念1

1.1.1 引例1

1.1.2 集合的积与二元关系2

1.1.3 图的定义4

1.2 子图和图的运算6

1.2.1 子图6

1.2.2 图的运算7

1.3 图的同构12

1.4 顶点的度数15

1.5 通路和连通18

1.6 完备图、二分图和补图22

1.7 邻接矩阵和关联矩阵26

1.8 树33

1.9 E图39

1.9.1 七桥问题39

1.9.2 E图40

1.10 有向图42

1.10.1 有向图43

1.10.2 有向树47

1.10.3 有序树50

1.10.4 k元有向树(或k元有序树)51

第二章 优美树54

2.1 优美图的概念54

2.2 优美树猜想58

2.3 一些已被证明是优美的树61

2.4 优美树的积67

2.5 优美树的矩阵表示74

2.6 龙虾树84

2.7 优美树研究的一些建议96

第三章 欧拉图的优美性98

3.1 欧拉图的优美性98

3.2 Bodendjek猜想及其证明111

3.3 Dm,n和mCn的优美性118

第四章 二分图及其它一些优美图128

4.1 二分图的优美性128

4.2 轮图、棱柱与王冠138

4.2.1 轮图的优美性138

4.2.2 棱柱与王冠142

4.3 完备图与风车图144

4.4 P1∨Pn与P(n1,n2,…，nm)的优美性147

4.4.1 P1∨Pn的优美性147

4.4.2 P(n1,n2,…，nm)的优美性149

4.5 k-优美图154

第五章 调和标号和序列标号159

5.1 调和标号和序列标号159

5.2 四种标号之间的关系165

5.3 强调和标号167

第六章 有向回路的优美性176

6.1 优美有向图的定义176

6.2 有向回路的优美性179

第七章 三种标号及其应用185

7.1 直尺模型185

7.2 非冗余标号的应用187

7.2.1 非冗余标号的定义187

7.2.2 非冗余标号的应用188

7.3 限制差基标号196

7.3.1 概要196

7.3.2 应用197

7.4 非限制差基标号200

习题解答202

参考文献239

名词索引244