如何从电阻网络中去除环路

Question

如何从电阻网络中去除环路

3

我有一个电阻网络，用一个无向图表示，它的边代表电阻值。一些节点称为驱动器，一些节点称为汇点，其他节点是内部节点。目标是计算每个驱动器到每个汇点的有效电阻。图可以有循环，星形三角形网络等。所以可以使用以下公式来计算有效电阻。

注意，如果图中没有循环，则简单的DFS遍历将给出每个汇点的有效驱动器电阻。但是，如果有循环，则必须删除循环。一种方法是将图复制到临时图中，然后使用上述公式从临时图中删除除驱动器和汇点之外的所有节点。对于所有驱动器汇点对执行此操作，但是这种方法对于大型密集图非常耗费时间。我通过将图存储在tcl哈希表或std::tr1::unordered_map中而获得高运行时间。

您有关于计算每个驱动器到每个汇点电阻的有效方法吗？

我有一个低效的解决方案：

- 对于每个驱动器和每个汇点， - 将原始图复制到临时图中， - 然后使用我上面提到的维基百科文章从临时图中删除除源和目标之外的所有节点。 - 最后的临时图将给出该源和该汇点之间的有效电阻。

这种解决方案的运行时间对于大型输入数据是不可接受的，因此我需要更好的解决方案。

- user1592989

2

正确的方法应该是执行节点分析而不是图形转换。 - timrau

我没有查看维基百科文章，但为什么不计算生成树呢？例如，深度优先搜索产生的那个？ - mrk

我认为你可以将这个问题建模为一个“最大流”问题，其中流量是阻力，并计算路径。 - Bill

我不知道如何在这个问题上执行节点分析，因为只给出了电阻网络而没有电压。此外，我认为生成树和最大流不能解决这个问题。你能解释一下这些方法如何解决我的问题吗？ - user1592989

2

将源节点指定为1V，汇节点指定为0
进行节点分析，得到总电流I
R = V / I = 1 / I

- timrau

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- timrau · Accepted Answer

计算每个驱动器到每个接收器的有效电阻时，无需进行图形转换。相反，您可以：

对于每对驱动器和接收器，将驱动器节点分配为1V，接收器节点分配为0
执行nodal analysis，该分析仅需要线性方程式的制定。然后您可以获得从驱动器到接收器的电流 I。
根据定义，有效电阻 R = V / I = 1 / I。