2

此有向图中的 5 个节点。

边缘：

1 -> 2

2 -> 3

2 -> 4

4 -> 5

（图形图像：http: //i.imgur.com/hafBv.jpg）

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

但是我在任何地方看到的定义都类似于：

一个节点 u 是一个关节点，如果对于 u 的每个子 v，从 v 到 DFS 树中比 u 更高的节点都没有后边。

这对有向图有什么作用？例如，节点 3 没有到 DFS 树中高于 2 的节点的后边。这是否将节点 3 归类为关节点？但它的删除不会导致图形被分成 2 个或更多部分（这是我对关节节点的外行定义）。

4

4 回答 4

0

关节点应始终有孩子和父母。这是您的定义中缺少的东西，并且使节点 1 和 3 关节点，而它们不是。

另请注意，在您对节点 3 的推理中，您认为节点本身不是其子节点。如果你仔细应用这个定义，你会发现你应该考虑孩子。在您的情况下-空集，并且根据我的扩展定义， 3 不再是关节点。

于 2012-04-26T08:36:34.160 回答
0

Node 3 does not have a back edge to a node higher in the DFS tree than 2

节点 3 没有子节点，因此它不能是关节点（来自 def）。如果我们把这个定义放在有向树的上下文中，那么关节点就是除了根节点和叶节点之外的所有点

于 2012-04-26T08:37:36.937 回答
0

免责声明：我的记忆很模糊。

有向图具有三种连通性。

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

eg 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 将是关节点。

于 2012-04-26T09:06:14.423 回答
0

but when we follow the method we used to solve the undirected graph we get the respected (num,low) values for nodes are node-1(1,1) 2 (2,2) ,node 3 (3,3), node 4(4,4).node 5(5,5). so following the def of articulation point and finding the node with 2 children and satisfying the rule (low(child)>=num(node)) we get only the node 2 so that is the articulation point . but the theory can be applied because it is still a connected graph i.e where every node is reachable but when we are finding we had to take care of tree and back edges and the rest is same as that of undirected graph.

于 2015-11-17T19:42:50.127 回答