Let G = (V,E) be a graph with vertices V and edge set E.
Input: G = (V,E)
Output: T = (V, W), where W is a subset of E such that T is a spanning tree of G.
Let W be the empty set. Add edges to W in the following manner: starting at any vertex v in V,
1) If all vertices in V have been visited, halt and return T
2) Choose a vertex u uniformly at random from the set of neighbors of v.
3) If u has never been visited before, add the edge (u,v) to the spanning tree.
4) Set v, the current vertex, to be u and return to step 1.
1) Write a matlab function USTsample that takes a connected graph specified in the form of a 2-by-n matrix E, where n is the number of edges in the graph, and returns an output from the Aldous-Broder algorithm in the form of a 2-by-r matrix T, where r is the number of edges in the tree generated by the algorithm. Each row of E specifies the two vertices that constitute an edge: e.g. if G has an edge between the 5th vertex and 80th vertex, then either [5 80] or [80 5] (but not both) will be a row of E; T is a similar specification of the edges in the spanning tree. Note that we don't pass in or out the vertex sets: we assume that the vertices of G are 1 through m, where you can determine m as the largest number in E.
2) Write a script function that demonstrates your USTsample function:
- In one cell, specify K5, the complete graph on 5 vertices, in the form that USTsample takes as input, and use USTsample to return a spanning tree of K5
- In another cell, visualize K5 and its spanning tree in one plot. You will need coordinates for the vertices of the graph; according to your own preference, assign the coordinates by hand. Plot the vertices of the graph as red dots and the edges of G as gray lines of width 1. Plot the edges of T as thick red lines of width 2.
- Add two cells that repeat the above two steps (of calling USTsample and visualizing the output) for the grid graph on 10 vertices.