这就是生活 弦图判定

lovelifes · November 10, 2019 · 23 hits

弦:连接环中不相邻的两个点的边。

弦图:一个无向图称为弦图当图中任意长度大于 3 的环都至少有一个弦。

团:满足 G 为关于 V 的完全图的图。

单纯点:设 N(v) 表示与点 v 相邻的点集。一个点称为单纯点当{v} + N(v) 的诱导子图为一个团。

完美消除序列:一个点的序列 (每个点出现且恰好出现一次) v1, v2, …, vn 满足 vi
在{vi, vi+1,…,vn}的诱导子图中为一个单纯点。

弦图充要条件:一个无向图是弦图当且仅当它有一个完美消除序列。


MCS 算法:从 n 到 1 依次给点标号,设 label[i] 表示第 i 个点与多少个已标号的点相邻,每次选择 label[i] 最大的未标号的点进行标号。

判断序列是否为完美消除序列:设{v[i+1],……,v[n]}中所有与 v[i] 相邻的点依次为
{v[j1],v[j2],……,v[jk]},只需要判断 v[j1] 是否与{v[j2],……,v[jk]}相邻即可。

时间复杂度:O(n+m)

No Reply at the moment.
You need to Sign in before reply, if you don't have an account, please Sign up first.