无向图的三元环计数（Triple Counting in Undirected Graphs）
字数 3318 2025-12-19 09:52:29

无向图的三元环计数（Triple Counting in Undirected Graphs）

题目描述

给定一个无向简单图 \(G = (V, E)\)，其中 \(|V| = n\)，\(|E| = m\)。需要计算图中三元环的数量。
一个三元环是指由三个顶点 \(\{u, v, w\}\) 构成的环，满足 \((u,v), (v,w), (w,u)\) 都是图中的边。
注意：三元环是无序的，即 \(\{u,v,w\}\) 和 \(\{v,u,w\}\) 视为同一个环。

解题思路

最朴素的方法是枚举所有三元组 \((u,v,w)\)，检查是否两两相连。时间复杂度为 \(O(n^3)\)，在 \(n\) 较大时不可行。
我们需要一个更高效的算法，利用定向法（Orientation Method），将时间复杂度降至 \(O(m \sqrt{m})\)。

核心思想

  1. 将无向图的每条边进行定向：从度数小的顶点指向度数大的顶点；若度数相等，则从编号小的指向编号大的。这样得到一个有向无环图（DAG）。
  2. 在定向后的图中，每个三元环 \(\{u,v,w\}\) 会出现且仅出现一次，其中两个顶点指向第三个顶点（即形成“两条入边、一条出边”的结构）。
  3. 枚举每个顶点 \(u\) 的出边邻居，对每一对出边邻居 \(v, w\)，检查 \(v\) 和 \(w\) 在原始图中是否有边（快速检查）。
  4. 利用定向的性质，总枚举次数被控制在 \(O(m \sqrt{m})\)。

解题步骤详解

步骤 1：计算每个顶点的度数

输入图的邻接表表示，先计算每个顶点 \(u\) 的度数 \(deg[u]\)。
时间复杂度：\(O(n + m)\)。

步骤 2：对边进行定向

构建一个新的有向邻接表 \(adj\_dir[u]\)，表示从 \(u\) 出发的出边邻居列表。
对于每条无向边 \((u, v)\)（假设 \(u < v\) 避免重复处理），定向规则为：

  • 如果 \(deg[u] < deg[v]\)，则定向为 \(u \rightarrow v\)。
  • 如果 \(deg[u] > deg[v]\)，则定向为 \(v \rightarrow u\)。
  • 如果 \(deg[u] = deg[v]\)，则定向为从编号小的指向编号大的（例如 \(u \rightarrow v\) 当 \(u < v\)）。

这样定向后，每个顶点的出度不超过 \(\sqrt{2m}\)。
证明：假设某个顶点 \(u\) 的出度 \(d^+(u) > \sqrt{2m}\)。对于 \(u\) 的每个出边邻居 \(v\)，有 \(deg[v] \ge deg[u]\)（根据定向规则）。那么这些邻居的度数至少为 \(deg[u]\)，而总边数 \(m \ge d^+(u) \cdot deg[u] / 2\)（每个邻居贡献至少 \(deg[u]\) 条边，但每条边可能被算两次，除以 2 粗略估计）。结合 \(d^+(u) > \sqrt{2m}\) 可推出矛盾。因此 \(d^+(u) \le \sqrt{2m}\)。

时间复杂度：\(O(m)\)。

步骤 3：标记边以便快速查询

为了在 O(1) 时间内检查两个顶点是否有边，需要快速查询结构。
常用方法：

  • 如果顶点编号较小（例如 \(n \le 10^5\)），可以使用邻接矩阵（空间 \(O(n^2)\) 可能太大）。
  • 更好的方法是哈希表：对每个顶点 \(u\)，将其邻居集合存入一个哈希表（如 unordered_set）。构建总复杂度 \(O(m)\)，单次查询平均 O(1)。

这里我们采用：
创建一个数组 unordered_set<int> neigh[u]（或布尔数组的压缩表示），存储 \(u\) 的所有邻居（原始无向边）。
构建时间：\(O(m)\)，查询时间：平均 O(1)。

步骤 4：计数三元环

初始化计数器 count = 0。
对每个顶点 \(u\)：

  1. 遍历 \(u\) 的每个出边邻居 \(v\)（即 \(v \in adj\_dir[u]\)）。
  2. 对每一对 \(v, w\)（其中 \(v, w\) 都是 \(u\) 的出边邻居，且 \(v < w\) 避免重复）：
    • 检查在原始无向图中，\(v\) 和 \(w\) 是否相连（即 neigh[v].contains(w) 为真）。
    • 如果相连，则 {u, v, w} 构成一个三元环，计数器加 1。

为什么这样不会漏掉三元环？
在定向后的 DAG 中，每个三元环恰好有一个顶点，它的两条边是入边（另外两个顶点指向它）。我们枚举每个顶点 \(u\) 作为“两条入边的终点”，检查它的两个入边邻居是否相连。根据定向规则，这两个邻居的出边会指向 \(u\)，所以它们同时是 \(u\) 的出边邻居。因此枚举 \(u\) 的所有出边邻居对即可覆盖。

