Chordal Graph

前言

没想到自己退役之前居然点开了弦图的知识树……
我肯定不会告诉你是因为做 CC 的 JERRYTOM 才学这个东西的。
也就学到最大团为止了,后面的最大独立集什么好像也不难但是懒得写了……
(2018.07.14)
结果中途咕咕咕,凉完了 NOI,颓完了 CodeM Final,明天就要开学的我才强迫自己把坑填完。
(2018.07.30)


一些约定

$G$ 一副无向图。
$G[S]$:$S$ 点集的诱导子图。
$\delta(S)$:$S$ 点集的邻集。


弦图的基本性质

定义

环中连接两个非环上相邻点的边。

弦图

任意长度大于 $3$ 的环都有至少一条弦的无向图。

一个很显然的性质

弦图的任意一个诱导子图一定是弦图。

$xy$ - 点割

对于一对非相邻节点 $x$ 和 $y$,如果删掉点集 $S$ 能使得 $x$ 与 $y$ 在 $G-S$ 中不连通,那么 $S$ 是一个 $xy$ - 点割。

基本性质

定理 $1$

内容

$G$ 是弦图当且仅当对于所有的极小 $xy$ - 点割 $S$,$G[S]$ 都是一个团。

证明

先证明必要性,假设 $G$ 是一个弦图,且其存在一个极小 $xy$ - 点割 $S$,$G[S]$ 并不是一个团。
考虑 $S$ 上两个非相邻节点 $u$ 和 $v$,由于 $S$ 是极小的 $xy$ - 点割,因此 $u$ 和 $v$ 一定都同时连接了至少一个 $x$ 集合的点和一个 $y$ 集合的点。
容易发现此时至少存在一个同时包含 $u$ 和 $v$ 的大小至少为 $4$ 的无弦环,矛盾。
再证明充分性,假设 $G$ 满足所有的极小 $xy$ - 点割 $S$ 的诱导子图都是一个团,但是 $G$ 不是弦图,也就是说 $G$ 至少存在一个大小为 $4$ 的无弦环。
考虑这个无弦环上两个非相邻节点 $u$ 和 $v$,它们的极小 $xy$ - 点割 $S$ 的诱导子图是一个团,显然要使这两个点不连通,$S$ 在它们环上两个方向的简单路径上都至少得有 $1$ 个点。由于 $S$ 是一个团,这两个点有连边,和环无弦矛盾。

定理 $2$

内容

令 $G$ 是一个非团弦图。假定 $S$ 是一个 $xy$ - 点割且 $G[S]$ 是一个团,令 $G_1,…,G_k$ 表示 $G-S$ 中的连通块。那么对于每一个连通块 $G_i$ 我们都可以选择出一个点 $x\in G_i$ 使得 $G[\delta(x)]$ 是一个团。

证明

考虑对 $|G|$ 使用数学归纳法,首先 $|G|=3$ 的时候显然成立。
令 $V_1,…,V_k$ 表示 $G_1,…,G_k$ 中的点集。由弦图的性质,$G[V_i\bigcup S]$ 都是弦图。
由于 $S$ 是一个点割,也就是说对于所有 $v_i\in V_i$,$\delta(v_i) \subseteq V_i\bigcup S$。因此在 $G[V_i\bigcup S]$ 中,$G[\delta(v_i)]$ 如果是一个团,那么在 $G$ 中 $G[\delta(v_i)]$ 也是一个团。
如果 $G[V_i\bigcup S]$ 本身是一个团,那对于所有 $v_i\in V_i$,$G[\delta(v_i)]$ 都是一个团。
如果 $G[V_i\bigcup S]$ 本身不是一个团,那么考虑 $G[V_i\bigcup S]$ 中的一对非相邻节点 $u,v$,由定理 $1$,它们的极小 $xy$ - 点割 $S_i$ 是一个团,根据归纳,一定可以找到两个点 $a,b\in (V_i\bigcup S)\S_i$ ,使得在 $G[V_i\bigcup S]$ 中,$G[\delta(a)]$ 和 $G[\delta(b)]$ 都是团。
由于 $a,b$ 在点割 $S_i$ 的不同连通块,因此其中至少存在一个是属于 $V_i$ 的,假设其为 $a$,那么 $a$ 就是我们要找的 $v_i$。


