赋权图的三角形覆盖数与匹配数研究

第1章基础知识 1.1图论基础 1.2线规划基础 1.3近似算法基础 1.3.1小点覆盖问题的近似算法 1.3.2大割问题的近似算法 第2章研究背景与相关工作 2.1背景描述 2.2相关工作 2.3本书后续章节结构 第3章边赋权图中图萨猜想成立的三个充分条件 3.1概况 3.2超图 3.2.1反馈集 3.2.2赋权超图. 3.2.3 横贯 3.3三角形覆盖与匹配 3.3.1三角形超图. 3.3.2具有较大三角形匹配数的图 3.3.3具有较大赋权边数的图 3.4小结 第4章 三角形覆盖的全对偶整数 4.1概况 4.2一般图上的结论 4.3平面图上的结论 4.4小结 第 5 章 稠密图中的三角形覆盖与匹配 5.1概况 5.2概率方法 5.2.1概率不等式 5.2.2图模型 5.3C(n，p)模型中三角形覆盖数与匹配数的关系 5.4g(n,m)模型中三角形覆盖数与匹配数的关系 5.5小结 第6章 边赋权图的k-圈覆盖与k-团覆盖的近似算法 6.1概况 6.2 k-圈覆盖的近似算法 6.2.1基于线规划的k-近似算法 6.2.2k为奇数时的（k-1/2）-近似算法. 6.2.3k为偶数时k-圈覆盖的难解 6.3 k-团覆盖的近似算法 6.3.1 基于线规划的（k2-k）/2-近似算法 6.3.2的（k2-k-1）/2-近似算法 6.3.3Kn中的k-团覆盖与k-团匹配 6.4小结 第7结 参考文献