Find all the articulation points in the graph in Figure 985

Find all the articulation points in the graph in Figure 9.85. Show the depth-first spanning tree, and the values of Num and Low for each vertex. Figure 9.85 is below. For your DFS, start at F, and when you have a choice of adjacent vertices search them in alphabetical order. Thus, from F you would first go to C.

Solution

Articulation point: Removal of it will disconnect the graph.

C F E

depth first spanning tree with first vertex A:

A D C B E F G H J K I

depth first spanning tree with first vertex B:

B C A D E F G H J K I

depth first spanning tree with first vertex C:

C A D B E F G H J K I

depth first spanning tree with first vertex D:

D A C B E F G H J K I

depth first spanning tree with first vertex E:

E B C A D F G H J K I

depth first spanning tree with first vertex F:

F G E B C D A H J K I

depth first spanning tree with first vertex G:

G F E B C D A H J K I

..