- #1

- 2

- 0

## Homework Statement

Let G = (V,E) be a graph with vertices V and edge set E.

Aldous-Broder algorithm:

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.

## Homework Equations

Aldous-Broder algorithm