《賦權圖的三角形覆蓋數與匹配數研究》是2023年6月北京郵電大學出版社出版的圖書，作者：唐中正。
基本介紹
- 中文名：賦權圖的三角形覆蓋數與匹配數研究
- 作者：唐中正
- 出版時間：2023年6月29日
- 出版社：北京郵電大學出版社
- ISBN：9787563569311
- 定價：49 元
出版信息,內容簡介,目錄介紹,
出版信息
書名：賦權圖的三角形覆蓋數與匹配數研究
出版時間：2023-06-29
編 著 者：唐中正
版 次：1-1
I S B N:978-7-5635-6931-1
定 價：￥49.00元
內容簡介
本書研究並部分回答了如下幾個和圖論中的三角形覆蓋數與匹配數緊密相關的問
題：什麼樣的圖結構可以保證三角形覆蓋數不超過兩倍的三角形匹配數成立？什麼樣的
圖結構可以保證三角形覆蓋數等於三角形匹配數成立？在隨機圖模型下，三角形覆蓋數
與三角形匹配數比值的上界可以改進到多好？將三角形覆蓋數推廣到一般的k-圈覆蓋數
與k-團覆蓋數，如何設計有理論保證的近似算法？本書適合運籌學、組合最佳化相關專業
的研究生和科研工作者閱讀，也可作為從事圖論算法的廣大技術人員的參考書。
目錄介紹
第1 章基礎知識. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1 圖論基礎. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 線性規劃基礎. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3 近似算法基礎. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.3.1 最小點覆蓋問題的近似算法. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.3.2 最大割問題的近似算法. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
第2 章研究背景與相關工作. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.1 背景描述. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.2 相關工作. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.3 本書後續章節結構. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
第3 章邊賦權圖中圖薩猜想成立的三個充分條件. . . . . . . . . . . . . . . . . . . . . . . 15
3.1 概況. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .15
3.2 超圖. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .18
3.2.1 反饋集. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3.2.2 賦權超圖. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.2.3 橫貫. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3.3 三角形覆蓋與匹配. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.3.1 三角形超圖. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .37
3.3.2 具有較大三角形匹配數的圖. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .41
3.3.3 具有較大賦權邊數的圖. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
3.4 小結. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .47
第4 章三角形覆蓋的全對偶整數性. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
4.1 概況. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .50
4.2 一般圖上的結論. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
4.3 平面圖上的結論. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
4.4 小結. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .68
第5 章稠密隨機圖中的三角形覆蓋與匹配. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
5.1 概況. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .70
5.2 機率方法. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
5.2.1 機率不等式. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .72
5.2.2 隨機圖模型. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .80
5.3 G(n, p) 模型中三角形覆蓋數與匹配數的關係. . . . . . . . . . . . . . . . . . . . 81
5.4 G(n,m) 模型中三角形覆蓋數與匹配數的關係. . . . . . . . . . . . . . . . . . . 94
5.5 小結. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .100
第6 章邊賦權圖的k-圈覆蓋與k-團覆蓋的近似算法. . . . . . . . . . . . . . . . . . 101
6.1 概況. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .101
6.2 k-圈覆蓋的近似算法. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
6.2.1 基於線性規劃的k-近似算法. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
6.2.2 k 為奇數時的(k-1/2)-近似算法. . . . . . . . . . . . . . . . . . . . . . . .104
6.2.3 k 為偶數時k-圈覆蓋的難解性. . . . . . . . . . . . . . . . . . . . . . . . . . . 106
6.3 k-團覆蓋的近似算法. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
6.3.1 基於線性規劃的(k2-k)/2-近似算法. . . . . . . . . . . . . . . . . . . . 107
6.3.2 改進的(k2-k-1)/2-近似算法. . . . . . . . . . . . . . . . . . . . . . . . . 109
6.3.3 Kn 中的k-團覆蓋與k-團匹配. . . . . . . . . . . . . . . . . . . . . . . . . . . 110
6.4 小結. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .112
第7 章總結. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
參考文獻. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
