算法代写 | CSE 21 HW 7

这个作业是完成最小生成树算法
CSE 21 HW 7

(1) (a) Construct 3 non-isomorphic trees on 5 vertices, give some justification for why these graphs are
not isomorphic.
(b) Construct 5 non-isomorphic trees on 6 vertices, give some justification for why these graphs are
not isomorphic.
(2) Suppose Brooks County has six radio stations S1, . . . , S6, whose distance are given in the table below
(in miles).
S1 S2 S3 S4 S5 S6
S1 − 85 175 200 50 100
S2 85 − 125 175 100 160
S3 175 125 − 100 200 250
S4 200 175 100 − 210 220
S5 50 100 200 210 − 100
S6 100 160 250 220 100 −
Suppose two stations cannot use the same channel if they are within 150 miles of each
other. What is the minimum number of channels needed?
(Hint: look at the name of the county).
(3) Below are the distances (in miles) of certain routes between the five cities: Fresno, Los Angeles,
Sacramento, San Diego, and San Francisco.
City pair Distance
Fresno – Los Angeles 221
Fresno – Sacramento 171
Fresno – San Diego 345
Fresno – San Francisco 187
Los Angeles – Sacramento 386
Los Angeles – San Diego 120
Los Angeles – San Francisco 382
Sacramento – San Diego 511
Sacramento – San Francisco 88
San Diego – San Francisco 508
Use Kruskal’s algorithm to find the minimum spanning tree of this graph. Clearly state the order
in which you add the vertices to the tree.