无向图三元图和四元图计数
aSunnyDay
·
·
个人记录
对于原图 G=(V,E) ，首先我们给每条边定向。将度数小的节点向度数大的节点连边，如果度数一样，则按节点编号（这点很重要！！！否则无法产生偏序关系！！！）。产生新图 G'=(V,E')
然后可以有一个结论，就是对于任意顶点 u\in V，有 \deg_u^+\leq \sqrt{m}。
可以用反证法来证明
这么做有一个好处，就是我们可以遍历每条边 u\rightarrow v，然后在任意一个顶点 u 或 v 继续遍历以它为出发点的所有边，这么做的复杂度是 m\sqrt{m} 的。
换句话来说，我们可以在 O(m\sqrt{m}) 里枚举所有的 u\rightarrow v，v\rightarrow w，或者是u\rightarrow v，u\rightarrow w，因为它们的总量是 m^{1.5} 级别的。
当然要注意，只能以 u 和 v 为出发的节点，不能是到达的节点，因为我们只能保证它的出度，无法保证入度。
现在考虑三元环计数的问题，对于原图 G 上的三元环 (u,v,w)，我们可以对应到新图 G' 上的三元环 (u,v,w)，其中满足 u\rightarrow v，v\rightarrow w，u\rightarrow w。并且这是一个双射（即一一映射）。
考虑枚举 u，首先枚举它的所有出边，并对所有 w 打上一个标记，说明它是能由 u 直接到达。然后枚举 u\rightarrow v, v\rightarrow w，并用原来打在 w 上的标记看它是否能由 u 直接到达。
这样我们便在 m^{1.5} 里解决了三元环计数问题
接着我们来看四元环问题。
一样的道理，对于原图 G 上的四元环 (A,B,C,D)，映射到新图 G' 上可能有如下几种情况。
-
A\rightarrow B$,$B\rightarrow C$,$C\rightarrow D$,$A\rightarrow D
-
A\rightarrow B$,$B\rightarrow C$,$A\rightarrow D$,$D\rightarrow C
-
A\rightarrow B$,$A\rightarrow D$，$C\rightarrow B$，$C\rightarrow D
至于这三个类型怎么想出来，可以画一个四元环，然后钦定第一个节点度数最小，这样两条边的方向就定了（这里也可以看出确定偏序关系的重要性），剩下两条边共 4 种定向方式，并且有两种是一样的，所以就把这三个给定出来了。
对于第一种情况，固定 B，在 m^{1.5} 时间里枚举 A\rightarrow B，A\rightarrow D，在 m^{1.5} 时间里枚举 B\rightarrow C，C\rightarrow D。并把结果存在 D 里。
对于第二种情况，固定 A，直接枚举 A\rightarrow B，B\rightarrow C 和 A\rightarrow D，D\rightarrow C，把答案存在 C 上，注意求的是 \dbinom{f_C}{2}，复杂度 m^{1.5}
对于第三种情况，固定 B，枚举 A\rightarrow B， A\rightarrow D 和 C\rightarrow B，C\rightarrow D。可以在 m^{1.5} 做完。
至于五元环以上的计数问题，目前没有 m^2 以内算法。