大家好,又见面了,我是你们的朋友全栈君。
弦图与区间图
参考资料:陈丹琦《弦图与区间图》
-
预备知识
图定义为\(G=(V,E)\),其中\(V\)为点集,\(E\)为边集。
子图定义为对于原图\(G=(V,E)\)的子图\(G’=(V’,E’),V’\in V,E’\in E\)。
对于原图\(G=(V,E)\),诱导子图\(G’=(V’,E’),V’\subseteq V,E’=\{(u,v)|u,v\in V,(u,v)\in E\}\)
团定义为原图的一个子图为完全图称为团。极大团定义为一个团不为另一个团的子集。最大团为点数最多的团。\(\omega(G)\)表示团数。
最小染色为用最小的颜色给点染色使相邻的点的颜色不同。\(\chi(G)\)表示色数。
最大独立集为最大的一个点的子集使任何两个点不相邻。\(\alpha(G)\)为最大独立集的点数。
最小团覆盖为用最少的团覆盖所有的点,\(\kappa(G)\)为用的最少的团数。
\(\omega(G)\le \chi(G)\),团数\(\le\)色数;\(\alpha(G)\le\kappa(G)\),最大独立集数\(\le\)最小团覆盖数。
-
弦图
弦定义为一个环中连接不相邻的点的边。
一个图被称为弦图当图中所有长度大于3的环至少有一个弦。
弦图的每一个诱导子图都是弦图。
-
弦图的判定
单纯点:设\(N(v)\)表示与点\(v\)相邻的点集。一个点被称为单纯点当\(\{v\}+N(v)\)的诱导子图为一个团。
任何一个弦图都至少有一个单纯点,不是完全图的弦图至少有两个不相邻的单纯点。
完美消除序列:一个点的序列\(v_1,v_2,\dots,v_n\)满足\(v_i\)在\(\{v_i,v_{i+1},\dots,v_n\}\)的诱导子图中为一个单纯点。一个图为弦图当且仅当存在一个完美消除序列,证明可详见论文。
-
求完美消除序列
求完美消除序列在论文中有很多方法,在这里介绍最简单的一种。
MCS算法:最大势算法。从n到1给节点编号,设\(label[i]\)为表示第\(i\)个点与多少个已标号点相邻,每次选择\(label[i]\)最大的未编号点进行编号。时间复杂度为\(O(n+m)\)
判断一个序列是否是完美消除序列:设\(\{\}\)
转载于:https://www.cnblogs.com/shanxieng/p/9899141.html
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/107215.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...