笔记 2023.12.20：图论问题选讲

笔记 2023.12.20：图论问题选讲

还有几个题的题解（口胡）在路上了。

QOJ5407 基础图论练习题

性质

对于一个强连通竞赛图，一定可以 \(O(n^2)\) 地找到一条哈密尔顿回路。

证明。考虑归纳，\(n=1\) 成立了，一般的 \(n\) 就考虑随意删掉一个点 \(x\)，整张图分成 \(H_1, H_2, \cdots, H_k\) 共 \(k\) 个强连通分量且不妨假设 \(x\) 向 \(H_1\) 连边，\(H_k\) 向 \(x\) 连边。这些 \(H\) 连成一个链状的偏序。根据归纳假设，我们首先从 \(x\) 走到 \(H_1\)，然后在 \(H_1\) 中走哈密尔顿回路，走到 \(H_2\)，……最后在 \(H_k\) 走回 \(x\)。

做法

对原竞赛图缩点。连接两个强连通分量的边的影响是显见的。对于强连通分量内部，考虑跑一条哈密尔顿回路，不在上面的边不管。如果翻转回路上的边，那大家就拆散了，成了一条链，相当于给一条链，链上连了一些反向边，求强连通分量个数。相当于对反向边覆盖的边做区间加，问有多少个边没被覆盖，然后强连通分量个数就是边数加一。\(O(n^2)\) 次区间加，\(O(n)\) 次全局查询，差分，\(O(n^2)\)。

CF1268D Invertation in Tournament

性质一

如果一个竞赛图是强连通图，等价于将出度序列排序后没有一个长度为 \(i<n\) 的前缀满足前缀和为 \(\binom i 2\)。

性质二

对于一个 \(n\geq 4\) 个点强连通竞赛图，一定存在一个 \((n-1)\) 个点的导出子图是强连通的。

证明。考虑归纳，\(n=1\) 成立了，一般的 \(n\) 就考虑随意删掉一个点 \(x\)，整张图分成 \(H_1, H_2, \cdots, H_k\) 共 \(k\) 个强连通分量且不妨假设 \(x\) 向 \(H_1\) 连边，\(H_k\) 向 \(x\) 连边。这些 \(H\) 连成一个链状的偏序。世界线分裂，如果 \(k=1\) 那么完事；如果 \(|H_i|=1\)，则 \(k\geq 3\)，加入 \(x\) 删除 \(h_i\) 就行；如果存在 \(|H_i|\geq 4\)，加入 \(x\) 删除 \(H_i\) 中一个点使得它还是强连通。

性质三

对于一个 \(n>6\) 的竞赛图，只需至多一次操作变成强连通。

证明。

缩点排成一条链。
如果有一个大小 \(\geq 4\) 的强连通分量，考虑随机选其中一个点反转方向，那么这个强连通分量还是强连通分量，然后它可以到达前面所有强连通分量，然后可以回去，到达后面所有强连通分量，最后回到刚才选的点。
如果有至少三个强连通分量，在中间的强连通分量中随机选取一个点反转，现在可能这个强连通分量分裂了但是没关系，它还是一条链加一个反点，通过这个反点可以遍历整张图。
如果不满足上面两种假设说明 \(n\leq 6\)。