三元环计数学习笔记

三元环是什么?

对于一张$n$个点$m$条边的无向图,一个形如$V=(A, B, C),  E=(AB, BC, CA)$的子图$G$就是一个三元环

三元环怎么数?

法一

很显然有一种基于度数乱搞的做法。

将点分为度数小于$\sqrt{m}$的点和度数大于等于$\sqrt{m}$的点,因为第一种点出边数量不多,第二种点总个数不多,所以对于第一种点枚举出边,对于第二种点枚举点即可

法二

这是一个正经做法

首先将整张图的每条边定向,让它变成一个有向图

设一条边连接的两个点分别叫$x$和$y$,如果$x$的度数和$y$的度数不相等,那么就让边从度数小的连向度数大的,否则让边从标号小的连向标号大的

这个图一定是一个DAG。假设有一个环,如果这个环上有两个点度数不同,那显然没办法成环,因为一条路径上的点度必定是不降的。那么考虑这个环上所有点的度数相同的,那么这个环上的标号就应该是递增的,很显然无法成立。所以这个图中必定没有环。

这样三元环的三条边就无法是$AB,BC,CA$了,只能是$AB,AC,BC$的形式

这样就有一种简单的方法可以保证每个三元环只被计算一次了。首先枚举 $AB,AC,BC$ 中的点$A$,给点$A$的所有出点打一个为标号$A$的标记。之后枚举$A$的出点,枚举当前出点$B$的出点,若$B$的出点$C$的标记是$A$,那么$ABC$就是一个三元环

例题

[HDU 6184] Counting Stars

发表评论

邮箱地址不会被公开。 必填项已用*标注