0.前言
由于机房巨神都学了这玩意，以前也没接触过这些科技，于是决定拿出一晚上搞（颓）一搞（颓）。
基本上是照着 OI Wiki 学的，有的证明会比较感性甚至懒得证。
1.图论基础
一些简单的定义不放了，可以参照《组合数学》（冯荣权，宋春伟）第七章图论。
定理 $1.0$ 设最小团覆盖数为 $\kappa(G)$，则 $\alpha(G)\le\kappa(G)$。
定理 $1.1$ 弦图的导出子图为弦图。
证明：若非弦图，则原图中有多于三元环，矛盾。$\Box$
定义 $1.2$ 将 $u,v$ 间割点的集合称为点割集。
引理 $1.3$ 设删去极小点割集 $I$ 后包含 $u,v$ 的连通块为 $G_u,G_v$，则 $\forall x\in I,N(x)\cap G_u\ne\varnothing,N(x)\cap G_v\ne\varnothing$。
证明：反证即得。$\Box$
定理 $1.4$ 弦图中任两点间极小点割集的导出子图为团。
证明：数学归纳法。设极小点割集为 $I$，则 $|I|=1$ 时成立。
若 $|I|>1$，设 $u,v\in I$，由引理 $1.3$ 易知，存在 $u_1,u_2\in N(u),v_1,v_2\in N(v)$ 满足 $u_1,v_1\in G_u,u_2,v_2\in G_v$。
令 $u\sim v$ 为 $u,v$ 之间最短路径，则此时显然存在多于四元环 $u-u_1\sim v_1-v-v_2\sim u_2-u$，由于原图为弦图，所以环上必有至少一条弦。
而显然这条弦只能连接 $u,v$，于是定理得证。$\Box$
定义 $1.5$ 若 ${x}+N(x)$ 的导出子图为团，则称 $x$ 为单纯点。
引理 $1.6$ 弦图至少有一个单纯点，不是完全图的弦图至少有两个不相邻单纯点。
证明：数学归纳法。显然点数 $\le3$ 时成立。
设点数 $<n$ 时成立，当前图（非完全图）有 $n$ 个点，设 $I$ 为 $u,v$ 间极小点割集，若 $G_u+I$ 为完全图，则 $u$ 即为单纯点；否则，$G_u+I$ 为弦图，必存在两个不相邻单纯点。由于 $I$ 的导出子图为团，所以 $G_u$ 中必存在一个单纯点。于是定理得证。$\Box$
定义 $1.7$ 一个图的完美消除序列（PEO）定义为 $1\sim n$ 的一个排列 $v_1,\dots,v_n$，满足任意 $v_i$ 在 ${v_i,\dots,v_n}$ 的导出子图中为单纯点。
定理 $1.8$ 弦图 $\Leftrightarrow$ 存在 PEO。
证明：由引理 $1.6$ 易证充分性，由反证法易证必要性。$\Box$
2.弦图的判定
先来看如何求 PEO，暴力求显然不行，于是就有了最大势算法（Maximum Cardinality Search）。
算法流程是这样的：倒序给点标号，设 $c_x$ 为 $N(x)$ 中已标号的点数，则每次标 $c$ 最大的点。
正确性证明先咕着，想起来了再补。
MCS 算法只是求出了一个序列，如果我们不知道原图是否为弦图，那么就需要判断一下。
判断方法很简单，只需判断 $v_i$ 在 ${v_i,\dots,v_n}$ 中相邻点中最小点是否与其他点连通即可。
那么，我们用 $O(n+m)$ 的复杂度解决了弦图判定问题。
3.弦图的美妙性质
3.1 最大独立集/最小团覆盖
[链接登录后可见]
PEO 上从前往后依次选择即可。
正确性：设通过这种方式选出了 $k$ 个点，则 $\kappa(G)\le k\le\alpha(G)$，又 $\alpha(G)\le\kappa(G)$，所以 $k=\alpha(G)=\kappa(G)$。
3.2 色数/团数
[链接登录后可见]
PEO 上从后往前依次染色即可。
正确性：与 3.1 类似，留作练习。
如果不需要染色方案，还可以求 $\max{|{x}+N(x)|}$（这里的 $N(x)$ 是 PEO 上 $x$ 之后的邻居，下同）。
3.3 极大团
弦图的极大团一定是某一个 ${x}+N(x)$，而我们需要判定是否为极大团。
设 $G={x}+N(x),H={y}+N(y)$，若 $G\subset H$，则 $G$ 不是极大团并且 PEO 上 $y$ 在 $x$ 前。
设 $\operatorname{next}(x)$ 为 $N(x)$ 中最靠前的点，$y^ *$ 为所有 $y$ 中最靠后的点，那么 $\operatorname{next}(y^ *)=x$。
所以只需判断是否存在 $y$ 满足 $\operatorname{next}(y)=x,|N(x)|+1\le|N(y)|$ 即可。
4.后记
这篇文章仅介绍了与弦图有关的一部分内容，cdq 的论文中还提到了区间图、极大团树等科技，以后会加以补充。
由于学得比较仓促，所以仅仅是入门水平，如果有描述不清或事实性错误请指出。
其实这部分内容挺简单的，前提是你要感性理解。
