algorithm - 这个有向图的接合点是什么？

Question

此有向图中的 5 个节点。

边缘:

1 -> 2

2 -> 3

2 -> 4

4 -> 5

(图形图像:http://i.imgur.com/hafBv.jpg)

我认为关节点是节点 2 和 4 是否正确？(如果删除节点 2 或节点 4，图形将断开连接)

但是我到处都看到的定义是这样的:

a node u is an articulation point, if for every child v of u, there is no back edge from v to a node higher in the DFS tree than u.

这对于有向图是如何工作的？例如，节点 3 在 DFS 树中没有比节点 2 更高的节点的后缘。这是否将节点 3 分类为关节点？但它的删除不会导致图形被分成 2 个或更多部分(这是我对关节节点的外行定义)。

Answer 1

免责声明:我的内存很模糊。

有向图具有三种连通性。

如果从每个顶点到每个其他顶点都有一条路径，则为“强连接”，如果任意两个节点之间有一条路径，但不是双向的，则为“已连接”。“弱连通”，如果仅当弧被替换为无向弧时图才连通。

例如1->2 , 2->3 , 3->1强连接，可以从每一个节点到每一个其他节点

1->2 , 2->3你不能从 3 到 1，但你可以从 1 到 3，所以它是连通的

1->2 , 3->2没有办法从 1 到 3 或从 3 到 1，所以它只是弱连接。

哪些节点是连接点取决于您正在考虑的连接类型。

您的图只有弱连接，因为无法从 3 到 4 或从 4 到 3。这意味着谈论关节点唯一有意义的方法是将弧线视为无向的。如您所说，在这种情况下，2 和 4 将是关节点。