寻找图的割点

1. Overview

In this tutorial, we’ll discuss articulation points and how to find them in a graph.

2. Definition

A vertex is said to be an articulation point in a graph if removal of the vertex and associated edges disconnects the graph. So, the removal of articulation points increases the number of connected components in a graph.

Articulation points are sometimes called cut vertices.

The main aim here is to find out all the articulations points in a graph.

3. Example

Let’s take an undirected graph and try to find articulation points simply by following the definition:

Here we’ve got a graph with a vertex set and edge set . Let’s start with the vertex and see if removing it and its and associated edges will disconnect the graph.

In this case, removal of vertex and associated edges and doesn’t disconnect the graph. Therefore, isn’t an articulation point.

But now let’s try vertex and itss associated edges , , , . This divides the graph into two connected components:

• The first component with vertex set and edge set
• The second component with vertex set and edge set

Thus, removing satisfies the articular point definition. Therefore, vertex is an articulation point in .

4. Algorithm to Find All Articulation Points

n this section, we’ll present an algorithm that can find all the articulation points in a given graph.

algorithm ArticulationPoints(G, s):
    // INPUT
    //     G(V, E) = a graph with vertices V and edges E
    //     s = the starting vertex for DFS
    // OUTPUT
    //     Prints the articulation points of G

    Construct the DFS tree of G
    Visited, depth, low -> initialize arrays
 
    Visited[s] <- true
    depth[s] <- d
    low[s] <- d

    for each k in Adj(s):
        if Visited[k] = false:
            ArticulationPoints(k, d + 1)
            low[s] <- min(low[s], low[k])
            if low[k] >= depth[s]:
                if s is not a root node or |children(s)| > 1:
                    print(s + " is an articulation point")

This is a Depth First Search (DFS) based algorithm for finding all the articulation points in a graph. Given a graph, the algorithm first constructs a DFS tree.

Initially, the algorithm chooses any random vertex to start the algorithm and marks its status as visited. The next step is to calculate the depth of the selected vertex. The depth of each vertex is the order in which they are visited.

Next, we need to calculate the lowest discovery number. This is equal to the depth of the vertex reachable from any vertex by considering one back edge in the DFS tree. An edge is a back edge if is an ancestor of edge but not part of the DFS tree. But the edge is a part of the original graph.

After calculating the depth and lowest discovery number for the first picked vertex, the algorithm then searches for its adjacent vertices. It checks whether the adjacent vertices are already visited or not. If not, then the algorithm marks it as the current vertex and calculates its depth and lowest discovery number.

After calculating the depth and lowest discovery number for all the vertices, the algorithms take a pair of vertices and checks whether its an articulation point or not. Let’s take two vertices and . We’re further considering is a parent, and is a child vertex. If the lowest discovery number of is greater than or equal to the depth of , then is an articulation point.

There’s one special case when the root is an articulation point.  The root is an articulation point if and only if it has more then one child in the tree. That’s why we put a checking condition in our algorithm to identify the root of the tree.

5. Running the Algorithm on a Graph

In this section, we’ll take a graph and run the algorithm on the graph to find out the articulation points:

Now we’ll convert the graph to a DFS tree. We’ll start from a vertex and construct the tree as we visit the vertices:

In this case, we started with the vertex and then visited the vertices . After the vertex , we go back and check if there is any vertex adjacent to , which there isn’t.

Similarly, we check for . Vertex has the adjacent vertex , which is not included in the tree. So we include vertex . At this point, we’re done with the construction of the DFS tree.

Notice that there are two dotted edges from vertices to and to . These are the back edges and are not part of the DFS tree.

Next, we’ll calculate the depth and lowest discovery number for all the vertices:

Vertex

Depth Number

Lowest Discovery
Number

A

1

1

B

2

1

C

6

1

D

3

1

E

4

3

F

5

3

The depth number for each vertex is calculated as they are visited in the DFS tree. For example, vertex has a depth number and it denotes that the algorithm visits the vertex one the very first time in the DFS tree. Similarly, the depth number of vertex is . It depicts that the vertex is the second vertex the algorithm visited the DFS tree.

Let’s talk about how the algorithm calculates the lowest discovery number for each vertex. The rule is simple: Search the reachable vertices with the back edge and see in which vertex this back edge lands. The lowest discovery number of the current vertex will be equal to the depth of that vertex where the back edge lands.

Let’s say we want to calculate the lowest discovery number for vertex . The neighbor vertex is , but it doesn’t have any back edge. So the search goes on and reaches vertex . Vertex has a back edge, and it connects to vertex . The lowest discovery number of is equal to the depth of . Therefore the lowest discovery number of is .

We can calculate the lowest discovery number for all other vertices in the DFS tree in a similar way.

Now, to find the articulation points, we need to take a pair of vertices where is the parent of according to the DFS tree. Let’s start with a random pair of vertices where is the parent of .

• Checking condition:

Therefore, there is no articulation point here. Now let’s take another pair where is the parent of .

• Checking condition:
• Checking condition 2:

Therefore, we can conclude that the vertex is an articulation point in the graph .

In this way, we can find out all the articulation points in any given graph.

6. Time Complexity Analysis

The algorithm mainly uses the DFS search with some additional steps. So basically, the time complexity of this algorithm is equal to the time complexity of the DFS algorithm.

In case the given graph uses the adjacency list, the time complexity of the DFS algorithm would be . Therefore, the overall time complexity of this algorithm is .

7. Applications

The concept of articulation points is very crucial in a network. The presence of articulation points in a connected network is an indication of high risk and vulnerability. If a connected network has an articulation point, then a single point failure would disconnect the whole network.

In computer science, one popular problem is to find out the maximum amount of flow passing from a source vertex to a sink vertex. This problem is known as the max-flow min-cut theorem. The concept of articulation point is used here to find the solution.

8. Conclusion

In this tutorial, we’ve presented a DFS-based algorithm to find all the articulation points in a graph.

We also demonstrated an example to verify the algorithm and mentioned a couple of applications of articulation points.