是什么

广义串并联图定义为：不存在同胚于 \(K_{4}\) 的子图的图。

\(K_{i}\) 就是 \(i\) 个点的完全图。
同胚：反复插入或删除二度点后同构。

通俗点就是：对于任意 \(4\) 个节点都不存在 \(6\) 条两两没有公共边的路径连接这 \(4\) 个节点中的每一对节点的无向连通图。

给两张图看看：

这张图就是一张广义串并联图。

那么这张图呢？

它并不是一张广义串并联图。
图中 \(1,4,6,5\) 号节点，可以通过 \(6\) 条没有公共边的的路径到达。
\(6\to4\)
\(6\to1\)
\(6\to2\to8\to5\)
\(4\to1\)
\(4\to5\)
\(1\to5\)
根据定义，这张图便不是一张广义串并联图。

怎么判

显然我们可以暴力去枚举所有 \(4\) 个点，去找存不存在 \(6\) 条可以使这 \(4\) 个点两两到达，且没有边重合的路径。但这样显然时间复杂度太高了，无法接受。
首先，我们观察到，假如存在一个点，其度数为 \(1\)，（我们不妨称度数为 \(k\) 的点为 \(k\) 度点）那么删去这个点对图的判定是没有影响的，对于这些点我们可以直接删除掉。
拿这张图举例：

删去其中的 \(1\) 度点后就变成了这样：

我们称这样的操作为“删 \(1\) 度点”操作。似乎这一没有什么太大的变化。
我们现在再给出一种操作，称为“缩 \(2\) 度点”操作，什么意思呢？取一个度数为 \(2\) 的点 \(u\)，与其相连的两个点设为 \(v\) 和 \(w\)，将原本的边 \((u,w)\) 和 \((v,w)\) 删去，连接一条新的边 \((v,w)\)。这样的操作称为“缩 \(2\) 度点”操作。
比如对上图中的 \(1\) 号点进行“缩 \(2\) 度点”操作，会得到这么一张图。

好，我们现在证明一下，进行“缩 \(2\) 度点”操作后的图的判定结果和原图一样。

缩 \(2\) 度点

我们不妨将操作反过来，现在变成删去 \((u,v)\)，新建点 \(w\)，连接 \((u,w)\) 和 \((v,w)\)。

假设原图不是广义串并联图，那么根据定义，存在 \(6\) 条不重合的路径，使 \(4\) 个不同的点可以两两到达。我们不妨设这 \(4\) 个点为 \(a,b,c,d\)，这 \(6\) 条路径为 \(p(a,b),p(a,c),p(a,d),p(b,c),p(b,d),p(c,d)\)。
我们这里分两种情况讨论：

• 在经历完所有的“缩 \(2\) 度点”操作后，这 \(6\) 条路径上没有一条边经历了更改。那此时，\(a,b,c,d\) 依然可以判定图不是广义串并联图。
  
• 在某次操作时，这 \(6\) 条路径中的某一条边经历了修改。我们设这条修改了的边为 \((u,v)\)，新增的点为 \(w\)。不妨假设出现修改的路径为 \(p(a,b)\)，因为这 \(6\) 条路径没有重边，所以 \(p(a,u)\) 和 \(p(v,b)\) 与另外 \(5\) 条路径也均没有重边。此时 \(w\) 点是一个图上曾经不存在的点。且只连接了 \(u\) 和 \(v\) 两个点，因此新的 \(p(a,b)\) 依然与另外 \(5\) 条路径没有重边。

若原图是广义串并联图，证明是类似的。
综上，“缩 \(2\) 度点”操作不会影响。

那么我们又可以将图变成这样：

(这里暂时先只进行了一部分“缩 \(2\) 度点”操作。)

我们发现出现了很多重边。
显然删去重边不会影响我们的判定结果，因此我们直接删去就行了。
我们称这种操作为“叠合重边”。

我们继续进行以上三种操作：

我们发现最后变成了一个点，一个点显然是不能继续操作了，并且一个点也是广义串并联图。

而我们看看另一张图：

