代码拉取完成,页面将自动刷新
弦图的定义
任意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排序就是他的完美消除序列
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。