Chapter Review 4172. Prim's Algorithm for MCST: Carry out the following procedure for the graph shown in
Figure 6.34 in Section 6.11.3. Let G = (V, E) be a graph. Maintain two sets: E 1 and
V 1 where E 1 is initially empty and V 1 is a subset of V initially containing any vertex of
the graph. Repeat I V I - 1 times: Find an edge e E E of least cost that joins a vertex
V E Vi to a vertex w ( V 1 .Let E 1 = E 1 U {e} and V 1 = VI U {w}.- A printer has one printing machine and one binding machine. Let pi and bi denote
the printing time and binding time for book i, respectively. For any two books i and
j, either bi > pj or bj > pi. Show that it is possible to specify an order in which the
books are printed (and then bound) so that once the first book is printed, the binding
machine will be kept busy until all the books are bound. As an example, find a schedule
for four books with printing time and binding time given as an ordered pair. (The first
coordinate is the printing time, and the second coordinate is the binding time.) D =
{(2, 3), (3, 5), (4, 1), (3, 3)}. - Eight computers must be networked together. Each computer must be accessible from
every other computer, but the connection does not have to be direct in all cases. The
computers (A-H) are represented by the vertices of the following graph, and the label
on an edge is an estimate of the cost of running the network cable. Find the set of
cables connecting all the computers with the minimum cost.
7(^3) B6
A 79 C
G6 5H^6 D
4 4 86 9 5
7 F E
- A bank plans to use special data lines to connect each of its branch offices with the
main office. The data line from a branch office need not be connected directly to the
main office. A branch office may be connected indirectly to the main office by con-
necting to another branch office that is connected (directly or indirectly) to the main
office. Every branch must be connected to the main office by some route. The distances
between pairs of offices are as follows:
1 2 3 4 5 6
1 X 160 270 75 70 190
2 160 X 310 80 210 50
3 270 310 X 175 120 215
4 75 80 175 X 150 240
5 70 210 120 150 X 100
6 190 50 215 240 100 XDetermine which pairs of offices should be connected by data lines so as to connect
every branch office (directly or indirectly) to the main office with a minimum total