它经过操作后，只能变成这样：

那此时我们大胆猜测：
假如一张图可以经过上述三种操作，变成一个点，那么这张图便是广义串并联图。

而且我们知道，这三种操作，会将所有度数小于等于 \(2\) 的点去掉。那我们可以再猜测：
如果一张图所有点的度数均大于等于 \(3\)，那么这张图一定不是广义串并联图。

我们现在来尝试证明一下。
（以下证明大多参考原文，只是部分给出了更加详细的证明。如果认为 OIer 不需要掌握证明，可以跳过这一部分。）

证明

首先我们来证明另外两个定理：

定理1

对于任意一个点双联通分量，其要么是 \(K_2\)，要么至少存在一个简单环。

我们知道，不存在环的图，是树。树除了叶子节点外均是割点。而有割点的图一定不是一个点双联通分量，因此对于树而言，只有 \(K_2\) 是点双联通分量。于是，不是 \(K_2\) 的点双联通分量一定不是树，也就一定存在至少一个简单环。

定理2

对于任意一个非空无向图 \(G\)，一定存在 \(G\) 的一个点双联通分量 \(B\)，使得 \(B\) 上只有不超过 \(1\) 个（可以是 \(0\) 个）节点是 \(G\) 的割点，如果不存在割点，此时 \(B=G\)。

假如 \(G\) 中存在一个点双联通分量为 \(K_{2}\)，且 \(G\not = {K_{2}}\)，那么度数不为 \(1\) 的那个点，是 \(G\) 的割点之一。（去掉这个点后，度数原先为 \(1\) 的点就不与原图联通了。）
假如 \(G=K_{2}\) 那么此时 \(G\) 中只有 \(B=G\) 这一个点双联通分量，且 \(G\) 和 \(B\) 均没有割点。

那么此时我们的图 \(G\) 是没有 \(K_{2}\) 这一类点双联通分量的。
我们对剩下的点双联通分量进行“缩点”操作，会得到一棵树。
分两种情况：

1. 缩成了一个点。此时说明 \(G\) 本身就是一个点双联通分量，并且 \(G\) 中没有割点，此时 \(B=G\)。
   
2. 是一棵树，此时树上的每个点都代表了一个点双联通分量。对于每一个点双，在 \(G\) 上的割点数量为其在树上的度数（两个点双至多有一个公共点且这个点为割点）。容易发现叶子节点度数为 \(1\)，也就找到了一个符合题设的 \(B\)。

得证。

上文中的“两个点双联通分量至多有一个公共点且这个点为割点”，大致证明如下：
设两个点双联通分量为 \(A\) 和 \(B\)，首先证明至多一个公共点。
使用反证法，假设存在两个或以上公共点。那么此时，\(A\) 中所有点均与 \(B\) 中所有点两两点双联通。\(A\) 中的点本身就两两点双联通，\(B\) 中的点同理。此时 \(A \cup B\) 才是点双联通分量，与题设矛盾。
我们现在证明第二点，这个点是割点。
依然使用反证法，假设这个点不是割点，那么删去这个点后，\(A\) 和 \(B\) 依然联通，那么这也说明 \(A \cup B\) 才是点双联通分量。与题设矛盾。
得证。

由这两个定理，我们可以得出一个引理。

引理1

对于一个不是 \(K_{2}\) 的点双联通分量上的任意一点 \(u\)，一定存在一个简单环 \(C\) 使得 \(u\) 在 \(C\) 上。

依然考虑反证法，假设存在一个点 \(u\)，找不到一个简单环 \(C\) 使得 \(u\) 在 \(C\) 上，设这个点双联通分量为 \(B\)。

