竞赛图的性质

xzzduang · 2023-03-11 12:45:07 · 个人记录

竞赛图是把一个完全图的边定向后得到的有向图，所以也是一个 n 个点 \binom{n}{2} 条边的无自环重边的有向图。

竞赛图有许多优美的性质和定理，并且多半都和强连通分量有关系。

0x01 兰道定理

对于一个从小到大排序后的出度序列 s_{1\ldots n}，它是合法的（存在一个竞赛图出度满足这个序列），当且仅当：

且在 k=n 时取等。注意到把以上结论中的出度换成入度也是对的。

必要性比较显然，因为前 k 个点内部的边已经刚好 \binom{k}{2} 条了。

充分性不太会证，好像是可以构造出来的。

0x02 寻找强连通分量

首先我们可以手模一下竞赛图缩点之后的结构，显然入度为 0 和出度为 0 的 scc 都只能有一个，所以这应该是一个链的结构。

可以发现，拓扑序小的 scc 里面的点的出度一定严格大于拓扑序大的 scc 里面的点的出度。

所以所有点按照出度大小从小到大排序之后，这个图的每个 scc 都是序列上的一个区间。

我们可以找到第一个 k 使得 \sum_{i=1}^ks_i=\binom{k}{2}，发现这个序列上的前 k 个点就是原图拓扑序最大的 scc。因为首先肯定有 \sum_{i=1}^ks_i\ge \binom{k}{2}，如果等于的话说明后面的点与这 k 个点的边都是连向这 k 个点的，这是前 k 个点组成一个强连通分量的必要条件。并且前面不存在取等的地方，说明前面绝对没有强连通分量，所以这 k 个点恰好组成了一个强连通分量。

简单地拓展一下可以发现，找到所有的 k 使得兰道定理的不等式取等，这些 k 就是所有强连通分量的分界点。

0x03 哈密顿通路

一个结论是：任何竞赛图都存在哈密顿通路。

我们可以尝试构造出一组解。

考虑增量构造，从空图开始加点，现在加入点 x，设前面的点形成的哈密顿通路的起点为 S，终点为 T。

• 如果存在 x\to S 或者 T\to x 的边，则直接将 x 在端点处加入通路即可。
• 否则此时一定存在 S\to x 和 x\to T，那么这条通路上一定存在两个相邻的点 u,v 使得 u\to x,x\to v，在 u,v 之间插入 x 即可。

这样就完成了证明，并且我们找到了一个 \mathcal{O}(n^2) 构造哈密顿通路的算法。

0x04 哈密顿回路

一个结论是：任何强连通的竞赛图都存在哈密顿回路。

我们可以尝试构造一组解。

首先我们先找出一条这个竞赛图的哈密顿通路，不妨认为这个通路是 1\to 2\to 3\ldots\to n-1\to n。

因为强连通，所以肯定存在一个点使得 t\to 1。我们可以把 1\to 2\to\ldots \to t\to 1 作为初始的回路，然后考虑增量构造。

现在加入点 x，且前 x-1 个点已经构造出了一条回路。

• 如果前 x-1 个点中存在一个 y 使得 x\to y。注意到 x-1\to x 成立，所以我们一定可以找到回路上相邻的两个点 u,v 使得 u\to x,x\to v。把 x 插入到 u,v 间即可。
• 否则前 x-1 个点中的每一个点都连向了 x，又因为强连通，后面肯定存在一个 y 连有到前 x-1 个点的反向边，找到这个 y，设它的反向边连向了 t。设 t 在回路上的前一个点是 r，因为有 r\to x 的边，我们可以像 r\to x\to x+1\ldots\to y\to t 这样把 [x,y] 这一段的点都加入回路。

这样就完成了证明，并且我们找到了一个 \mathcal{O}(n^2) 构造哈密顿回路的算法。