Problem 1: Prove that the graph obtained from Kn by deleting one edge has (n 2)nn3 spanning trees.
Problem 2: Let G be a connected graph in which each edge has a positive weight/length. Recall that Dijkstras algorithm takes a vertex s of G and creates a shortest path spanning tree T from s. If T is a shortest path spanning tree from s, then dT(s,v) = dG(s,v) for all v V (G).
We can also create a shortest path spanning tree from a point on an edge. Consider edge uv of G and any point on uv. Let T be a shortest path spanning tree from such that dT(,v) = dG(,v) for all v V (G).
There are an infinite number of points along any single edge, and we can create a shortest path spanning tree from each of these points. However, there are only a finite number of possible spanning trees of G (at most nn2 from Mondays class); therefore, there will be many points and 0 for which the shortest path spanning trees T and T0 are identical.
Furthermore, lets say two spanning trees T1 and T2 are equivalent if for all x V , dT1(u,x) = dT2(u,x) and dT1(v,x) = dT2(v,x). Let S be a set of spanning trees. Lets define a class of equivalent trees to be a maximum subset of S such that all trees in the subset are equivalent to each other.
Let Suv be the set of all shortest path spanning trees that are rooted at a point along the edge uv. How many separate classes of equivalent spanning trees can there be in Suv? Prove your answer.
Reviews
There are no reviews yet.