弦图的完美消除序列

定义

单纯点

一个点是单纯点当且仅当 $G[\delta(v)]$(或者 $G[{v}+\delta(v)]$)的诱导子图是一个团。

完美消除序列

完美消除序列是一个序列 ${v_1,v_2,…,v_n}$,图中每个点恰好出现一次,满足 $v_i$ 在 ${v_{i+1},v_{i+2},…,v_n}$ 的诱导子图中是单纯点。

弦图完美消除序列的性质

引理 $3$

内容

弦图 $G$ 至少存在一个单纯点。

证明

如果 $G$ 本身就是团,那么其每一个节点都是单纯点。
否则,考虑两个非相邻节点 $u$ 和 $v$,根据定理 $1$ 其极小 $xy$ - 点割 $S$ 的诱导子图一定是一个团,根据定理 $2$ 一定存在单纯点。

定理 $4$

内容

一个图是弦图当且仅当它有一个完美消除序列。

证明

先证明必要性,每次选出一个单纯点然后删掉它,诱导子图也是弦图,因此依然有单纯点。这样可以构造出弦图的完美消除序列。
再证明充分性,假设一个图不是弦图且存在完美消除序列,也就是说它存在一个长度大于 $3$ 的无弦环。那么假设这个环最早出现在消除序列中的点是 $v$,取其相邻节点 $v_1,v_2$,根据消除序列的定义 $(v_1,v_2)\in E$,和环无弦矛盾。

最大势算法(Maximum Cardinality Search, MCS)

流程

每个点有一个初始势能 $card(x)=0$。
从 $n$ 到 $1$ 确定完美消除序列的每一个元素,每次选择 $card(x)$ 最大的将其填入,并将其邻集中没有被选择的 $card$ 增加 $1$。
实现可以直接开 $n$ 个队列记录每种势能有哪些点,记录 $best$ 表示当前最大势能。节点势能增加移动至另一个队列的时候不需要删除原本的。
简单势能分析一下,复杂度是 $O(n+m)$ 的。

定义

$\alpha(x)$

$x$ 在(通过 MCS 得到的)完美消除序列中的排名。

正确性证明

引理 $5$

内容

对于点对 $u,v$ 满足 $\alpha(u)<\alpha(v)$,如果存在点 $x$ 使得 $(u,x)\in E,(v,x)\not\in E$ 且 $\alpha(x)>\alpha(v)$。那么一定存在点 $y$ 使得 $(v,y)\in E,(v,x)\not\in E$ 且 $\alpha(y)>\alpha(v)$。

证明

若不成立则有 $\alpha(u)>\alpha(v)$,矛盾。

引理 $6$

内容

假定有 $\alpha(x)<\alpha(u)<\alpha(v)$,如果 $u$ 和 $v$ 没有边,$x$ 和 $v$ 都有连边。那么一定存在一条 $u$ 到 $v$ 的只经过 $\alpha$ 值大于 $\alpha(u)$ 的简单路径。

证明

考虑节点 $u$,由于 $u$ 和 $v$ 不相邻,且 $x$ 连接了 $v$,使用引理 $5$ 可以得到一定存在一个 $u’$ 满足 $(u,u’)\in E,(x,u’)\not\in E$ 且 $\alpha(u’)>\alpha(u)$。
分类讨论,如果 $\alpha(u’)<\alpha(v)$,我们继续对 $x,u’,v$ 进行递归论证;否则我们继续对 $u,v,u’$ 进行递归论证。
递归的条件是 $3$ 个点的 $\alpha$ 值依次递增,第 $2$ 个点和第 $3$ 个点没有边,第 $1$ 个点和第 $3$ 个点有边。
只有第二个条件可能会不满足,这也意味着证明结束:此时就得到了一条只经过 $\alpha$ 值大于 $\alpha(u)$ 的点连接 $u$ 和 $v$ 的简单路径。注意到递归过程中三个点的 $\alpha$ 值至少有一个增大了,因此有限步内一定可以递归到边界。

