xxx 三元环计数（Triple Counting in Undirected Graphs）
字数 3659 2025-12-19 12:23:10

xxx 三元环计数（Triple Counting in Undirected Graphs）

题目描述
给定一个无向简单图 \(G = (V, E)\)，我们需要计算图中包含多少个三元环（triangle）。一个三元环是指由三个顶点 \(u, v, w\) 组成的集合，使得 \((u,v), (v,w), (w,u)\) 三条边均存在于图 \(G\) 中。

要求：算法的时间复杂度应优于朴素的 \(O(|V|^3)\)（枚举所有三个顶点并检查）。通常输入规模可能很大（顶点数 \(|V|\) 与边数 \(|E|\) 达到 \(10^5\) 量级），需要高效算法。

解题过程循序渐进讲解

步骤1：理解问题与朴素解法

三元环计数是图论中一个经典问题，常用于衡量图的聚集程度（聚类系数）。
最直接的方法是：

  1. 枚举所有三个顶点的组合 \(\binom{|V|}{3}\)。
  2. 对每个组合检查是否两两相连。

时间复杂度：\(O(|V|^3)\)，对于大规模图不可行。

我们需要利用图的稀疏性设计更优的算法。

步骤2：优化思路——定向边技术

一个常用技巧是：将无向图转化为有向无环图（DAG），然后只在 DAG 中寻找特定形式的三元环。

具体步骤：

  1. 对顶点按度排序（或按度与编号结合排序）
    定义顶点 \(v\) 的度 \(d(v)\) 为它的邻居数量。
    我们规定一个全序关系：比较 \(d(u)\) 与 \(d(v)\)，如果度不同，则度小的顶点排在前面；如果度相同，可按顶点编号排序。
    即：

\[ u < v \quad \text{当且仅当} \quad (d(u) < d(v)) \ \text{或} \ (d(u) = d(v) \ \&\& \ u <_{\text{id}} v) \]

