algorithm - 如何计算随机图生成的期望值

Question

您好，这是我的第一个问题。遇到一个算法和概率的作业，找不到线索去计算。

问题:计算图中三角形的数量:给定一个无向图 G = (V, E)，G 中的三角形是大小为 3 的团(形式上，一组节点 {u, v, w} 是 G 中的三角形，如果(u, v), (v, w), (u, w) 都是 G 的边)。考虑以下用于近似图中三角形数量的算法。首先构造一个采样图G' = (V, E') 如下。 G' 的顶点集与 G 的顶点集相同。对于每个 e ∈ E，将 e 放入 E' 的概率为 p(假设 p 为 0.1)。在这个新的采样图 G' 中，计算三角形的数量并令 T' 为 G' 中的三角形数量(假设您已经给出了一个黑盒子例程来计算 G' 中的三角形数量)。则输出T̃= T'/p。证明T̃=T ,T的期望值是原图G的三角形数。

我很困惑 G 或 G' 中形成三角形的边不是独立的，因为 G 中的两个相邻三角形可能共享边。并不是 G 中的所有顶点对都可以在 G' 中形成一条边，只有那些在 G 中的边才会与 p 一起出现在 G' 中。我很难想到G或G'中边数与三角形数的关系。

希望有人能给我一些提示，即使不是整个解决方案也可以。

Answer 1

the edge in G or G' to form a triangle is not independent since two adjacent triangles in G might share the edge

没关系。期望之和是对总和的期望，而不考虑相关性，因此您可以单独推理三角形。 (更高的时刻，如果你关心分析这个算法的估计质量，会更棘手。)