时间复杂度分析：
每个顶点 \(u\) 的出度不超过 \(\sqrt{2m}\)，所以检查的出边邻居对数量为 \(O(\sqrt{m}^2) = O(m)\) 级别？不对，是对所有顶点求和：
设 \(d^+(u)\) 为 \(u\) 的出度，则总检查对数为 \(\sum_{u} \binom{d^+(u)}{2} \le \sum_{u} (d^+(u))^2\)。
由于 \(\sum_{u} d^+(u) = m\)（每条边恰好被定向一次），且 \(d^+(u) \le \sqrt{2m}\)，通过柯西不等式可证明 \(\sum_{u} (d^+(u))^2 \le \sqrt{2m} \cdot m = O(m \sqrt{m})\)。
因此总时间复杂度为 \(O(m \sqrt{m})\)，在一般图中优于 \(O(n^3)\)。

步骤 5：输出结果

最终 count 就是三元环的总数。

算法示例

假设图有 5 个顶点，边集为：
(1,2), (1,3), (1,4), (2,3), (2,5), (3,4), (3,5)
度数：deg[1]=3, deg[2]=3, deg[3]=4, deg[4]=2, deg[5]=2。

步骤 2：定向

  • (1,2)：deg 相等，1<2，定向 1→2
  • (1,3)：deg1<deg3，定向 1→3
  • (1,4)：deg1>deg4，定向 4→1
  • (2,3)：deg2<deg3，定向 2→3
  • (2,5)：deg2>deg5，定向 5→2
  • (3,4)：deg3>deg4，定向 4→3
  • (3,5)：deg3>deg5，定向 5→3

有向邻接表：
1→{2,3}
2→{3}
4→{1,3}
5→{2,3}

步骤 4：计数

  • u=1：出边邻居 {2,3}，检查 (2,3) 有边 → count=1
  • u=2：出边邻居 {3}，无对
  • u=4：出边邻居 {1,3}，检查 (1,3) 有边 → count=2
  • u=5：出边邻居 {2,3}，检查 (2,3) 有边 → count=3

最终三元环：{1,2,3}, {1,3,4}, {2,3,5}，共 3 个。

关键点总结

  1. 定向降低了出度，将枚举限制在 \(O(\sqrt{m})\) 以内。
  2. 快速查询边是保证效率的关键，需用 O(1) 数据结构。
  3. 算法适用于无向简单图（无自环、无重边）。
  4. 时间复杂度 \(O(m \sqrt{m})\)，空间复杂度 \(O(n + m)\)。

这样我们就完成了无向图三元环计数的高效算法讲解。

