竞赛图

竞赛图

定义：有向图，对于 \(\forall u\ne v\)，有 \(u\to v\) 或 \(v\to u\) 中的恰好一条边

说人话就是给完全图的每条边定向后得到的有向图

性质

下面均针对有 \(n\) 个点的竞赛图

强连通相关

将竞赛图中的点按出度大小从小到大排序

竞赛图缩点后，DAG 的形态可以看作是一条链，前面的点指向每个后面的点

缩点后还是竞赛图，归纳证明

极大强连通分量在排好序上的点中是互不相交的区间，区间右端点 \(r\) 满足 \(\sum_{i=1}^r out_i=\frac{r(r-1)}2\)

如果第一次出现某个前缀 \(x\) 中点的出度总和为 \(\frac {x(x-1)}2\)，则它是一个强连通分量，且缩点后拓扑序最大

这意味着它所有的出边都指向了内部

同理，对任意的前缀 \(x\)，出度总和 \(\ge \frac {x(x-1)}2\)，而且兰道定理为只要满足前面的条件，就能构造出竞赛图

当 \(n\ge 4\) 时，竞赛图一定有一个点数为 \(n-1\) 的导出子图，满足它是强连通图

证明则是分类讨论去掉 \(x\) 后图被分为若干个强连通分量

哈密顿路相关

竞赛图有哈密顿路径

可以归纳证明并根据归纳给出构造方式

构造：

直接增量构造，假设当前已经有 \(S\to T\) 的路径，现在正在加入点 \(x\)

• 若有 \(x\to S\) 或 \(T \to x\) 的边，直接把它插入首尾
• 否则一定有 \(S\to x,x\to T\)，那么这条通路上存在相邻的点 \(u,v\) 满足 \(u\to x,x\to v\)（考虑 \(x\) 指向和被指向的操作序列首尾不同，中间必然有相邻不同的位置），插入 \(u,v\) 中间即可

竞赛图的强连通分量有哈密顿回路（竞赛图强连通是有哈密顿回路的充要条件）

针对括号中的内容同样给出一种增量构造方式（必要性显然就不说了）

假设我们已经找到了一条哈密顿路径，并把图中的点按路径上的顺序重新标号为 \(1\sim n\)

当前 \(1\sim x-1\) 号点已经连成了回路，现在插入 \(x\) 号点

• 如果存在点 \(y\) 使得 \(x\to y\) 的边存在，由于 \(x-1\to x\) 的边存在，根据上面同理分析，存在相邻两点 \(u,v\) 使得 \(u\to x,x\to v\)，直接把 \(x\) 插入 \(u,v\) 中间
• 否则说明 \(x\) 指向所有点，因为图强连通，所以一定找得到后面的某一点 \(y>x\) 且 \(u\) 指向 \(y\)，把 \(x\sim y\) 这一段路径直接插入到 \(u\) 后面

这样我们得到了 \(O(n^2)\) 构造哈密顿路径与回路的方法

上述增量构造本质就是在归纳，对于 \(n=1\) 的情况显然成立，因此归纳假设正确

杂项

竞赛图的任意导出子图都是竞赛图

竞赛图如果有环，则一定有三元环

例题

CF1268D Invertation in Tournament

观察性质

引理：\(n\ge 4\) 的强连通竞赛图一定可以翻转某个点使翻转后仍连通

根据上面的，它有大小为 \(n-1\) 的强连通导出子图，翻转多余的即可

核心结论：\(n>6\) 的竞赛图一定可以通过翻转一个点的出入边变成强连通图

根据之前的引理，设竞赛图的强连通分量分别为 \(a_1,a_2,\dots,a_k\)

• 如果 \(k=1\)，则 \(ans=0\)
• 如果 \(k\ge 3\)，则翻转 \(a_{2\sim k-1}\) 中的某个点一定可以，因为任意点都可以经过它回到 \(a_1\)
• 如果 \(k=2\)，因为 \(n>6\) 所以一定有一个强连通分量大小 \(\ge 4\)，设为 \(a_1\)，那么翻转它中间的一个点可以使它仍然强连通，并且能让 \(a_2\) 回到它，满足要求

于是数据分治，对于 \(n\le 6\)，暴力枚举翻转的点的集合，对于 \(n>6\)，枚举翻转哪个点，用度数排序后判断是否为强连通图

复杂度 \(O(n^2(\log n))\)，注意 tarjan 的复杂度为 \(O(n+m)\)，稠密图时要小心