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 最大独立集/最小团覆盖
洛谷P3852 [TJOI2007]小朋友
PEO 上从前往后依次选择即可。
正确性：设通过这种方式选出了 \(k\) 个点，则 \(\kappa(G)\le k\le\alpha(G)\)，又 \(\alpha(G)\le\kappa(G)\)，所以 \(k=\alpha(G)=\kappa(G)\)。
3.2 色数/团数
洛谷P3196 [HNOI2008]神奇的国度
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 的论文中还提到了区间图、极大团树等科技，以后会加以补充。
由于学得比较仓促，所以仅仅是入门水平，如果有描述不清或事实性错误请指出。
其实这部分内容挺简单的，前提是你要感性理解。