定理 $7$

内容

在弦图上运行 MCS 算法可以得到弦图的一个完美消除序列。

证明

只需证明在弦图上运行 MCS 算法,选择点 $x$ 的时候,$x$ 在 $x$ 与已经被标记的点的诱导子图中是单纯点。
如果 $x$ 不是单纯点,那么 $x$ 一定和两个不相邻的已标记点 $u$ 和 $v$ 相连。
不妨令 $\alpha(x)<\alpha(u)<\alpha(v)$,由引理 $6$,存在一条只经过已标记点连接 $u$ 和 $v$ 的简单路径。
此时一定存在一个长度大于 $3$ 的无弦环,矛盾。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
void MCS()
{
int best=0;
for (int x=1;x<=n;++x) link[card[x]=0].push(x),vis[x]=0;
for (int j=n,p;j>=1;--j)
{
for (p=0,++best;!p;)
{
--best;
for (int x;!link[best].empty();)
{
x=link[best].front(),link[best].pop();
if (!vis[x])
{
vis[x]=1;
for (int i=last[x],y;i;i=nxt[i])
if (!vis[y=tov[i]])
link[++card[y]].push(y),best=max(best,card[y]);
p=x;
break;
}
}
}
seq[rk[p]=j]=p;
}
for (;best;--best) for (;!link[best].empty();link[best].pop());
}

弦图的判定

对给定的图 $G$ 运行 MCS 算法,判定的到的序列是否是一个完美消除序列。
朴素的方法是 $O(n^3)$ 的。
利用完美消除序列的性质,我们只需要倒过来枚举每一个元素 $x$,假定与其相连的且 $\alpha$ 值比其大的点按 $\alpha$ 排序依次是 $p_1,p_2,…,p_k$,那么只需要判定 $p_1$ 是否与其它点直接相连即可。时间复杂度 $O(n+m)$。


弦图的其它问题

定义

$N(v)$

$N(v)=\{w|w\in\delta(v),\alpha(v)<\alpha(w)\}$。

最大团/极大团

定理 $8$

内容

弦图的极大团一定是 $G[v\bigcup N(v)]$ 的形式。

证明

首先 $G[v\bigcup N(v)]$ 一定是一个团。
假设点集 $V$ 的诱导子图是一个极大团。令 $v$ 是其中 $\alpha$ 最小的点,那么 $V \subseteq G[v\bigcup N(v)]$。又由于 $V$ 是极大团,那么 $V=G[v\bigcup N(v)]$。

推论 $9$

弦图的最多有 $n$ 个极大团。

判定 $G[v\bigcup N(v)]$ 是否是一个极大团

如果存在 $w$ 使得 $v\bigcup N(v)\subset w\bigcup N(w)$ 则 $G[v\bigcup N(v)]$ 并不是一个极大团。

令 $next(v)$ 表示 $N(v)$ 中 $\alpha$ 最小的节点。如果 $G[v\bigcup N(v)]$ 不是极大团,令 $w^{*}$ 是所有满足 $v\bigcup N(v)\subset w\bigcup N(w)$ 的 $\alpha$ 最大的 $w$。
那么一定有 $next(w^{*})=v$,否则 $next(w^{*})$ 是满足条件的 $\alpha$ 更大的 $w$($next(w^{*})\in G[w\bigcup N(w)]$,因此 $v\bigcup N(v)$ 的每一个节点都和 $next(w^{*})$ 有连边)。

也就是说我们只需要判断 $next(w)=v$ 的点 $w$。
由于 $w\bigcup N(w)$ 是一个团,且 $v\in w\bigcup N(w)$,且 $next(w)=v$,因此 $(N(w)\backslash w)\subseteq N(v)$。
所以 $v\bigcup N(v)\subset w\bigcup N(w)$ 当且仅当 $|N(v)|+1\leq|N(w)|$。
按照本人的理解这里可以写作 $|N(v)|+1=|N(w)|$,但是大家写的好像都是 $\leq$,如果我理解有误欢迎读者指正。

最小染色

小坑待填。

最大独立集

小坑待填。

最小团覆盖

小坑待填。