Question

Problem 1. (15 points) Consider an undirected connected graph G = (V, E) with edge costs ce > 0 for e € E which are all distinct. (a) [8 points). Let E' CE be defined as the following set of edges: for each node v, E' contains the cheapest of all edges incident on v, i.e., the cheapest edge that has v as one of its endpoints. Is the graph (V, E') connected? Is it acyclic? For both questions, provide a proof or a counter-example with explanations. (b) (7 points). Consider the following outline for an algorithm, which starts with an empty set T of edges: Let E' contain the cheapest edge out of each connected component of (V,T). Add E' to T, and repeat until (VT) is connected. Show that this algorithm outputs a minimum spanning tree of , and can be implemented in time 0(m logn). Hints: • Each iteration of this algorithm can be viewed as applying the operation from part (a) on a “contracted graph”, where each connected component of (V,T) corresponds to a node. • If you want, you are welcome to use the efficient implementation of the Union-Find data structure which supports Find and Union in logarithmic time, as described in Chapter 4.6 of the KT book. However, this implementation is not necessary, and focusing on it may mislead you from the basic idea. • We recommend thinking about how many iterations it will take until (V,T) is connected.

Other answer is incorrect

Answer 1

a. Removing the back edge will result in a graph with no back edges, and thus a graph with no cycles (as every graph with at least one cycle has at least one back edge). Notice that a graph can have two cycles but a single back edge, thus removing some edge that disrupts that cycle is insufficient, you have to remove specifically the back edge. For example, in graph G = (V, E) = ({a, b, c}, {(a, b),(b, c),(a, c),(c, a)}), there are two cycles [a, b, c, a] and [a, c, a], but only one back edge (c, a). Removing edge (b, c) disrupts one of the cycles that gave rise to the back edge ([a, b, c, a]), but another cycle remains, [a, c, a].