弦图

符号与约定

下文默认图是连通的。

• 子图：点集与边集都是原图点集与边集的子集的图。
• 导出子图：一个点集的导出子图是该点集与所有两个端点均在该点集内的边构成的边集构成的子图。
• 团：完全子图。
• 极大团：不是其他团的子图的团。
• 最大团：点数最大的团。
• 团数：最大团的点数。
• 最小染色：使用最少的颜色给点染色使得任意一条边的两个端点颜色不同。
• 色数：最小染色的颜色数。
• 最大独立集：最大的点集使得其中任意两个点之间没有边。
• 最小团覆盖：用最少的团覆盖所有点。
• 弦：连接环上两个不相邻的点的边。
• 弦图：任意一个大小大于 $3$ 的环都有一个弦的图。

弦图的性质

性质 1：团数小于等于色数。

考虑对最大团染色至少需要团数种颜色。

性质 2：最大独立集小于等于最小团覆盖。

每个团中至多选择一个点。

以上两个性质在普通图上也存在。

性质 3：弦图的导出子图一定是弦图。

考虑到若导出子图上存在无弦环，其在原图上也存在。

点割集

我们称弦图上任意两点 $u, v$ 的点割集是满足删去其中的点后 $u, v$ 不连通的集合。

引理 1：弦图上任意两点 $u, v$ 的极小点割集的导出子图一定是团。

设割掉极小点割集后 $u$ 所在连通块为 $A$，$v$ 所在连通块为 $B$，则极小点割集中的任意一个点一定与 $A, B$ 均有边，否则我们可以将这个点删去。
对于极小点割集中的任意两点 $a, b$，设它们与 $A, B$ 相连的点为 $a _ 1, a _ 2, b _ 1, b _ 2$。显然 $a _ 1, b _ 1$ 之间存在路径只经过 $A$ 中的点，$a _ 2, b _ 2$ 之间存在路径只经过 $B$ 中的点。那么考虑 $a \to a _ 1 \sim b _ 1 \to b \to b _ 2 \sim a _ 2 \to a$ 这个环，他的弦只能是 $(a, b)$。（$x \sim y$ 表示点 $x$ 到点 $y$ 的最短路，且只经过 $A$ 或 $B$ 中的边。）
由此可得极小点割集的导出子图一定是团。

单纯点

单纯点 是与其相邻的点加上其本身构成的点集的导出子图是团的点。

引理 2：非完全图的弦图一定有至少两个不相邻单纯点。

考虑归纳证明。对于点数等于 $3$ 时结论显然成立。
当点数大于 $3$ 时，找到两个不相邻的点 $u, v$ 和它们的任意一个极小点割集 $I$，若 $A + I$ 是完全图，则 $u$ 是单纯点。$B + I$ 同理。
否则，$A + I$ 也是弦图，可以找到两个不相邻的单纯点，必然有一个在 $A$ 中，该点在原图中也是单纯点。$B + I$ 同理。
于是我们在 $A$ 和 $B$ 中分别找到了两个单纯点，显然它们不相邻。

完美消除序列

定义一个弦图的完美消除序列 $p _ {1 \ldots n}$ 是一个排列，满足对于任意 $i$，$p _ i$ 是 $\{p _ i, p _ {i + 1}, \ldots, p _ n\}$ 的导出子图的单纯点。

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

必要性：每次选出单纯点删掉即可构造。
充分性：对于每个环，我们取出其在完美消除序列上第一次出现的点，显然环上与之相邻的点之间必然有边。所以每个环都有一条弦。

MCS 最大势算法

用于求解弦图的完美消除序列。

过程：

1. 设 $l _ i$ 为与点 $i$ 相邻的已标号点的数量。
2. 找到一个 $l _ i$ 最大的未标号的点 $i$。
3. 将 $i$ 标号然后更新 $l$。
4. 重复上述过程直到所有点都被标号。
5. 将标号顺序 reverse 后即可得到一个完美消除序列。

时间复杂度为 $O(|V| + |E|)$。

参考代码如下：

for (int i = 1; i <= n; i++) pos[i] = vec[0].size(), vec[0].push_back(i);
for (int i = 1, j = 0; i <= n; i++, j++) {
	while (vec[j].empty()) j--;
	int u = p[i] = vec[j].back();
	vec[j].pop_back();
	pos[u] = -1;
	for (int k = g.hd[u]; k; k = g.nxt[k])
		if (pos[g.to[k]] != -1) {
			int v = g.to[k];
			pos[vec[l[v]].back()] = pos[v];
			swap(vec[l[v]][pos[v]], vec[l[v]].back());
			vec[l[v]].pop_back();
			pos[v] = vec[++l[v]].size();
			vec[l[v]].push_back(v);
		}
}
reverse(p + 1, p + n + 1);

考虑如何证明对于任意一个弦图，MCS 算法一定能求出来完美消除序列。

这里应该有一个证明，但是我咕了。

应用

判断图是否是弦图

首先用 MCS 算法求出一个序列，然后判断它是否是完美消除序列，若是则图是弦图，否则不是弦图。

具体地，对于每个 $p _ i$，找到与之相连且在它之后出现的点，按出现顺序记为 $c _ 1, c _ 2, \ldots, c _ k$，我们只需要判断 $c _ 1$ 与 $c _ j$ 之间是否有边即可。因为这个团中其他边会在 $p _ {c _ 2}, p _ {c _ 3}, \ldots, p _ {c _ k}$ 中被判断。

求弦图的团数与色数

求团数：
设 $N(x)$ 为完美消除序列中在 $x$ 之后且与 $x$ 相连的点的集合，则弦图的最大团一定可以被表示为 $\{x\} + N(x)$，则 $|\{x\} + N(x)|$ 的最大值就是弦图的团数。

求色数：
考虑按完美消除序列从后往前考虑，贪心染 $\operatorname{mex}$，这样需要的颜色数量等于团数。
由于团数小于等于色数，这样取到等号，一定最小。

求弦图的最大独立集和最小团覆盖

最大独立集：
按完美消除序列从前往后贪心。
正确性证明：每次考虑最靠前的极大团，选最前面的点不劣于选其他点，且优于不选点。

最小团覆盖：
取最大独立集中的每个点 $x$ 对应的团 $\{x\} + N(x)$，这样需要的团的数量等于最大独立集的大小。
由于最大独立集小于等于最小团覆盖，这样取到等号，一定最小。

区间图

对于任意 $n$ 个区间，我们将每个区间看作一个点，两个点之间有边当且仅当这两个区间有交，这样构造出来的图称为区间图。

显然区间图一定是弦图，且其中一个完美消除序列是按区间右端点从小到大排序。

使用这个性质可以证明很多贪心的正确性。