习题9-4

习题9-4

1.在图9-33中,用破圈法构造最小生成树,并画出生成树.

2.求图9-34的最小生成树T并给出T的权和.

img

图9-33

img

图9-34

3.求图9-35的最小生成树,并给出权值.

4.求图9-36的最小生成树,并给出权值.

img

图9-35

img

图9-36

5.图G=(V,E),其中V={a,b,c,d,e,f},E={(a,b),(a,c),(a,e),(b,d),(b,e),(c,e),(d,e),(d,f),(e,f)},对应边的权值依次为5,2,1,2,6,1,9,3及8.求出G权最小的生成树及其权值.