因为 \(u\) 在点双联通分量上，所以我们删去 \(B\) 上任意一点 \(v\) 后，其他在 \(B\) 上的点依然与 \(u\) 联通。我们不妨删去一个与 \(u\) 相邻的点 \(w\)。取一点 \(a\) 在 \(B\) 上且原路径 \(p(u,a)\) 经过 \(w\)，现在删去点 \(w\) 后，有新的路径 \(p'(u,a)\)，根据点双联通的定义，\(p(u,a)\) 与 \(p'(u,a)\) 没有重合的边。于是，\(p(u,a),p'(u,a)\) 构成一个环，与题设矛盾。

得证。

我们现在需要证明：任意一张广义串并联图都可以经过上文三种操作，最终变成一个点。

我们再证明一个定理。

定理3

若一张无向连通图 \(G\) 中存在 \(3\) 个不同的 \(1\) 度点 \(x,y,z\)，则一定存在一个点 \(u \notin \{x,y,z\}\) 使得存在 \(3\) 条两两没有公共边的简单路径，满足其中一个端点均为 \(u\) 且另一个端点分别为 \(x,y,z\)。

我们先求出 \(G\) 的任意一棵生成树 \(T\)。
因为 \(x,y,z\) 在 \(G\) 上是 \(1\) 度点，所以在 \(T\) 上绝对也是 \(1\) 度点，也就是叶子。
一张图上度数为奇数的点的数量一定为偶数个（所有点度数之和为 \(2n\)，是一个偶数，偶数乘任何数还是偶数，奇数乘偶数是偶数，偶数加偶数是偶数，奇数加偶数是奇数。）。因此在 \(G\) 中一定存在一个点不是 \(x,y,z\) 中的一个，我们将这一个点作为 \(T\) 的根。
取一点 \(u=\operatorname{LCA}(x,y)\)。因此 \(x,y,z\) 均为叶子且不为根，所以有 \(u\not ={x},u\not ={y},u\not ={z}\)。
我们分两种情况来：

第一种情况如图（图比较简陋）：

也就是 \(z\) 不在 \(u\) 的子树中，或者 \(\operatorname{LCA}(u,z)=u\) 且 \(\operatorname{LCA}(y,z)=u\) 的情况。此时显然在 \(T\) 上，\(u\) 到 \(x,y,z\) 的路径没有重边。

第二种情况如图（图依然简陋）：

此时 \(\operatorname{LCA}(x,z)\) 和 \(\operatorname{LCA}(y,z)\) 中恰有一个不是 \(u\)。
不妨设 \(\operatorname{LCA}(x,z)=w\not=u\)，那么此时在 \(T\) 上，\(w\) 到 \(x,y,z\) 的路径没有重边。

得证。

要证明原命题，我们尝试证明其逆否命题：

任意一个不能用上述操作使其变为一个只包含一个节点的图的无向连通图不是广义串并联图。

根据前文，我们知道一张图经过三种操作后，要么变成一个点，要么变成一张所有点的度数均大于等于 \(3\) 的图。
一个点显然是广义串并联图，我们又知道三种操作对图的判定没有影响。因此能变成一个点的图是广义串并联图。
那我们现在只需要证明：任意一张所有点的度数均大于等于 \(3\) 的图不是广义串并联图。

最终证明

我们现在有一个所有点的度数均大于等于 \(3\) 的图 \(G\)。
根据定理2，\(G\) 上一定存在一个点双联通分量 \(B\)，存在至多一个点是 \(G\) 的割点。
\(B\) 不会是 \(K_{2}\)，否则会出现度数为 \(1\) 的点。

若 \(B\not ={G}\)，则 \(B\) 中存在一个 \(G\) 中的割点。再根据引理1，一定存在一个简单环 \(C\) 使得这个割点在 \(C\) 上。
若 \(B=G\)，则 \(B\) 中不存在一个 \(G\) 中的割点，此时我们根据定理1，找到任意一个简单环 \(C\)。

设 \(C\) 的环长为 \(len\)，环上的点依次为 \(v_{0},v_{1},v_{2},\dotsb,v_{len-1}\)，有 \(v_{0}\) 与 \(v_{len-1}\) 相邻，对于 \(1\le i\le len-1\) 有 \(v_{i-1}\) 与 \(v_{i}\) 相邻。

参考文献

吴作同, 《〈公园〉命题报告》, IOI2019 中国国家候选队论文
OI-Wiki 图论相关概念
OI-Wiki 双连通分量