三元环与四元环计数

本文讨论$n$个点$m$条边简单无向图$G=(V,E)$的三元环和四元环计数的相关问题。

记$\deg_u$表示点$u$的度。

记$\text{out}_u,\text{in}_u$分别表示点$u$的出度和入度。

三元环计数

考虑将每条边定向，从度数大的点指向度数小的点，度数相同的点则从编号小的指向编号大的。这是全序的，因此定向完后的$G'=(V,E')$是个 DAG。

对于$u\in V$，枚举$(u\to v)\in E'$，再枚举$(v\to w)\in E'$来统计三元环。

首先，每个环只会被统计一次。

算法时间复杂度为$\sum_{u\in V}\text{in}_u\cdot \text{out}_u$。

如果$\deg_u>\sqrt{m}$， 那么$\text{in}_u < \sqrt{m}$。因为$\deg_v>\deg_u>\sqrt{m}$的结点$v$的数量是$O(\sqrt{m})$的。

如果$\deg_u\le \sqrt{m}$，那么$u$的邻边数是$O(\sqrt{m})$的，也就是说$\text{in}_u<\sqrt{m}$仍然成立。因此

$$\sum_{u\in{V}}\text{in}_u\cdot \text{out}_u < \sqrt{m}\sum_{u\in{V}}\text{out}_u < m\sqrt{m}$$

这变相证明了三元环的数量是$O(m\sqrt{m})$的。

FOR(i,1,m){
  scanf("%d%d",ex+i, ey+i);
  dg[ex[i]] ++;
  dg[ey[i]] ++;
}
FOR(i,1,m){
  int u = ex[i], v = ey[i];
  if(dg[u] < dg[v] || (dg[u] == dg[v] && u<v))swap(u,v);
  addEdge(u,v);
}
FOR(u,1,n){
  for_adj(i,u,v) tag[v] = u;
  for_adj(i,u,v) for_adj(j,v,w) if(tag[w] == u) ++cnt;
}

四元环计数

仍然考虑从度数大的点定向到度数小的点。这里我们需要处理两种环：$a\to b\to c\to d\gets a$，或者$a\to b\to c\gets d\gets a$。

对于$u\in V$：

• 枚举$(u\to v)\in E'$，再枚举原图上的边$(v, w)\in E$，根据标记累加四元环个数，然后更新标记。

第一部分的复杂度与三元环相同。

第二部分的复杂度是$\sum_{u\in V}\text{in}_u\cdot \text{deg}_u$。

因为$\text{in}_u<\sqrt{m}$，于是

$$\sum_{u\in{V}}\text{in}_u\cdot \deg_u < \sqrt{m}\sum_{u\in{V}}\deg_u < m\sqrt{m}$$

bool good(int u, int v){
  return dg[u] > dg[v] || (dg[u] == dg[v] && u > v);
}
FOR(u,1,n){ // g2: 有向图, g1: 原图
  for_adj(g2,i,u,v) for_adj(g1,j,v,w){
    if(w == u || !good(u,w))continue;
    if(tag[w] != u) tc[w] = 0;
    cnt += tc[w];
    tag[w] = u, ++tc[w];
  }
}