基础定义
定义 (邻域).
略。
定义 (导出子图).
略。
定义 (团).
略。
定义 (点割集).
略。
引理.
令 \(G=(V,E)\) 是弦图，\(A\) 是 \(G\) 关于 \(u, v\) 的极小点割集，则 \(A\) 是一个团。
定义 (单纯点).
略。
引理.
所有弦图存在单纯点，非完全图的弦图存在两个不相邻的单纯点。
归纳。任选两个不相邻的点 \(u, v\) 和它们的极小点割集 \(A\)，将剩下的点根据和谁连通分成 \(V_1, V_2\)。那么 \(V_1 \cup A, V_2 \cup A\) 的导出子图都存在两个不相邻的单纯点，且分别都不可能都在 \(A\) 中。
定义 (完美消除序列).
排列 \(p_1, \dots, p_n\) 满足对于任意 \(i\)，\(\{p_i\} \cap \{N(p_i) \cap \{p_{i+1}, \dots, p_n\}\}\) 是一个团。对于给定的排列，将这些团记为 \(C(p_i)\)。
引理.
\(G=(V,E)\) 是弦图当且仅当其存在完美消除序列。
最大势算法.
维护一个集合 \(S\)，初始为空集。
每次将 \(\operatorname{argmax}_{v\notin S} |N(v) \cap S|\) 加入 \(S\)。若有相等的任取一个。
按顶点加入时间从晚到早排序即得一个完美消除序列。
引理.
对于弦图 \(G\) 和任意完美消除序列，\(G\) 的任意极大团都是某个 \(C(p_i)\)。
且以下四个命题等价：
- \(C(p_i)\) 是 \(G\) 的极大团。
- 对于 \(j < i\)，\(C(p_i) \not\subseteq C(p_j)\)。
- 对于 \(j\) 满足 \(p_i\) 是 \(C(p_j) \setminus \{p_i\}\) 中最早出现的，\(C(p_i) \not\subseteq C(p_j)\)。
- 对于 \(j\) 满足 \(p_i\) 是 \(C(p_j) \setminus \{p_i\}\) 中最早出现的，\(|C(p_i)| \ge |C(p_j)|\)。
证明.
- \(1 \Leftrightarrow 2\)：显然。
- \(2 \Leftrightarrow 3\)：\(2 \to 3\) 显然，\(3 \to 2\) 考虑若不满足条件，则最大的不满足条件的 \(j\) 一定满足 \(p_i = \min C(p_j) \setminus \{p_j\}\)。
- \(3 \Leftrightarrow 4\)：易见 \(C(p_i) \supseteq C(p_j) \setminus \{p_j\}\)，于是显然。
最小点染色
构造.
按照完美消除序列倒序枚举，每次染上最小的颜色使得相邻不存在同色。
那么所用颜色 \(\ge\) 最小色数，且 \(\le\) 最大团，因为用 \(\max |N(v)|+1\) 种颜色一定能完成染色，且最小色数 \(\ge\) 最大团。
因此弦图最小色数等于最大团大小。
最大独立集与最小团覆盖
构造 (最大独立集).
沿着完美消除序列的顺序能选就选。
构造 (最小团覆盖).
取上述贪心中得到的最大独立集 \(I\)，\(\{C(v) \mid v \in I\}\) 即为所求。
而最大独立集 \(\le\) 最小团覆盖，因此它们都是最优的。
团树
定义.
一张图 \(G=(V,E)\) 的团树是一棵树 \(T\)，满足存在 \(G\) 的所有极大团到 \(T\) 的顶点的双射，且对于 \(v \in V\)，包含 \(v\) 的所有极大团在 \(T\) 中对应的顶点构成一个连通子图。
引理.
一张图是弦图当且仅当它有团树。
证明.
右推左：根据下文，子树图是弦图。
左推右：接下来给出一种构造算法。
构造.
按照完美消除序列倒序枚举。现在加入 \(p_i\)，如果 \(p_i = \{p_i\}\) 那么直接连向树上任意点，否则设 \(p_j\) 是 \(C(p_i) \setminus \{p_i\}\) 中最早出现的点，则 \(C(p_i) \setminus \{p_i\} \subseteq C(p_j)\)。如果 \(C(p_i) \setminus \{p_i\} = C(p_j)\) 且 \(p_j\) 所在的点恰好为 \(C(p_j)\)，则将 \(p_i\) 加入 \(p_j\) 所在的点，否则新建一个点连向 \(p_j\) 所在的点。
区间图
给定若干区间，每个区间对应一个点，若相交则连边，即得一张区间图。
容易证明区间图是弦图。而它的团树显然是一条链。
完美消除序列：按右端点升序。或者对称地，按左端点降序。
子树图
给定一棵树和一些树上连通块，每个连通块对应一个点，若相交则连边，即得一张子树图。
容易证明子树图也是弦图。
完美消除序列：按连通块的最浅点从深到浅排序。
应用
例题 1
简要题意.
给定字符串每个位置的回文半径，计数字符串个数。
其是弦图。手玩 Manacher 过程可得。
例题 2
简要题意.
给定 KMP 的 \(next\) 数组，计数字符串个数。
考虑一棵树，\(i\) 连向 \(next_{i-1}+1\)（注意不是 \(next_i\)）。那么对于所有祖先后代，要么是必须相等，要么是必须不相等。
因此对于所有相等的极大连通块，以最浅点作为代表元，那么不等当且仅当有祖先后代关系，这相当于以代表元为根的子树的相交图。
例题 3
简要题意.
以区间的形式给定一张区间图 \(G=(V, E)\)，求最大的点集 \(S \subseteq V\) 使得 \(S\) 在 \(G\) 的导出子图中不存在 \(m\) 元团。
Source: Ural 1424.
按照右端点升序贪心取。但严重依赖区间图的性质，比较难以推广。
例题 4
简要题意.
给定一棵树和 \(m, k\)，将树上的点 \(m\) 染色满足同色的点的距离 \(\ge k\)，求方案数。
Source: QOJ 7772 (加强版, 原版不知道在哪).
显然可以转化成每个点的 \(\frac k2\) 邻域的相交图（如果在边上可以拆点），因此这是子树图，因此是弦图。完美消除序列即按照最浅点深度降序，当然也可以按照每个邻域的中心深度降序。
例题 5
简要题意.
给定一棵树和 \(k\)，新建一个图是每个点的 \(\frac k2\) 邻域的相交图，每个点的编号是中心在树上的编号，\(q\) 次询问给定区间在新图上的导出子图的连通块个数。
Source: Luogu P7126.
我们考虑建出一个团树，随意定一个根，用它来分析连通块性质。显然，任意连通子图在团树上都对应一个连通块。我们考虑固定点集之后统计每个连通块在团树上的最浅点，于是可以想到把所有点按照在团树上的最浅点的深度排序，这样一个点是最浅点当且仅当它和前面的点没有连边。
不过事实上对于这个题我们不需要再建出一个团树来，直接取原树的 BFS 序即可。
然后就是树分治和二维数点的问题了。
例题 6
简要题意.
给定一棵树和 \(m\) 个点对 \((x_i, y_i)\)，定义 \(S(x, y)\) 为所有点 \(z\) 满足 \(z\) 与 \(x \rightsquigarrow y\) 路径上最近的点不是 \(x\) 也不是 \(y\) 的集合。
选择最少的点 \(z_j\) 满足每个 \((x_i, y_i)\) 都满足存在某个 \(z_j \in S(x_i, y_i)\)。
Source: CF1610H.
考虑对偶，问题变为选择最多的点对 \((x_i, y_i)\) 满足任意 \(z\) 都至多存在一组 \((x_i, y_i)\) 满足 \(z \in (x_i, y_i)\)。
相当于是 \(S(x_i, y_i)\) 的最大独立集，而 \(S(x_i, y_i)\) 是树上连通块，因此按照弦图方法贪心即可。
例题 7
简要题意.
给定一棵树和若干树上连通块（以一些点的虚树的形式给出），判定这些连通块的相交图是否是单极性的（所有极大团缩点之后得到一棵菊花和一些孤立点）。
Source: DMOPC '23 Contest 1 P6.
也就是说，存在一棵菊花和一些孤立点任意链接之后得到这张图的团树。
那么我们不妨直接尝试构建一棵团树，出现两个相交的极大团之后直接尝试判断分别删掉这两个团之后图是否合法即可。判断合法也可以用构造团树的方法来做。
例题 8
简要题意.
以区间的形式给定一张区间图 \(G=(V, E)\)，求最大匹配。
按右端点升序贪心，若一个区间和前缀中某个未匹配的区间相交，则取右端点最小的区间与其匹配。不需要反悔。
同样比较依赖区间图的性质，但是好像可以做一些简单的推广。
例题 9
简要题意.
给定一棵有根树和若干祖先后代链，求它们的相交图的最大匹配。
按最浅点深度降序贪心，取可以匹配的最深的匹配即可。
例题 10
简要题意.
给定弦图 \(G=(V, E)\)，Alice 和 Bob 将在 \(G\) 上博弈。
第一轮，Alice 选择不超过 \(k\) 个点，设选中的点集为 \(A_1\)，然后 Bob 选择 \(V \setminus A_1\) 中的一个点，设其为 \(v_1\)。
第 \(i\) \((i>1)\) 轮，Alice 选择不超过 \(k\) 个点，设选中的点集为 \(A_i\)，然后 Bob 选择 \(V \setminus A_i\) 中的一个点，设其为 \(v_i\)。Bob 需要满足 \(v_{i-1}\) 和 \(v_i\) 之间存在一条不经过 \(A_{i-1} \cap A_i\) 内的点的路径。
如果某一轮 Bob 无法选择 \(v_i\)，则 Alice 获胜。如果游戏能无限进行下去，则 Bob 获胜。
求出最小的 \(k\)，使得 Alice 能获胜。
如果 \(k\) 小于最大团，那么 Bob 总是可以在最大团里选一个点，于是 Alice 无法获胜。
如果 \(k\) 大于等于最大团，建出团树，Alice 先随意选择一个极大团 \(A_1\)，然后 Bob 选择的点 \(v_1\) 会在团树上对应一个不包含 \(A_1\) 的连通块。Alice 一直往这个连通块的方向选儿子就能获胜。
因此最小的 \(k\) 就是最大团大小。
例题 11
简要题意.
给定弦图 \(G=(V, E)\)，求至少删掉多少个点，才能让 \(G\) 中不存在环。
建出团树，问题等价于选择最多的原图点，使得每个极大团被覆盖的次数不超过 \(2\) 次。
大力 DP \(f(u, i, j)\) 状态数是 \(O(m\sqrt m)\) 的。