圖的匹配多項式及其應(yīng)用

目錄
前言
第1章 匹配多項式的概念及性質(zhì) 1
1.1 圖的基本概念、術(shù)語和記號 1
1.2 圖的匹配多項式及相關(guān)概念 3
1.3 遞推公式 6
1.4 積分公式 10
1.5 圖與它的補(bǔ)圖的匹配多項式 14
1.6 圖的匹配多項式與特征多項式 17
1.7 一些說明 21
第2章 一些特殊圖的匹配多項式 22
2.1 特殊圖的匹配多項式 22
2.2 圈鏈圖的匹配多項式 26
2.3 廣義圈鏈的匹配多項式 31
2.4 剖分圖的匹配多項式 35
2.5 圖的運(yùn)算和匹配多項式 39
2.5.1 第一種圖變換 39
2.5.2 第二種圖變換 41
2.5.3 第三種圖變換 42
2.5.4 第四種圖變換 44
2.6 一些說明 45
第3章 匹配多項式的根與系數(shù) 46
3.1 匹配多項式的根 46
3.2 匹配多項式的系數(shù) 53
3.3 一些圖類的匹配*大根 56
3.4 匹配多項式與特征多項式的性質(zhì)類比 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 構(gòu)造匹配等價圖的若干方法 173
7.5 一些說明 177
第8章 圖的匹配等價圖的個數(shù) 178
8.1 路并圖的匹配等價圖的個數(shù) 178
8.2 I-形圖并圖的匹配等價圖數(shù) 181
8.3 點圈并圖的匹配等價圖數(shù) 186
8.4 一些說明 192
第9章 匹配多項式的應(yīng)用 193
9.1 滿足某些不等式條件的置換的計數(shù) 193
9.1.1 滿足一個線性不等式條件的置換的計數(shù) 193
9.1.2 滿足兩個線性不等式條件的置換的計數(shù) 195
9.1.3 滿足一個二次不等式條件的置換的計數(shù) 198
9.2 匹配能量和Hosoya指標(biāo)的計算公式 201
9.3 樹及單圈圖中的匹配能量極值圖 208
9.4 θ-圖的匹配能量全排序 212
9.5 8-字圖的匹配能量全排序 218
9.6 啞鈴圖的匹配能量局部排序 221
9.7 雙圈圖中的匹配能量極值圖 228
9.8 廣義μ-圖匹配能量排序 232
9.9 樹、單圈及雙圈圖的補(bǔ)圖的匹配能量 238
9.10 由路產(chǎn)生的一些圖的補(bǔ)圖的匹配能量 245
9.10.1 路并補(bǔ)圖的匹配能量 246
9.10.2 k-叉樹補(bǔ)圖的匹配能量 246
9.10.3 梅花圖補(bǔ)圖的匹配能量 248
9.10.4 廣義μ-圖補(bǔ)圖的匹配能量 249
9.11 一些說明 250
參考文獻(xiàn) 252
附錄 258