无向图的三元环计数（Triple Counting in Undirected Graphs） 题目描述 给定一个 无向简单图 \( G = (V, E) \)，其中 \( |V| = n \)，\( |E| = m \)。需要计算图中 三元环 的数量。 一个三元环是指由三个顶点 \( \{u, v, w\} \) 构成的环，满足 \( (u,v), (v,w), (w,u) \) 都是图中的边。 注意：三元环是无序的，即 \( \{u,v,w\} \) 和 \( \{v,u,w\} \) 视为同一个环。 解题思路 最朴素的方法是枚举所有三元组 \( (u,v,w) \)，检查是否两两相连。时间复杂度为 \( O(n^3) \)，在 \( n \) 较大时不可行。 我们需要一个更高效的算法，利用 定向法（Orientation Method） ，将时间复杂度降至 \( O(m \sqrt{m}) \)。 核心思想 将无向图的每条边进行 定向 ：从度数小的顶点指向度数大的顶点；若度数相等，则从编号小的指向编号大的。这样得到一个 有向无环图（DAG） 。 在定向后的图中，每个三元环 \( \{u,v,w\} \) 会出现且仅出现一次，其中两个顶点指向第三个顶点（即形成“两条入边、一条出边”的结构）。 枚举每个顶点 \( u \) 的 出边邻居 ，对每一对出边邻居 \( v, w \)，检查 \( v \) 和 \( w \) 在原始图中是否有边（快速检查）。 利用定向的性质，总枚举次数被控制在 \( O(m \sqrt{m}) \)。 解题步骤详解 步骤 1：计算每个顶点的度数 输入图的邻接表表示，先计算每个顶点 \( u \) 的度数 \( deg[ u ] \)。 时间复杂度：\( O(n + m) \)。 步骤 2：对边进行定向 构建一个新的有向邻接表 \( adj\_dir[ u ] \)，表示从 \( u \) 出发的出边邻居列表。 对于每条无向边 \( (u, v) \)（假设 \( u < v \) 避免重复处理），定向规则为： 如果 \( deg[ u] < deg[ v ] \)，则定向为 \( u \rightarrow v \)。 如果 \( deg[ u] > deg[ v ] \)，则定向为 \( v \rightarrow u \)。 如果 \( deg[ u] = deg[ v] \)，则定向为从编号小的指向编号大的（例如 \( u \rightarrow v \) 当 \( u < v \)）。 这样定向后，每个顶点的 出度 不超过 \( \sqrt{2m} \)。 证明 ：假设某个顶点 \( u \) 的出度 \( d^+(u) > \sqrt{2m} \)。对于 \( u \) 的每个出边邻居 \( v \)，有 \( deg[ v] \ge deg[ u] \)（根据定向规则）。那么这些邻居的度数至少为 \( deg[ u] \)，而总边数 \( m \ge d^+(u) \cdot deg[ u] / 2 \)（每个邻居贡献至少 \( deg[ u ] \) 条边，但每条边可能被算两次，除以 2 粗略估计）。结合 \( d^+(u) > \sqrt{2m} \) 可推出矛盾。因此 \( d^+(u) \le \sqrt{2m} \)。 时间复杂度：\( O(m) \)。 步骤 3：标记边以便快速查询 为了在 O(1) 时间内检查两个顶点是否有边，需要快速查询结构。 常用方法： 如果顶点编号较小（例如 \( n \le 10^5 \)），可以使用 邻接矩阵 （空间 \( O(n^2) \) 可能太大）。 更好的方法是 哈希表 ：对每个顶点 \( u \)，将其邻居集合存入一个哈希表（如 unordered_set ）。构建总复杂度 \( O(m) \)，单次查询平均 O(1)。 这里我们采用： 创建一个数组 unordered_set<int> neigh[u] （或布尔数组的压缩表示），存储 \( u \) 的所有邻居（原始无向边）。 构建时间：\( O(m) \)，查询时间：平均 O(1)。 步骤 4：计数三元环 初始化计数器 count = 0 。 对每个顶点 \( u \)： 遍历 \( u \) 的每个出边邻居 \( v \)（即 \( v \in adj\_dir[ u ] \)）。 对每一对 \( v, w \)（其中 \( v, w \) 都是 \( u \) 的出边邻居，且 \( v < w \) 避免重复）： 检查在原始无向图中，\( v \) 和 \( w \) 是否相连（即 neigh[v].contains(w) 为真）。 如果相连，则 {u, v, w} 构成一个三元环，计数器加 1。 为什么这样不会漏掉三元环？ 在定向后的 DAG 中，每个三元环 恰好有一个顶点 ，它的两条边是入边（另外两个顶点指向它）。我们枚举每个顶点 \( u \) 作为“两条入边的终点”，检查它的两个入边邻居是否相连。根据定向规则，这两个邻居的出边会指向 \( u \)，所以它们同时是 \( u \) 的出边邻居。因此枚举 \( u \) 的所有出边邻居对即可覆盖。 时间复杂度分析 ： 每个顶点 \( u \) 的出度不超过 \( \sqrt{2m} \)，所以检查的出边邻居对数量为 \( O(\sqrt{m}^2) = O(m) \) 级别？不对，是 对所有顶点求和 ： 设 \( d^+(u) \) 为 \( u \) 的出度，则总检查对数为 \( \sum_ {u} \binom{d^+(u)}{2} \le \sum_ {u} (d^+(u))^2 \)。 由于 \( \sum_ {u} d^+(u) = m \)（每条边恰好被定向一次），且 \( d^+(u) \le \sqrt{2m} \)，通过柯西不等式可证明 \( \sum_ {u} (d^+(u))^2 \le \sqrt{2m} \cdot m = O(m \sqrt{m}) \)。 因此总时间复杂度为 \( O(m \sqrt{m}) \)，在一般图中优于 \( O(n^3) \)。 步骤 5：输出结果 最终 count 就是三元环的总数。 算法示例 假设图有 5 个顶点，边集为： (1,2), (1,3), (1,4), (2,3), (2,5), (3,4), (3,5) 度数：deg[ 1]=3, deg[ 2]=3, deg[ 3]=4, deg[ 4]=2, deg[ 5 ]=2。 步骤 2：定向 (1,2)：deg 相等，1 <2，定向 1→2 (1,3)：deg1 <deg3，定向 1→3 (1,4)：deg1>deg4，定向 4→1 (2,3)：deg2 <deg3，定向 2→3 (2,5)：deg2>deg5，定向 5→2 (3,4)：deg3>deg4，定向 4→3 (3,5)：deg3>deg5，定向 5→3 有向邻接表： 1→{2,3} 2→{3} 4→{1,3} 5→{2,3} 步骤 4：计数 u=1：出边邻居 {2,3}，检查 (2,3) 有边 → count=1 u=2：出边邻居 {3}，无对 u=4：出边邻居 {1,3}，检查 (1,3) 有边 → count=2 u=5：出边邻居 {2,3}，检查 (2,3) 有边 → count=3 最终三元环：{1,2,3}, {1,3,4}, {2,3,5}，共 3 个。 关键点总结 定向 降低了出度，将枚举限制在 \( O(\sqrt{m}) \) 以内。 快速查询边 是保证效率的关键，需用 O(1) 数据结构。 算法适用于 无向简单图 （无自环、无重边）。 时间复杂度 \( O(m \sqrt{m}) \)，空间复杂度 \( O(n + m) \)。 这样我们就完成了无向图三元环计数的高效算法讲解。