0

嗨,所有图论专家:)

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

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

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

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

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

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

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

示例共享图

4

2 回答 2

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。

于 2016-01-21T06:03:10.580 回答
0

找到一种算法来计算从当前节点到所有其他节点的最短路径的长度。对每个节点进行迭代。存储结果并使用它们来避免对同一路径重复相同的计算。

将上一段中的“计算路径”替换为“计算间接份额”,您就有了一个算法。

于 2016-01-21T02:38:00.503 回答