图的匹配多项式及其应用

目录
前言
第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