Problem 3. (35 points) Answer the following questions about MST and shortest paths in the given graph G. Your answers should be short yet indicate your thought process. No credit will be given for just an answer without explanation: (a) In graph G, when we examine every cycle in the graph, is it true that the longest edge on the cycle is never in the MST? (b) Imagine that we modify the graph G in the following way: for every vertex pair that does not share an edge, we construct an edge of weight 1, and for all vertex pairs that do share an edge, we change the edge weights to 1 (now we have a complete graph where all edges weigh 1). How many minimum spanning trees does the newly constructed graph have? (c) If Prim's algorithm starts building the tree from vertex A, and currently, vertices and F are in the tree, what is the next vertex to be added to MST and why? (d) If Djikstra's algorithm starts from A, and currently A,F,C,E are in the shortest-path tree, what vertex is added next, and what is its final short- est path distance to A? Does this newly added vertex help any future vertex decrease its total shortest path to A, and if yes, which and by how much? (e) How many comparison operations would Floyd-Warshall algorithm require on the given graph G? Problem 2. (12 points Determine which statements below are true multiple slakmonts potentially truc) about the DFS traversal of graph G starting from var tex A (no explanation needed (a) When choosing among a group of neighbors which to visit next, if DFS uses the alphabetical order to break ties reg starting from A, we preter vertex over L'or), then DFS visits before it visits ib) Vertex A is not processed until all the other vertices in the graph have been (c) (A general DES question, not just the given graph) If DIS stumbles upon a vortex that is already discovered, this signifies the graph can't be a tree. Problem 3. (38 points) Answer the following questions about MST and shortest puth in the given graph G. Your answers should I short yel indicate your thought process. No credit will be given tor jest an answer without explanation: (a) In graph G. when we camine every cycle in the graph, is it true that the Ingest edge on the cycle is never in the MST th) Imagine that we modify the graph G in the following way for every vertex pair that does not share an edge, we construct an edge of weight I, and for all vertes per al do care and we change the edge weights to now we have a complete graph where all edges weigh 1). How many minimum spanning trees does the newly constructed graph have? (c) Ir Prim's algorithm starts building the tree from vertex A, and currently, vertices and are in the tree. what is the next vertex to be added to MST d) If Djikstra's algorithm starts from A, and currently A.F.C. are in the wales-ruthtroe, whal vertex is akku ment, and what is its final sel- est path distance to A Loes this itewly added vertex help any future vertex decrease its total shortest path to A, and if yes, which and by how much? (c) How many comparison operations would Floyd-Warshall algorithm require on the given graph