作者：唐中正，刁卓著
页数：121页
出版社：北京邮电大学出版社
出版日期：2023
ISBN：9787563569311
电子书格式：pdf/epub/txt
内容简介
本书研究并部分回答了如下几个与图论中的三角形覆盖数与匹配数紧密相关的问题：什么样的图结构可以保证三角形覆盖数不超过两倍的三角形匹配数成立？什么样的图结构可以保证三角形覆盖数等于三角形匹配数成立？在随机图模型下，三角形覆盖数与三角形匹配数比值的上界可以改进到多好？将三角形覆盖数推广到一般的k-圈覆盖数与k-团覆盖数，如何设计有理论保证的近似算法？
作者简介
唐中正，男，中国科学技术大学学士，中国科学院数学与系统科学研究院博士，香港城市大学联培博士，现为北京邮电大学理学院数学系讲师，研究方向为组合优化、图论、近似算法等。
目录
第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结
参考文献
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结
参考文献
