极大平面图理论PDF电子书下载

第1章 图论基础 1

1.1图的定义与类型 1

1.2图的度序列 6

1.2.1度序列定义及性质 6

1.2.2可图序列的特征 7

1.2.3可图序列的实现计数与构造 8

1.3图的运算 8

1.3.1子图与图的一元运算 9

1.3.2二元运算 10

1.3.3一元运算续 13

1.4图的同构 15

1.4.1定义与记号 15

1.4.2同构测试算法 17

1.4.3图同构的应用 17

1.5图的矩阵 18

1.6平面图 20

1.6.1相关定义 20

1.6.2欧拉公式及应用 21

1.6.3 Kuratowski定理 22

1.6.4平面嵌入算法 22

1.7图着色 23

1.7.1定义与分类 23

1.7.2图的色数 24

1.7.3图着色算法 25

1.7.4图着色应用 28

参考文献 29

第2章 放电变换与极大平面图的结构 33

2.1欧拉公式 33

2.2放电变换 34

2.3路型结构 35

2.3.1边 35

2.3.2 3-路P3 40

2.4面型结构 54

2.5圈和星图 76

2.5.1圈的权重w（Ck）及其上点的度数限制？（Ck） 76

2.5.2星图 77

参考文献 78

第3章 四色猜想的计算机证明 82

3.1四色猜想 82

3.2 Kempe“证明”与Heawood反例 82

3.3不可避免的可约构形集 86

3.3.1基本概念 86

3.3.2不可避免集 87

3.3.3构形的可约性 89

3.4计算机证明 91

3.5改进与总结 102

参考文献 105

附图 107

第4章 同阶极大平面图的构造 137

4.1基本概念 137

4.2同阶极大平面图的相互转化 139

4.3边翻转运算数目的上界 142

4.4边翻转运算数目的下界 146

参考文献 148

第5章 异阶极大平面图的构造 149

5.1纯弦圈法 149

5.2递归生成5-连通极大平面图 151

5.3最小度为5的4-连通和3连通极大平面图的递归生成 154

5.4递归生成δ≥4的极大平面图 157

5.5偶极大平面图的递归生成 159

5.6最小度为5阶数≤19极大平面图 161

参考文献 164

第6章 极大平面图的生成运算系统 165

6.1极大平面图的基本扩缩运算系统 165

6.2多米诺扩缩运算系统 168

6.2.1连续扩缩运算与多米诺扩缩运算 168

6.2.2轮心数≤3的多米诺扩缩运算与多米诺构形 169

6.2.3扩轮对象集 171

6.2.4多米诺构形的定义 172

6.2.5多米诺构形的特征 175

6.3祖先图与子孙图 178

6.3.1子孙图 178

6.3.2祖先图 181

6.4极大平面图的构造方法 183

6.4.1构造的一般理论 183

6.4.2可分极大平面图的构造 184

6.4.3非可分极大平面图构造基本定理 186

6.4.4非可分极大平面图的构造方法与步骤 189

6.5小结 191

参考文献 192

第7章 色多项式递推公式与四色猜想 193

7.1色多项式的缩轮递推公式 193

7.2证明四色猜想的新思路 197

参考文献 200

第8章 纯树着色与唯一4-色极大平面图猜想 202

8.1唯一4-色极大平面图研究进展 202

8.2树着色与圈着色 204

8.3纯树着色极大平面图 205

8.3.1最小度为5的纯树着色极大平面图猜想 205

8.3.2哑铃极大平面图 206

8.4递归极大平面图 209

8.4.1基本性质 210

8.4.2（2.2）-递归极大平面图 211

8.4.3扩4-轮运算图的着色 215

8.5唯一4-色极大平面图的证明思路 216

8.6小结 217

参考文献 218

第9章 Kempe变换 220

9.1定义与基本性质 220

9.2 Kempe等价类 222

9.2.1基于顶点着色的K-类 222

9.2.2基于边着色的K-类 226

9.2.3着色重构图 227

9.3 σ-运算 228

9.3.1 2-色耳相关定义与性质 228

9.3.2 σ-运算 232

9.4 σ-特征图 233

9.4.1 σ-特征图定义 233

9.4.2 σ-特征图基本性质 234

9.5极大平面图的Kempe等价类 237

9.5.1树型Kempe等价类 237

9.5.2圈型Kempe等价类 237

9.5.3循环圈型Kempe等价类 240

参考文献 242

附录 244

附录A 6～12-阶δ≥4的极大平面图 244

附录B 6～12-阶δ≥4的非可分极大平面图的全部着色、分类及特征图 250