CS 163/265, Winter 2025, Practice Problem Set 2

1. Suppose that we compute the minimum spanning tree $T$ of a graph $G$, but then we increase the weight of one of its edges, $e$. Assume that before and after this change all edges have distinct weights.

   1. Use the cut property to prove that for every edge $f$ in $T$ (with $f\ne e$), edge $f$ remains part of the minimum spanning tree after the change. (Hint: find a cut for which $f$ is the only edge of $T$ crossing the cut; use the cut property to show that, before the weight change, $f$ must be the smallest edge of $G$ crossing this cut. Use the cut property a second time, with the same cut, to show that $f$ remains part of the changed minimum spanning tree.)

   2. Based on part (a) and the cut property, describe a linear-time algorithm to find the new minimum spanning tree after this change to the weight of $e$. (Hint: re-use most of $T$ and use the cut property once to find the parts that might have changed.)

2. Recall that Kruskal's algorithm for minimum spanning trees considers the edges of a graph in sorted order, and adds some of these edges in that order to the minimum spanning tree. Suppose that we have a connected graph with five vertices, so that it adds four edges to the tree. The first edge that it adds must be at the start of the sorted sequence (in position 0). The second edge that it adds must be the second edge in the sorted sequence (in position 1). The third edge that it adds might be in position 2 or position 3. For the fourth edge that it adds, what positions in the sorted sequence can that edge have? You can assume that the graph is simple (there are no repeated edges) and that there are also no repeated edge weights.

3. Suppose that a directed acyclic graph $D$ has five vertices, $\alpha$, $\beta$, $\gamma$, $\delta$, and $\omega$, that every topological ordering of $D$ begins with $\alpha$, and that every topological ordering of $D$ ends with $\omega$. What is the maximum number of different topological orderings that $D$ can have? Draw an example of a directed acyclic graph $D$ that has this maximum number of different topological orderings.

4. Suppose that your friend would like to finish their computer science major by taking ICS 46, CS 161, CS 163, CS 171, CS 172B, CS 172C, and CS 178 (none of which they have already taken). Use the UCI Course Catalog for Computer Science (2025–2025 edition) to draw an activity-on-edge graph with a single start vertex, and a single edge vertex, and with these classes as the activities on the edges, representing accurately the prerequisite requirements between these courses. (Ignore the other ways of fulfilling the prerequisites for these courses, and ignore the recommended courses; ICS 46 is not listed on that page of the catalog but you can find it listed as a prerequisite for some of these courses.) Assume that your friend can take an unlimited number of courses per quarter but must take each prerequisite to a course before taking the course, and that each course is offered in every quarter (not actually true). How many quarters will it take your friend to complete the major, following an optimal schedule? Identify a critical path among these courses.

   (Note: Course prerequisites cannot always be described accurately by a DAG, because students do not need to take every course and because of the and/or relations among some prerequisites. See e.g. CS 117 for a course with a very complicated prerequisite structure.)