三元环计数与四元环计数.

三元环计数#

给定图 , 求图中有多少恰有三个元素的环.

记 为 中 的度数. 构造有向图 , 使得对于原图中的所有边 , 若 或者 且 , 则连边 , 否则连边 . 容易发现所构造的 是一有向无环图. 记 为 中 的入度, 为 中 的出度.

考虑如下算法: 枚举点 , 再枚举其所有出边 , 再枚举 的所有出边 , 判定 是否构成一个三元环, 也即是否存在边 .

该算法之时间复杂度可以如下计算: 对于每个点 , 有 个 会添加 的计算量. 也即复杂度为 . 首先有: , 所以 . 又 只会向 的点连边, 由于 , 所以这些点的个数是不大于 的, 所以 . 所以 . 所以 .

四元环计数#

给定图 , 求图中有多少恰有三个元素的环.

仿照三元环计数的, 我们对二元组 从小到大排序, 记 为排序后 的排名. 我们这样计数四元环: 找到其中 最大的节点 和 最小的节点 , 统计二元组 的数量, 满足 .

我们还是先枚举 然后枚举一个 的 , 再枚举一个 满足 , 在这个 上记录被访问的次数, 最后对于每个 统计并清空这个记录的值即可.