三元环计数&四元环计数_三元环计数博客

作者：笔触狂放9 | 2024-02-06 21:21:19

踩

三元环计数博客

给出一张n个点m条边的无向图，问图中有多少个三元组{ u , v , w } ，满足图中存在 { (u,v) , (v,w) , (w,u) } 三条边。

将所有点按度数从小到大排序，如果度数相同按 点编号 从小到大排序，u的排名记作 $rnk_u$ 。

将这张图转化为有向图：对于一条无向边 x − y ，若 $rnk_x>rnk_y$ ，那么就将这条无向边变成 x → y 。反之则反之。

这样转化后，这张图一定是 有向无环图 。

证明：

使用反证法，假设有一个环： $a\to b \to c \to a$ ，
那么有（设 x 的度数为 $d_x$ ）：
$d_a \geq d_b \geq d_c \geq d_a$ ，要使该不等式成立，当且仅当满足 $d_a = d_b = d_c = d_a$ 。

设 x 的编号为 $id_x$ ，那么有： $id_a>id_b>id_c>id_a$

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/笔触狂放9/article/detail/64612

三元环计数&四元环计数_三元环计数 博客