本文讨论个点条边简单无向图的三元环和四元环计数的相关问题。

表示点的度。

分别表示点的出度和入度。

三元环计数

考虑将每条边定向,从度数大的点指向度数小的点,度数相同的点则从编号小的指向编号大的。这是全序的,因此定向完后的是个 DAG。

对于,枚举,再枚举来统计三元环。

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

算法时间复杂度为

如果, 那么。因为的结点的数量是的。

如果,那么的邻边数是的,也就是说仍然成立。因此

这变相证明了三元环的数量是的。

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;
}

四元环计数

仍然考虑从度数大的点定向到度数小的点。这里我们需要处理两种环:,或者

对于

  • 枚举,再枚举原图上的边,根据标记累加四元环个数,然后更新标记。

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

第二部分的复杂度是

因为,于是

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];
  }
}