无向图三元环计数

这个做法的思想还是很巧妙的，首先我们考虑枚举，暴力的方法就是枚举三个点$O(n^3)$，枚举一个点然后枚举出边，然后再枚举出点的出边，然后考虑这个做法的复杂度。对于每条边分析，它会对复杂度的贡献就是指向的点的度数，所以总复杂度就是${\sum }_{i=1}^{m}de{g}_{p_i}$,但是如果我们能够把无向图变为有向图就可以优化复杂度，如果这个有向图没有环，那么所有无向图中的环对应了有向图中的<u,v><u,w><v,w>，然后考虑构造一种方法是的复杂度尽量优秀，那么考虑让度数小的点向度数大的点连边，这样构造出来的图有非常优美的性质，满足所有点的出度都是$O(\sqrt{m})$

具体证明：
如果这个点在原图上度数小于$\sqrt{m}$那么新图上出度一定小于$\sqrt{m}$。
如果这个点在原图上度数大于$\sqrt{m}$那么新图上它只会指向度数大于等于$\sqrt{m}$的点，因为一个图总度数是$O(m)$，所以度数大于等于$\sqrt{m}$的点只有$O(\sqrt{m})$个，所以这些点的出度也是$O(\sqrt{m})$的。

总结

以上是生活随笔为你收集整理的无向图三元环计数的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。