第九章　复习题

第九章　复习题

1.单项选择题.

（1）设图G的邻接矩阵为，则G的边数为（ ）.

A.5 　B.6　C.3　D.4

（2）设图G=〈V，E〉，则下列结论成立的是（ ）.

（3）无向图G存在欧拉通路，当且仅当（ ）.

A.G中所有结点的度数全为偶数　B.G中至多有两个奇数度结点

C.G连通且所有结点的度数全为偶数　D.G连通且至多有两个奇数度结点

（4）设G是有n个结点、m条边的连通图，必须删去G的（ ）条边，才能确定G的一棵生成树.

A.m-n+1　B.m-n　C.m+n+1　D.n-m+1

2.求图9-45中从v1到v5的最短路.

3.求图9-46中v1到v11的最短路.

4.用破圈法和避圈法求图9-47（a）、图9-47（b）的最小生成树.

5.求如图9-48所示的网络最大流.

6.某工厂x生产特定产品，要通过如图9-49所示的运输网络运送到零售点y，利用标号法确定从工厂到零售点的产品最大运送数量.