'trim' 一张图的算法

Question

我正在尝试创建一种算法来计算给定的带加权边的无向图的总阻力。该算法还将被赋予一个起始节点和一个结束节点，它们将代表连接到电源的终端。例如，顶部的图表以起始节点 1 结束于节点 6 将表示 this circuit

         (3)
          |
          |6 
     3    | 
(2)------(4)
 |        |
 |5       |1
 |        |
 |    3   |   1
(1)------(5)------(6)

如您所知，6 欧姆电阻在这种情况下并不重要，因为如果在节点 1 和 6 之间施加电压，电流将不会流过它。所以，我想我应该首先所有 'trim' 这个图表。下面是这个过程的解释：

裁剪图基本上就是把图中不能包含在起始节点和结束节点之间的路径中最多经过任何一个节点一次的部分。

   4                 4              
   |                /|
   |               / |
2--3              2--3              2--3
|  |              |  |              |  |
|  |              |  |              |  |
1--5--6           1--5--6           1--4--5

  (1)               (2)               (3)

例如，在图(1)中，节点4应该被修剪，因为在1和6之间的任何路径中，访问节点4意味着访问节点 3 至少两次，因为没有来自节点 4 的路径不会再次访问节点 3。如果这个图被修剪，它将变成图(3)。但是，如果图 (2) 被修剪，它不会改变，因为在从 1 到 6 的路径上可以访问所有节点，包括节点 4.

那么，我如何设计一种算法来修剪具有给定起始和结束节点的图？

编辑： 所以，我已经了解了 maxflow / mincut 问题，看起来这可以用来解决这个问题。我还没有尝试过，但如果我能设法使用流程来完成，我会 post 进行另一次编辑。

Answer 1

只需删除所有只有一条边的节点（不包括两个结束节点）。

但这不考虑节点 "beyond" 结束节点。如果在您的原始图中我们想要计算节点 5 和 6 之间的电阻，那么我们不需要任何其他节点（节点 1、2、3 和 4 都是无关紧要的）。

要真正删除所有不相关的节点，您必须找到两个结束节点之间的所有不同路径，并删除不属于任何这些路径的所有节点。

Answer 2

找到双连通组件树。
任何不在树中从 s 到 t 的路径上的节点（或路径上的部分组件）都可以删除。

时间复杂度是线性的。

双连通分量：https://en.wikipedia.org/wiki/Biconnected_component

Answer 3

这可能是一个可能的解决方案：

如果从一个节点（比如 v）开始，如果我们可以同时到达没有共同顶点的源节点和终端节点，那么在计算总阻力时必须考虑该节点。

我的意思是，假设从 v 到源的路径之一是 (v, a1, a2, a3, a4, ..., source) 从 v 到终端的路径是 (v, b1, b2, b3, ..., terminal)

那么如果这些的交集给出零个元素，那么节点v不能被修剪。否则可以省略。

所以我们可以有以下两种解决方案： 1. 从每个顶点做一个深度优先搜索，检查路径是否有一些共同的顶点。

找到图中所有的桥。您可以在这里查找：https://en.wikipedia.org/wiki/Bridge_(graph_theory)

这里给出了查找图中所有桥的方法：https://www.geeksforgeeks.org/bridge-in-a-graph/

如果在删除桥边后，源顶点和终端顶点在同一个连通分量中，则可以从图中修剪连通分量另一侧的所有节点。例如：在图（1）中，只有一个桥3-4.

如果我们删除它，我们会得到两个连通分量 (1,2,3,5,6) 和 (4)。我们可以看到1和6都在同一个连通分量中，因此所有其他连通分量节点（这里只有编号为4的节点）都可以被修剪。

'trim' 一张图的算法

Algorithm to 'trim' a graph

algorithm

graph-theory

graph-traversal

graph-algorithm