图论练习题

更新时间:2024-01-20 00:22:01 阅读量: 教育文库 文档下载

说明:文章内容仅供预览,部分内容可能不全。下载后的文档,内容与下面显示的完全一致。下载之前请确认下面内容是否您想要的,是否完整无缺。

图论练习题

一、基本题

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 B.n(n+1) 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

Top