Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

MA214 Algorithms and Data Structures

2023/24

Exercises 8

(Graph searching, minimum spanning trees)

Exercise 8.1.  Properties of Depth-First Search                                                           3 pts

(a) Give a counterexample to the claim that if a directed graph G contains a path from u to v, and if u.d < v.din a depth-first search of G, then v is a descendant of u in the depth-first forest produced.

(b) Give a counterexample to the claim that if a directed graph G contains a path from u to v, then any depth-first search must result in v.d < u.f.

Exercise 8.2.  Minimum spanning trees                                                                     3 pts

(a) Let (u, v) be a minimum-weight edge in a connected graph G.  Show that (u, v) belongs to some minimum spanning tree of G.

(b) Let e be a maximum-weight edge on some cycle of connected graph G  =  (V, E). Prove that there is a minimum spanning tree of G′  =  (V, E − {e}) that is also a minimum spanning tree of G; that is, there is a minimum spanning tree of G that does not include e.

Exercise 8.3.  Prim’s algorithm                                                                                  4 pts

(a) Using the figures from the lecture as a template, depict the execution of Prim’s algorithm on the following undirected graph G = (V, E) starting from root r = a. Suppose that vertices appear in the adjacency lists in alphabetical order.

(b) Suppose that we represent the graph G = (V, E) as an adjacency matrix. Describe a simple version of Prim’s algorithm for this case that runs in O(n2 ) time, where n is the number of vertices. A simple description of the algorithm suffices, you do not need to implement it in Python.