- Home
- Uncategorized
- CS180 Homework 4

$30.00

Category: Uncategorized

Description

5/5 - (5 votes)

1. Consider an undirected graph that weights of edges are distinct. We can define an order on the set of

spanning trees of the graph as follows: each spanning tree has n 1 edges, by sorting the weights of all

n 1 tree edges in the increasing order, we obtain a tuple (w1,…, wn1) where w1 < w2 < ... < wn1. We
can easily define a lexicographic order on tuples by imagining that each tuple is a word with n 1 letter.
More precisely, we say tuple (w0
1,..., w0
n1) is bigger than tuple (w1,..., wn1) if for the smallest index i at
which w0
i 6= wi, we have w0
i > wi. We say tree T1 > T2 if T1’s tuple is lexicographically bigger than T2’s

tuple. We define the lexicographically minimum tree to be the smallest tree in this ordering of trees. Prove

that the lexicographically minimum tree is a minimum spanning tree.

2. Given an undirected graph with distinct weights. Consider a spanning tree for the graph: given any pair of

vertices u and v, the tree can be used to return a path between u and v such that maximum-weight edge

on the path has a smaller weight than the maximum-weight edge of any other path between u and v.

(a) Prove that the spanning tree with the above property is the minimum spanning tree (mst).

(b) We define a order between two paths A and B. We sort the weights of edges in the decreasing order and

A = {w1, w2,…, wi}, B = {w0

1, w0

2,…, w0

j

}. We say A is bottleneck-smaller than B, if the first different

weight edge in A has smaller weight than the edge in B, more precisely if for the smallest index k

in A at which w0

k 6= wk, we have wk