'What are the articulation points of this directed graph?
5 nodes in this directed graph.
Edges:
1 -> 2
2 -> 3
2 -> 4
4 -> 5
(Graphical image : http://i.imgur.com/hafBv.jpg )
Am I correct in thinking that the articulation points are node 2 and 4 ? (If you remove node 2 or node 4, the graph becomes disconnected)
But the definition I've seen everywhere says something similar to:
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.
How does this work for a directed graph? For example, Node 3 does not have a back edge to a node higher in the DFS tree than 2. Does this classify Node 3 as an articulation point? But its removal does not cause the graph to be broken into 2 or more pieces (That is my layman definition of an articulation node).
Solution 1:[1]
Disclaimer: My memory is vague.
Directed graphs have three kinds of connectedness.
"Strongly connected" if there is a path from every vertex to every other vertex, "Connected" if there is a path between any two nodes, but not in both directions. "Weakly connected" if the graph is only connected if the arcs are replaced with undirected arcs.
eg 1->2 , 2->3 , 3->1 Strongly connected, you can get from every node to every other node
1->2 , 2->3 You can't get from 3 to 1 but you can from 1 to 3 so it's connected
1->2 , 3->2 There is no way to get from 1 to 3 or from 3 to 1, so it's only weakly connected.
What nodes are articulation points depends on what kind of connectedness you are considering.
Your graph is only weakly connected since there's no way to get from 3 to 4 or from 4 to 3. Which would mean that the only way it makes sense to talk about articulation points is if you treat the arcs as undirected. In which case 2 and 4 would be the articulation points, as you said.
Solution 2:[2]
Articulation point should always have children and parent. This is something that is missing from your definition and makes nodes 1 and 3 articulation points whilst they are not.
Also note that in your reasoning for node 3 you consider the node itself not its children. If you apply the definition carefully you will see that you should consider the children instead. In your case - empty set and, with the extended by me definition, 3 is no longer articulation point.
Solution 3:[3]
Node 3 does not have a back edge to a node higher in the DFS tree than 2
Node 3 doesnt have children, so it cannot be an articulation point (from def). If we put this definition in the context of a directed tree, then the articular points are all the points except the root and the leaf node
Solution 4:[4]
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.
Solution 5:[5]
The definition of articulation is not as clear as in case of undirected graphs. However if we choose two particular nodes: source and sink and call any point that must occur on the path from source to sink articulation point, the definition is clear.
I call them unavoidable points and have got simple solution for finding them on my GitHub
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow
| Solution | Source |
|---|---|
| Solution 1 | Spike |
| Solution 2 | Boris Strandjev |
| Solution 3 | UmNyobe |
| Solution 4 | Guru Charan |
| Solution 5 | vSzemkel |