algorithm - 图上的谜题

Question

给定一个无向图 G=(V,E)，每个节点 i 与“Ci”个对象相关联。在每一步，对于每个节点 i，Ci 对象在 i 的邻居之间平均分配。经过K步后，输出前5个节点中拥有最多对象的对象个数。

这是一步中发生的事情的一个例子:
A的对象被B和C平分。
B的对象被A和C平分。
C的对象由A和B平分。

一些约束:|V|<10^5, |E|<2*10^5, K<10^7, Ci<1000

我目前的想法是:用矩阵表示每一步的变换。这个问题转化为矩阵的幂的计算。但考虑到 |V|，这个解决方案太慢了可以是 10^5。

Is there any faster way to do it?

Answer 1

单步矩阵方程如M x = x'，其中x是当前节点内容的向量，x'是一步之后的内容。即，x' = M x。之后步骤的内容是 x"= M x' = M(M x)。接下来是 M 的示例，其中图形的邻接矩阵显示在左侧。标题为 的列#nbr 是节点 a、b ... e 的邻居数。矩阵 M 是从邻接矩阵中通过将每个 1 替换为等于中的个数的分数而形成的同一列。

  a b c d e  #nbr          matrix M
a 0 0 1 1 0   2       0   0  1/3 1/4  0
b 0 0 0 1 0   1       0   0   0  1/4  0
c 1 0 0 1 1   3      1/2  0   0  1/4 1/2
d 1 1 1 0 1   4      1/2  1  1/3  0  1/2
e 0 0 1 1 0   2       0   0  1/3 1/4  0

要从初始内容 x 开始执行 K 个步骤，只需计算 (M^K) x。使用 exponentiation method这需要 lg K 矩阵乘法，lg 表示以 2 为底的对数。由于矩阵乘法通常具有 O(n^3) 复杂度，因此此方法为 O(lg K * n^3) 如果直接实现，或者如果使用 Coppersmith/Winograd 算法则为 O(lg K * n^2.376)。复杂度可以降低到 O(n^2.376) – 也就是说，我们可以删除 lg K 乘数 – by diagonalizing M 转化为 (P^-1)AP 形式，从 M^K = (P^-1)(A^K)P，A^K 是一个O(n lg K) 操作，整体给出 O(n^2.376)。对角化通常花费 O(n^3)，但为 O(n^2.376) using Coppersmith/Winograd algorithm .