三元环问题总结_竞赛图 三元环

三元环问题总结

标签：知识点总结
阅读体验：https://zybuluo.com/Junlier/note/1322477

定义

就是三个点构成的环

无向图上求三元环

首先考虑暴力

1. 枚举一条边，然后枚举其中一个点连出的所有边并把能连到的点都打上标记，再枚举另一个点能连到的所有的边，把打了标记的点数加进答案
2. 显然算重，每个环被枚举到了三次，所以答案除以$3$
3. 复杂度呢：$O(m)$枚举边，$O(m)$第一个点枚举边，$O(m)$第二个点枚举边，所以$O(n^3)$

考虑更优秀的做法

1. 怎么优化上面的算法呢，我们把边有向化，每一条边从度数小的指向度数大的，如果度数相同则编号小的指向编号大的，再同样的用上面暴力的方法枚举
2. 给出复杂度：$O(m\sqrt m)$
3. 为什么复杂度降低了呢，首先还是枚举每条边是吧，然后对于度数小于$\sqrt m$的点，我们当然只用枚举$\sqrt m$条边；对于度数大于$\sqrt m$，它枚举的边指向的点度数一定大于$\sqrt m$（连边方法），这样的点最多只有$\sqrt m$个对吧，那么总的复杂度不就是$O(m\sqrt m)$了吗

如果图是有向图呢

很简单，你是不是发现如果你知道三个点的连边方向了，那是不是可以$O(1)$判断是否为合法三元环
所以我们把有向图变无向，然后重新定向，向上边所讲的找出三元环，然后判断是否合法就$OK$了
复杂度不就是一样的吗，常数可能大一些

竞赛图的三元环呢

竞赛图定义

每两个点间都有连边的有向图

他有什么性质呢

对于一个竞赛图，它要么是一个拓扑图，要么存在一个三元环。
说人话：一个竞赛图中如果存在环，则一定是三元环

随便自己在草稿纸上画几下就得证了，还是证一下吧
一些自己的瞎几把定义：$(i,j)$：有向边，$[i,j]$：无向边

反证法：如果存在环且它不是三元环，那么会有三元组$(i,j,k)$（都在大环上）存在边$(i,j),(j,k)$，那么考虑边$[i,k]$的方向，如果是$(k,i)$，那不就是三元环，伪掉，如果是$(i,k)$，那么会得到一个把$j$排除在外的小一点的环，那么递归证明，最后也是个三元环，伪掉，那么如果竞赛图中有环则一定是三元环

怎么求三元环数量呢？

你当然可以用上面有向图求三元环的方法
但是对于竞赛图，我们有线性方法
先给出结论(圆括号是组合数，$out_i$是一个点的出度)

$$Ans=\binom{n}{3}-\sum_{i=1}^{n}{\binom{out_i}{2}}$$ 给出证明：

直接选出三个点，那么就要容斥掉不是三元环的情况是吧
当然是这个三元环有一个点出度为$2$啦，这样的三元组不可能构成环。。。

一些题目还会要求你容斥掉更多的情况，都可以考虑从点的度数那里入手吼