java - (经济)份额图的图算法

Question

大家好所有的图论专家:)

我目前正面临一个我自己无法解决的算法问题。

我必须在已经包含直接股份的有向图中找到每家公司彼此之间的所有间接股份(参见图片中的一个非常简单的示例)。

我必须从有向图开始，其中节点是公司，边是这些公司之间的直接份额。该算法现在必须将所有节点之间的间接份额附加到边(这包括在算法期间向图中添加新边)。

间接份额被定义为所有中间直接份额的乘积。如果图中只有节点 A、B 和 C，则只有一个间接共享，即从 A 到 C 的一个。

间接(A，C)= 100% * 80% = 1 * 0.8 = 0.8 = 80%

现在我需要一个算法来计算整个图的这些份额。图中没有特定的起点，它可能包含各种大小的圆(在示例中 C 和 D 之间只有一个“直接”圆)和一对节点之间的多条路径(如路径从 C 到 E)。

如果有人可以帮助我提供一些伪代码或可能算法的描述，那将非常有帮助。我已经在图论书籍和互联网上搜索算法，但我能找到的都是用于查找最短路径、所有路径或访问图的所有节点的标准算法。但是我找不到一种机制来计算这种图边权重的数学组合。

example share graph

Answer 1

让我们通过观察如果给定公司收到 1 美元并且所有收到的钱都根据他们的所有权转移给股东会发生什么来实现所有权。然后，当所有的货币流通都停止时，我们将计算所有权比例为最终收到的货币比例。

最简单的方法是首先计算每家公司收到的总金额，这将为我们提供一组线性方程式，其解将告诉我们当 1 美元汇出时每家公司收到的总金额一审给A公司。

假设 A 和 B 拥有彼此 1/2 的股份作为示例。那么 a = 1 + b/2 和 b = a/2，其中 a 是 A 收到的总金额，b 是 B 收到的总金额 - 因为 A 将获得 1 美元和 1/2 B 看到了，B 将得到 A 看到的 1/2。这求解为 a = 1 + a/4 或 a = 4/3 和 b = 2/3。如果我们遵循分配的每个步骤，那么 A 收到 1 并将 1/2 发送给 B，B 发送 1/4 给 A，B 发送 1/8 给 B，B 发送 1/16 给 A... 所以 A 得到 1 + 1/4 + 1/16 + ... = 4/3。

所以 A 总共看到 4/3，B 总共看到 2/3 - 但是 A 和 B 必须传递他们收到的所有内容的 1/2，所以 A 最终得到 2/3，B 最终得到1/3，这是有道理的 - 传入的 1 美元被准确地计算在内。

如果我们将金钱的分配作为所有权的指示，那么 A 拥有自己的 2/3，B 拥有另外 1/3。