13. Given a graph G as below (a) Write out the DFS and BFS sequences, respective

Question

13. Given a graph G as below (a) Write out the DFS and BFS sequences, respectively. (starting from node A and assume neighbor node are visited in alphabetic order, e.g., B is visited before C) (b) Show the articulation points in this graph. (c) How to determine whether a node is an articulation point? (d) Show the biconnected components. (e) Find minimum-cost spanning tree. Specify the name of the algorithm that you use. 13. Given a graph G as below (a) Write out the DFS and BFS sequences, respectively. (starting from node A and assume neighbor node are visited in alphabetic order, e.g., B is visited before C) (b) Show the articulation points in this graph. (c) How to determine whether a node is an articulation point? (d) Show the biconnected components. (e) Find minimum-cost spanning tree. Specify the name of the algorithm that you use. 13. Given a graph G as below (a) Write out the DFS and BFS sequences, respectively. (starting from node A and assume neighbor node are visited in alphabetic order, e.g., B is visited before (b) Show the articulation points in this graph. (c) How to determine whether a node is an articulation point? (d) Show the biconnected components. (e) Find minimum-cost spanning tree. Specify the name of the algorithm that you use.

Explanation / Answer

a) The BFS and DFS sequences are given below, we will use the following method to find out the sequences from the graph

Breadth first search:

   unmark all vertices

    choose some starting vertex x

    mark x

    list L = x

    tree T = x

    while L nonempty

    choose some vertex v from front of list

    visit v

    for each unmarked neighbor w

        mark w

        add it to end of list

        add edge vw to T

the sequence for BFS is ABCDEF

Depth first search

preorder(node v)

    {

       visit(v);

      for each child w of v

        preorder(w);

    }

dfs(vertex v)

    {

    visit(v);

    for each neighbor w of v

        if w is unvisited

        {

        dfs(w);

        add edge vw to tree T

        }

    }

The sequence for DFS is DBEAGCF

b) Articulation Points

Articulation Points is also known as cut point or vertices in a graph

A vertex in an undirected connected graph is an articulation point (or cut vertex) if removing it (and edges through it) disconnects the graph.

Articulation points represent vulnerabilities in a connected network – single points whose failure would split the network into 2 or more disconnected components.

They are useful for designing reliable networks.

For a disconnected undirected graph, an articulation point is a vertex removing which increases number of connected components.

c) the node is in articulation point Node A B C are in ASrticulation point

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.