一、广义串并联图的定义
广义串并联图，对于任意 \(4\) 个节点都不存在 \(6\) 条两两没有公共边的路径连接这 \(4\) 个节点中的每一对节点的无向连通图。
树，仙人掌等都是广义串并联图。
二、广义串并联图的性质
广义串并联图重要的是一种思想——将图缩合。
每次删 \(1\) 度点、缩 \(2\) 度点、叠重边。
具体就是如下三种操作：
-
将度数为 \(1\) 的点删除。
-
对于一个度数为 \(2\) 的点 \(a\)，设其连接了 \((a, b)\) 和 \((a, c)\)，将 \((b, a)\) 和 \((a, c)\) 缩成 \((b, c)\)。
-
对于重边，只保留一条。
可以证明，广义串并联图经过缩合后只剩下一个点。
设图 \(G = (V, E)\)，\(|V| = n, |E| = m\)，当 \(m - n \le k\)，\(k\) 较小时，可以考虑广义串并联图。
经过如上缩合操作后，\(m - n\) 单调不增。
最终图中只剩下度数 \(\ge 3\) 的点，所以 \(m \ge \dfrac{3}{2}n, k \ge m - n \ge \dfrac{1}{2}n\)。
得到 \(n \le 2k, m \le 3k\)，就将图缩合到了一个极小的范围内。