竞赛图

(Updated: )
(6 mins to read)

若竞赛图存在环，则一定存在三元环。

大小为$n$($n>1$)的强连通块，大小为$[3,n]$的简单环均存在。

任意竞赛图都有哈密顿路径（经过每个点一次的路径，不要求回到出发点）。

增量构造：对于第$i$个点，要么放在第一个，要么从后往前找到第一个满足$j\rightarrow i$的，然后插在$j$的后面。

竞赛图存在哈密顿回路的充要条件是强联通。

先构造哈密顿路径，然后构造哈密顿回路。

维护链$v_1,\dots,v_k,\dots,v_i$​，其中$v_k\rightarrowv_1$​，然后考虑扩展到节点$i+1$来扩大环：

  1. $v_{i+1}\rightarrow v_1$​，直接扩大
  2. 找到最小的$j$，满足$v_{i+1}\rightarrow v_{j} (j\le k)$，然后修改路径为$v_{i+1},v_j,\dots,v_k,v_1,\dots,v_{j-1},v_{k+1},\dots,v_i$
  3. 直接考虑下一个节点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
void gao(vector<int>& path) {
  vector<int> npath;
  // 哈密顿路
  npath.push_back(path.front());
  int sz = path.size();
  for (int i=1; i<sz; i++) {
    if (G[path[i]][npath.front()]) npath.insert(npath.begin(), path[i]);
    else {
      for (int j=(int)npath.size()-1; j>=0; j--) {
        if (G[npath[j]][path[i]]) {
          npath.insert(npath.begin()+j+1, path[i]);
          break;
        }
      }
    }
  }
  // 哈密顿回路
  int k = 0;
  for (int i=1; i<sz; i++) {
    if (G[npath[i]][npath[0]]) k = i;
    else {
      for (int j=1; j<=k; j++) {
        if (G[npath[i]][npath[j]]) {
          vector<int> tmp;
          tmp.push_back(npath[i]);
          tmp.insert(tmp.end(), npath.begin()+j, npath.begin()+k+1);
          tmp.insert(tmp.end(), npath.begin(), npath.begin()+j);
          tmp.insert(tmp.end(), npath.begin()+k+1, npath.begin()+i);
          tmp.insert(tmp.end(), npath.begin()+i+1, npath.end());
          swap(tmp, npath);
          k = i;
          break;
        }
      }
    }
  }
  swap(path, npath);
}

强连通缩点后呈链状，拓扑序小的点向所有拓扑序大的点连边（因此可以直接根据强连通分量判断任意两点间的可达性）。

Dirac定理：$n$阶($n\ge3$)无向简单图，任意不相邻的两个顶点$v_i,v_j$​，均有$d(v_i)+d(v_j)\gen$，则存在哈密顿回路。

先不断从首尾扩展，得到极大的路径$s,v_1,\dots,v_k,t$，若$s$和$t$有边则得到回路，否则一定存在$s\rightarrowv_{i+1},t\rightarrowv_i$​（鸽巢原理），构造得到回路$s,v_{i+1},\dots,t,v_i,\dots,s$。如果该回路长度小于$n$，剩余点一定与回路中的某个点有边相连，从该处将环断开，然后重复扩展即可。

$n$阶($n\ge2$)无向简单图，任意不相邻的两个顶点$v_i,v_j$​，均有$d(v_i)+d(v_j)\gen-1$，则存在哈密顿通路。

$n$阶($n\ge3$)无向简单图，任意顶点$v_i$​，均有$d(v_i)\ge\frac{n}{2}$​，则存在哈密顿回路。

兰道定理：将竞赛图的出度从小到大排序得到比分序列$s$，满足以下条件则合法：

$\forall 1\leq k \leq n,\sum \limits_{i=1}^k s_i \geq\binom{k}{2}$，且$k=n$时必须取等号。

先构造序列$a=(0,1,\dots,n-1)$，此时$a$的前缀小于$s$，后缀大于$s$（因为$a$和$s$的总和相同），然后找到第一个$a_l<s_l$​，以及最后一个$a_u=a_l$​（为了保证修改后$a$仍然有序），再找到第一个$a_v>s_v$​，则$a_u<s_u\le s_v<a_v$​，即$a_v\gea_u+2$，若$v\rightarrow u$，或$v\rightarrow p,p\rightarrowu$，就将相应边进行翻转，这样不断调整，最终$a=s$。

强连图竞赛图计数：$g_i=f_i-\sum_{j=1}^{i-1}\binom{i}{j}g_jf_{i-j}$​，即枚举拓扑序最小的强连通分量的大小。