图的匹配多项式及其应用PDF电子书下载

第1章 匹配多项式的概念及性质 1

1.1 图的基本概念、术语和记号 1

1.2 图的匹配多项式及相关概念 3

1.3 递推公式 6

1.4 积分公式 10

1.5 图与它的补图的匹配多项式 14

1.6 图的匹配多项式与特征多项式 17

1.7 一些说明 21

第2章 一些特殊图的匹配多项式 22

2.1 特殊图的匹配多项式 22

2.2 圈链图的匹配多项式 26

2.3 广义圈链的匹配多项式 31

2.4 剖分图的匹配多项式 35

2.5 图的运算和匹配多项式 39

2.5.1 第一种图变换 39

2.5.2 第二种图变换 41

2.5.3 第三种图变换 42

2.5.4 第四种图变换 44

2.6 一些说明 45

第3章 匹配多项式的根与系数 46

3.1 匹配多项式的根 46

3.2 匹配多项式的系数 53

3.3 一些图类的匹配最大根 56

3.4 匹配多项式与特征多项式的性质类比 64

3.5 匹配根的Gallai定理 65

3.6 一些说明 74

第4章 匹配根对图的刻画 75

4.1 匹配最大根对图的刻画 75

4.2 匹配次大根小于1的图 78

4.3 匹配次大根等于1的图 82

4.4 至多有两个正匹配根的图 90

4.5 最多有五个不同匹配根的图 93

4.6 恰有k个正匹配根的树 96

4.7 一些说明 99

第5章 匹配唯一的图 100

5.1 匹配唯一的正则图 100

5.2 匹配唯一的几乎正则图 104

5.3 梅花图的匹配唯一性 110

5.4 匹配唯一的T-形树 119

5.5 带有较少匹配根的匹配唯一图 131

5.6 一些说明 138

第6章 图的匹配等价图类 139

6.1 路及点圈并图的匹配等价图类 139

6.2 In的匹配等价图类 144

6.3 K1∪In的匹配等价图类 150

6.4 两种度序列图的匹配等价图类 153

6.5 一些说明 159

第7章 图匹配等价的充要条件 160

7.1 最大根小于2的图匹配等价的一个充要条件 160

7.2 最大根不大于2的图匹配等价的一个充要条件 164

7.3 图的线性表示和匹配等价 170

7.4 构造匹配等价图的若干方法 173

7.5 一些说明 177

第8章 图的匹配等价图的个数 178

8.1 路并图的匹配等价图的个数 178

8.2 I-形图并图的匹配等价图数 181

8.3 点圈并图的匹配等价图数 186

8.4 一些说明 192

第9章 匹配多项式的应用 193

9.1 满足某些不等式条件的置换的计数 193

9.1.1 满足一个线性不等式条件的置换的计数 193

9.1.2 满足两个线性不等式条件的置换的计数 195

9.1.3 满足一个二次不等式条件的置换的计数 198

9.2 匹配能量和Hosoya指标的计算公式 201

9.3 树及单圈图中的匹配能量极值图 208

9.4 θ-图的匹配能量全排序 212

9.5 8-字图的匹配能量全排序 218

9.6 哑铃图的匹配能量局部排序 221

9.7 双圈图中的匹配能量极值图 228

9.8 广义θ-图匹配能量排序 232

9.9 树、单圈及双圈图的补图的匹配能量 238

9.10 由路产生的一些图的补图的匹配能量 245

9.10.1 路并补图的匹配能量 246

9.10.2 k-叉树补图的匹配能量 246

9.10.3 梅花图补图的匹配能量 248

9.10.4 广义θ-图补图的匹配能量 249

9.11 一些说明 250

参考文献 252

附录 258