Please list the names of the other members of your peer group for this week and the number of extra credit points you think they deserve for their participation in group work on Tuesday and Thursday combined.
Given a graph G = (V, E), must any subset of edges T ⊆ E that connects all vertices in V and have minimal total weight be a tree, or can it be some other subgraph? Answer this question separately for two cases:
a. All of the edges have positive weight.
b. Some edges may have negative weights.
If you think “yes it must be a tree” then argue why this is the case (hint: suppose it’s not a tree: find a contradiction to connectedness or minimality). If you think “no, it need not be a tree” then give an example where a connected graph that is not a tree has lower weight.
The graph of Figure 23.4 has several edges of equal weight. Sometimes both are used; sometimes one can’t be used because it forms a cycle; and sometimes the choice is arbitrary: either edge could have been used. In this third case, the choice of which one was used depends on the order in which edges are sorted in line 4 (nondecreasing order by weight).
The actual ordering used in the book’s example is:
(g, h), (c, i), (f, g), (a, b), (c, f), (g, i), (c, d), (h, i), (a, h), (b, c), (d, e), (e, f), (b, h), (d, f)
Give an ordering that would result in a different minimum spanning tree than the one shown in figure 23.4 by rewriting the above list swapping just one pair of edges.
Suppose we are in Canada’s Thousand Islands National Park, and in one particular lake there are eight small islands that park officials want to connect with floating bridges so that people can experience going between islands without a canoe. The cost of constructing a bridge is proportional to its length, and the table below shows the distances between pairs of islands in meters (Canada is trying to free itself of the archaic British system of measurement based on the sizes of a dead king’s body parts.)
Which bridges should they build to connect the eight islands at minimal cost? Say in a sentence or two how you found the solution, and give the solution as a list of pairs of islands, for example, (A, B) ….
A  B  C  D  E  F  G  H  

A  − 
240 
210 
340 
280 
200 
345 
120 
B  −

− 
265 
175 
215 
180 
185 
155 
C  − 
−

− 
260 
115 
350 
435 
195 
D  −

−

−

− 
160 
330 
295 
230 
E  −

−

−

−

− 
360 
400 
170 
F  −

−

−

−

−

− 
175 
205 
G  −

−

−

−

−

− 
− 
305 
H  −

−

−

− 
−

− 
−

−