这个顺序是确定的，便于后续处理。

  1. 将每条无向边定向
    对于原图中的边 \((u, v)\)，如果 \(u < v\)（按上述顺序），则将边定向为 \(u \to v\)；否则定向为 \(v \to u\)。
    这样我们得到一个有向图 \(G'\)，它满足一个重要性质：每个顶点的出度不超过 \(\sqrt{2|E|}\)。
    原因：假设某个顶点 \(v\) 的出度 \(\mathrm{outdeg}(v) > \sqrt{2|E|}\)，则对每个出边 \(v \to u\)，因为 \(v < u\)，所以 \(d(v) \le d(u)\)。但 \(d(v) \ge \mathrm{outdeg}(v) > \sqrt{2|E|}\)，则 \(d(u) > \sqrt{2|E|}\)，这样的 \(u\) 至少有 \(\mathrm{outdeg}(v)\) 个，它们之间不可能有边（否则会产生更小的度与定向矛盾），这样总边数将超过 \(|E|\)，矛盾。
    因此，\(\mathrm{outdeg}(v) \le \sqrt{2|E|}\)。这个性质保证了算法效率。

步骤3：算法流程

算法分为两阶段：

第一阶段：预处理与定向

  1. 读入图，计算每个顶点的度。
  2. 对每条边 \((u, v)\)，按上述全序规则定向为 \(u \to v\)（若 \(u < v\)）。
  3. 存储两个结构：
    • 原图的邻接表（用于判断两点之间是否有边）。
    • 新有向图的出边表（仅存储从每个顶点出发的边）。

第二阶段：枚举三元环
对每个顶点 \(x\)：

  • 标记 \(x\) 的所有邻居（在原无向图中）为“已访问”。
  • 对 \(x\) 的每个出边邻居 \(y\)（即 \(x \to y\)），再对 \(y\) 的每个出边邻居 \(z\)（即 \(y \to z\)），检查 \(z\) 是否被标记为 \(x\) 的邻居（即原图中 \(x\) 与 \(z\) 是否有边）。
  • 若存在，则 \((x, y, z)\) 构成一个三元环。
  • 最后清除 \(x\) 的邻居标记。

为什么这样能找到所有三元环？
因为每个三元环 \((a,b,c)\) 在原图中是三个顶点两两相连，我们在全序下假设 \(a < b < c\)（排序后）。
边的定向情况一定是：

  • \(a \to b\)
  • \(a \to c\)
  • \(b \to c\)
    因为 \(a\) 是最小的，所以它向 \(b, c\) 连边；而 \(b < c\)，所以 \(b \to c\)。

当我们遍历 \(x = a\) 时，会检查出边 \(a \to b\)，然后从 \(b\) 的出边找到 \(b \to c\)，并检查 \(c\) 是否是 \(a\) 的邻居（原图边 \(a-c\) 存在）。从而发现该三元环。每个环恰好被计数一次，因为只有最小顶点 \(a\) 作为 \(x\) 时才计到。

步骤4：时间复杂度分析

对每个顶点 \(x\)：

  • 标记邻居：\(O(d(x))\)。
  • 遍历 \(x\) 的出边邻居 \(y\)：每个 \(y\) 是出边终点，\(x\) 的出度不超过 \(O(\sqrt{m})\)（其中 \(m = |E|\)）。
  • 对每个 \(y\)，遍历它的出边邻居 \(z\)：\(y\) 的出度也不超过 \(O(\sqrt{m})\)。
  • 检查 \(z\) 是否是 \(x\) 的邻居：用哈希表或布尔数组可 \(O(1)\) 判断。

总复杂度：

\[O\left( \sum_{x} (d(x) + \mathrm{outdeg}(x) \cdot \sqrt{m}) \right) \]

其中 \(\sum d(x) = 2m\)，且 \(\mathrm{outdeg}(x) \le \sqrt{2m}\)，所以：

\[O\left( 2m + n \cdot (\sqrt{2m})^2 \right) = O(m + n \cdot m / ?) \]

更精确分析：

\[\sum_x \mathrm{outdeg}(x) = m \]

每个 \(x\) 对 \(y\) 的遍历量是 \(\mathrm{outdeg}(x) \cdot \mathrm{outdeg}(y)\) 的上限？实际上，整体复杂度为：

\[O(m \cdot \sqrt{m}) = O(m^{1.5}) \]

但实际运行远快于 \(O(n^3)\)，当图较稀疏时（\(m = O(n)\)），复杂度 \(O(n^{1.5})\)。

步骤5：实例演示

考虑图：
顶点：1,2,3,4
边：(1,2), (1,3), (2,3), (2,4), (3,4)

计算度：
d(1)=2, d(2)=3, d(3)=3, d(4)=2

排序（度小的在前，度相同按编号）：顺序 1 < 4 < 2 < 3（度2的顶点1和4，编号小在前；度3的2和3，编号小在前）

定向：

  • 边(1,2)：1<2 → 1→2
  • (1,3)：1<3 → 1→3
  • (2,3)：2<3 → 2→3
  • (2,4)：4<2（因为4<2）→ 4→2
  • (3,4)：4<3 → 4→3

有向图出边：
1: {2,3}
4: {2,3}
2: {3}
3: {}

开始计数：

  • x=1：标记邻居{2,3}。
    出边邻居 y=2：y的出边邻居 z=3。检查 z=3 是否是 x=1 的邻居 → 是，找到环(1,2,3)。
    出边邻居 y=3：y的出边邻居无。
    计数=1。

  • x=4：标记邻居{2,3}。
    出边邻居 y=2：y的出边邻居 z=3，检查 z=3 是邻居 → 找到环(4,2,3)。
    出边邻居 y=3：无出边。
    计数=2。

  • x=2：标记邻居{1,3,4}。
    出边邻居 y=3：y无出边。
    无新环。

  • x=3：无出边，跳过。

总三元环数 = 2，正确（图中有两个三角形：(1,2,3) 和 (2,3,4)）。

步骤6：算法总结

该算法称为 定向边法（或度排序法），是三元环计数的经典 \(O(m^{1.5})\) 解法。它的优点是：

  1. 易于实现。
  2. 无需复杂数据结构（只需邻接表和标记数组）。
  3. 在稀疏图中非常高效。

注意事项：

  • 图必须是无向简单图（无自环、无重边）。
  • 标记数组可使用 vector<int> 或 unordered_set，每轮清除。
  • 如果使用哈希表（如 unordered_set）标记邻居，则注意清除的代价，整体仍是 \(O(m^{1.5})\)，常数稍大。

这样，我们就完成了三元环计数问题的详细讲解。

xxx 三元环计数（Triple Counting in Undirected Graphs） 题目描述 给定一个 无向简单图 \( G = (V, E) \)，我们需要计算图中包含多少个 三元环 （triangle）。一个三元环是指由三个顶点 \( u, v, w \) 组成的集合，使得 \( (u,v), (v,w), (w,u) \) 三条边均存在于图 \( G \) 中。 要求：算法的时间复杂度应优于朴素的 \( O(|V|^3) \)（枚举所有三个顶点并检查）。通常输入规模可能很大（顶点数 \( |V| \) 与边数 \( |E| \) 达到 \( 10^5 \) 量级），需要高效算法。 解题过程循序渐进讲解 步骤1：理解问题与朴素解法 三元环计数是图论中一个经典问题，常用于衡量图的聚集程度（聚类系数）。 最直接的方法是： 枚举所有三个顶点的组合 \( \binom{|V|}{3} \)。 对每个组合检查是否两两相连。 时间复杂度：\( O(|V|^3) \)，对于大规模图不可行。 我们需要利用图的稀疏性设计更优的算法。 步骤2：优化思路——定向边技术 一个常用技巧是： 将无向图转化为有向无环图（DAG） ，然后只在 DAG 中寻找特定形式的三元环。 具体步骤： 对顶点按度排序（或按度与编号结合排序） 定义顶点 \( v \) 的度 \( d(v) \) 为它的邻居数量。 我们规定一个 全序关系 ：比较 \( d(u) \) 与 \( d(v) \)，如果度不同，则度小的顶点排在前面；如果度相同，可按顶点编号排序。 即： \[ u < v \quad \text{当且仅当} \quad (d(u) < d(v)) \ \text{或} \ (d(u) = d(v) \ \&\& \ u <_ {\text{id}} v) \] 这个顺序是确定的，便于后续处理。 将每条无向边定向 对于原图中的边 \( (u, v) \)，如果 \( u < v \)（按上述顺序），则将边定向为 \( u \to v \)；否则定向为 \( v \to u \)。 这样我们得到一个有向图 \( G' \)，它满足一个重要性质： 每个顶点的出度不超过 \( \sqrt{2|E|} \) 。 原因：假设某个顶点 \( v \) 的出度 \( \mathrm{outdeg}(v) > \sqrt{2|E|} \)，则对每个出边 \( v \to u \)，因为 \( v < u \)，所以 \( d(v) \le d(u) \)。但 \( d(v) \ge \mathrm{outdeg}(v) > \sqrt{2|E|} \)，则 \( d(u) > \sqrt{2|E|} \)，这样的 \( u \) 至少有 \( \mathrm{outdeg}(v) \) 个，它们之间不可能有边（否则会产生更小的度与定向矛盾），这样总边数将超过 \( |E| \)，矛盾。 因此，\( \mathrm{outdeg}(v) \le \sqrt{2|E|} \)。这个性质保证了算法效率。 步骤3：算法流程 算法分为两阶段： 第一阶段：预处理与定向 读入图，计算每个顶点的度。 对每条边 \( (u, v) \)，按上述全序规则定向为 \( u \to v \)（若 \( u < v \)）。 存储两个结构： 原图的邻接表（用于判断两点之间是否有边）。 新有向图的出边表（仅存储从每个顶点出发的边）。 第二阶段：枚举三元环 对每个顶点 \( x \)： 标记 \( x \) 的所有邻居（在原无向图中）为“已访问”。 对 \( x \) 的每个 出边邻居 \( y \)（即 \( x \to y \)），再对 \( y \) 的每个出边邻居 \( z \)（即 \( y \to z \)），检查 \( z \) 是否被标记为 \( x \) 的邻居（即原图中 \( x \) 与 \( z \) 是否有边）。 若存在，则 \( (x, y, z) \) 构成一个三元环。 最后清除 \( x \) 的邻居标记。 为什么这样能找到所有三元环？ 因为每个三元环 \( (a,b,c) \) 在原图中是三个顶点两两相连，我们在全序下假设 \( a < b < c \)（排序后）。 边的定向情况一定是： \( a \to b \) \( a \to c \) \( b \to c \) 因为 \( a \) 是最小的，所以它向 \( b, c \) 连边；而 \( b < c \)，所以 \( b \to c \)。 当我们遍历 \( x = a \) 时，会检查出边 \( a \to b \)，然后从 \( b \) 的出边找到 \( b \to c \)，并检查 \( c \) 是否是 \( a \) 的邻居（原图边 \( a-c \) 存在）。从而发现该三元环。每个环恰好被计数一次，因为只有最小顶点 \( a \) 作为 \( x \) 时才计到。 步骤4：时间复杂度分析 对每个顶点 \( x \)： 标记邻居：\( O(d(x)) \)。 遍历 \( x \) 的出边邻居 \( y \)：每个 \( y \) 是出边终点，\( x \) 的出度不超过 \( O(\sqrt{m}) \)（其中 \( m = |E| \)）。 对每个 \( y \)，遍历它的出边邻居 \( z \)：\( y \) 的出度也不超过 \( O(\sqrt{m}) \)。 检查 \( z \) 是否是 \( x \) 的邻居：用哈希表或布尔数组可 \( O(1) \) 判断。 总复杂度： \[ O\left( \sum_ {x} (d(x) + \mathrm{outdeg}(x) \cdot \sqrt{m}) \right) \] 其中 \( \sum d(x) = 2m \)，且 \( \mathrm{outdeg}(x) \le \sqrt{2m} \)，所以： \[ O\left( 2m + n \cdot (\sqrt{2m})^2 \right) = O(m + n \cdot m / ?) \] 更精确分析： \[ \sum_ x \mathrm{outdeg}(x) = m \] 每个 \( x \) 对 \( y \) 的遍历量是 \( \mathrm{outdeg}(x) \cdot \mathrm{outdeg}(y) \) 的上限？实际上，整体复杂度为： \[ O(m \cdot \sqrt{m}) = O(m^{1.5}) \] 但实际运行远快于 \( O(n^3) \)，当图较稀疏时（\( m = O(n) \)），复杂度 \( O(n^{1.5}) \)。 步骤5：实例演示 考虑图： 顶点：1,2,3,4 边：(1,2), (1,3), (2,3), (2,4), (3,4) 计算度： d(1)=2, d(2)=3, d(3)=3, d(4)=2 排序（度小的在前，度相同按编号）：顺序 1 < 4 < 2 < 3（度2的顶点1和4，编号小在前；度3的2和3，编号小在前） 定向： 边(1,2)：1 <2 → 1→2 (1,3)：1 <3 → 1→3 (2,3)：2 <3 → 2→3 (2,4)：4<2（因为4 <2）→ 4→2 (3,4)：4 <3 → 4→3 有向图出边： 1: {2,3} 4: {2,3} 2: {3} 3: {} 开始计数： x=1：标记邻居{2,3}。 出边邻居 y=2：y的出边邻居 z=3。检查 z=3 是否是 x=1 的邻居 → 是，找到环(1,2,3)。 出边邻居 y=3：y的出边邻居无。 计数=1。 x=4：标记邻居{2,3}。 出边邻居 y=2：y的出边邻居 z=3，检查 z=3 是邻居 → 找到环(4,2,3)。 出边邻居 y=3：无出边。 计数=2。 x=2：标记邻居{1,3,4}。 出边邻居 y=3：y无出边。 无新环。 x=3：无出边，跳过。 总三元环数 = 2，正确（图中有两个三角形：(1,2,3) 和 (2,3,4)）。 步骤6：算法总结 该算法称为 定向边法 （或度排序法），是三元环计数的经典 \( O(m^{1.5}) \) 解法。它的优点是： 易于实现。 无需复杂数据结构（只需邻接表和标记数组）。 在稀疏图中非常高效。 注意事项： 图必须是无向简单图（无自环、无重边）。 标记数组可使用 vector<int> 或 unordered_set ，每轮清除。 如果使用哈希表（如 unordered_set ）标记邻居，则注意清除的代价，整体仍是 \( O(m^{1.5}) \)，常数稍大。 这样，我们就完成了三元环计数问题的详细讲解。