图论练习题

图论练习题

一、基本题

1、设G是由5个顶点构成的完全图，则从G中删去（A）边可以得到树。 A．6 B．5 C．8 D．4 2、下面哪几种图不一定是树（A）。 A．无回路的连通图

B．有n个结点，n-1条边的连通图 C．对每对结点间都有通路的图

D．连通但删去任意一条边则不连通的图 3、5阶无向完全图的边数为（B）。

A．5 B．10 C．15 D．20

4、设图G有n个结点，m条边，且G中每个结点的度数不是k，就是k+1，则G中度数为k的节点数是（ ）

A．n/2 B．n(n+1) C．nk-2m D．n(k+1)-2m 5、设G=为有向图，V={a,b,c,d,e,f}，E={,,,,}是（B）。 A．强连通图 B．单向连通图 C．弱连通图 D．不连通图 6、在有n个结点的连通图中，其边数（B）

A．最多有n-1条 B．至少有n-1条 C．最多有n条 D．至少有n条 7、设无向简单图的顶点个数为n，则该图最多有（C）条边。

2

A．n-1 B．n(n-1)/2 C． n(n+1)/2 D．n 8、要连通具有n个顶点的有向图，至少需要（A ）条边。

A．n-l B．n C．n+l D．2n 9、n个结点的完全有向图含有边的数目（B）。

A．n*n Ｂ．n（n＋１） C．n／2 D．n*（n－l） 10、在一个无向图中，所有顶点的度数之和等于所有边数（B）倍。

A．1/2 B．2 C．1 D．4

11、在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（C）倍。

A．1/2 B．2 C．1 D．4 12、连通图G是一棵树，当且仅当G中（B）

A．有些边不是割边 B．所有边都是割边 C．无割边集 D．每条边都不是割边 13、4个顶点的完全图G，其生成树个数是（ ）。

A．4 B．8 C．16 D．64

二、应用题

题1、判断下图是否能一笔画出，并说明理由。

V0

Vn V0

Vn

图（a） 图（b）

答：图a ，b 都可以 因为奇度点的个数为偶数，其余都是偶度点。

题2、用Kruskal算法求下图的的最小生成树，并计算其权。

A B C D E F

答： 其权之和为

38。

题3、求出下图中以v1为起点的一条中国邮路。

题4、利用Dijkstra算法，求解下图中从顶点1到其余各点的最短路径。

题5、求下图最大流。

题6、求下图的最大流。

题7、利用Dijkstra算法，求下图从1出发到其余各点的最短路径。

本文来源：https://www.bwwdw.com/article/0vwo.html