(Q). Let T = (V,E) be an (undirected) tree whose edge weights are arbitrary positive real numbers. Design an O(n) time algorithm for computing a maximum matching in T, where n = |V|. (You may look at page 1135 of Cormen, Leiserson, Rivest, and Stein for the de?nition of maximum matching on undirected graphs.)
(Q): Let G = (V,E) be a weighted directed graph (which can contain cycles), with n = |V|, m = |E|, and each edge weight being a positive real number. Assume that the graph G has been stored in the computer. We have studied in class a dynamic programming algorithm for computing the length of a k-link shortest path from a vertex s to another vertex t in G in O(k(m + n)) time and O(n) additional space (i.e., the space is in addition to that for storing G). Design an O(n) additional space algorithm for reporting an actual k-link shortest path from a vertex s to another vertex t in G (in addition to the length of such a path), and make your algorithm run as fast as possible (in the big-O notation).