本书研究并部分回答了如下几个和图论中的三角形覆盖数与匹配数紧密相关的问
题：什么样的图结构可以保证三角形覆盖数不超过两倍的三角形匹配数成立？什么样的
图结构可以保证三角形覆盖数等于三角形匹配数成立？在随机图模型下，三角形覆盖数
与三角形匹配数比值的上界可以改进到多好？将三角形覆盖数推广到一般的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