1 Star 0 Fork 0

harrytsz/ACM

加入 Gitee
与超过 1200万 开发者一起发现、参与优秀开源项目,私有仓库也完全免费 :)
免费加入
该仓库未声明开源许可证文件(LICENSE),使用请关注具体项目描述及其代码上游依赖。
克隆/下载
弦图.txt 1.14 KB
一键复制 编辑 原始数据 按行查看 历史
tiankonguse 提交于 2014-11-10 17:14 . update
弦图的定义
任意size>3的环都存在弦。弦即环上不相邻两点之间的边。
完美消除序列
v_i和v_{i+1}, ... , v_n构成的诱导子图里,把和v_i相连的点拿出来,会成为一个团。
完美消除序列的求法
令d_i = 0,然后每次选取d值最大的一个点拿出来放进序列头,再枚举该点的出边,把他们的d值加1。如此反复。
完美消除序列的性质
按序列从后往前染色可得图的色数。在弦图里,色数等于最大团的size
按序列从前往后贪心取可得最大独立集。在弦图里,最大独立集额等于最小团覆盖
按上面最大势方法求出这个序列顺序以后,如果想知道该图是不是弦图,那么枚举每个点v_i,假设他在v_{i+1}, ..., v_n里有边直接相连的点集为S = {x_1, x_2, ... , x_m}然后只需判定x_1是不是和x_2, x_3, ... , x_m都有边就可以了
完美图的定义
所有诱导子图满足色数等于最大团size的图
伴完美图的定义
所有诱导子图满足最大独立集等于最小团覆盖的图
区间图总是弦图
并且按r排序就是他的完美消除序列
马建仓 AI 助手
尝试更多
代码解读
代码找茬
代码优化
1
https://gitee.com/harrytsz/ACM.git
git@gitee.com:harrytsz/ACM.git
harrytsz
ACM
ACM
master

搜索帮助