图论复习题

图论复习题

1、设G是由5个顶点构成的完全图，则从G中删去（ ）边可以得到树。

A．6 B．5 C．8 D．4 2、下面哪几种图不一定是树（ ）。 A．无回路的连通图

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

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

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=为有向图，则有（ ）。

A．E?V x V B．E?V x V C．V x V?E D．V x V=E 6、图G1和G2的结点和边分别存在一一对应关系是G1和G2同构的（ ）。

A．充分条件 B．必要条件 C．充分必要条件 D．既不充分也不必要条件 7、设

G=为有向图，V={a,b,c,d,e,f}，

E={,,,,}是（ ）。

A．强连通图 B．单向连通图 C．弱连通图 D．不连通图 8、无向图G中的边e是G的割边（桥）的充分必要条件是（）。 A．e是重边 B．e不是重边 C．e不包含在G的任一简单回路中 D．e不包含在G的某一简单回路中

9、在有n个结点的连通图中，其边数（ ） A．最多有n-1条 B．至少有n-1条 B．C．最多有n条 D．至少有n条

10．设无向简单图的顶点个数为n，则该图最多有（ ）条边。

A．n-1 B．n(n-1)/2 C． n(n+1)/2 D．n2 11．n个结点的完全有向图含有边的数目（ ）。

A．n*n Ｂ．n（n＋１） C．n／2 D．n*（n－l） 12．一个有n个结点的图，最少有（ ）个连通分量。

A．0 B．1 C．n-1 D．n 13．一个有n个结点的图，最多有（ ）个连通分量。

A．0 B．1 C．n-1 D．n

14．在一个无向图中，所有顶点的度数之和等于所有边数（ ）倍。

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

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

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

16、连通图G是一棵树，当且仅当G中（ ） A．有些边不是割边 B．所有边都是割边 C．无割边集 D．每条边都不是割边 17．4个顶点的完全图G，其不同构的生成树个数是（ ）。

A．4 B．3 C．5 D．6 18、下面四组数能构成无向图的度数列的有( )。 A、 2,3,4,5,6,7； B、 1,2,2,3,4； C、 2,1,1,1,2； D、 3,3,5,6,0。

19、图 的邻接矩阵为( )。

?1

??0?1??A、?1

000??1??101??1?1101?

???000?；B、??1111??0

??111??0

?1111????111?；C、??1

100??0

??

011??0

?1101?

???000?；D、??1

100?

?

101?101?

?

000??。

20、一棵无向树T有8个顶点，4度、3度、2度的分枝点各1个，其余顶点均为树叶，则T中有（ ）片树叶。

A、3； B、4； C、5； D、6

21、设V＝{a,b,c,d},与V能构成强连通图的边集E＝( )

(A) {,,,,}

(B) {,,,,} (C){,,,,} (D) {,,,,}

题1：已知图的结点集V={a,b,c,d}以及图G和图D的边集合分别为：

E(G)={(a,a), (a,b), (b,c), (a,c)}

E(D)={, , , , }

试作图G和图D，写出各结点的度数，回答图G、图D是简单图还是多重图？

题2：设简单连通无向图G有12条边，G中有2个1度结点，2个2度结点，3个4度结点，其余结点度数为3．求G中有多少个结点．试作一个满足该条件的简单无向图．

题3：设简单连通无向图G有9条边，G中有4个3度结点，2个1度结点，其余结点度数为2．求G中有多少个结点．

题4：两个图同构有下列必要条件：

（1） 结点数相同； （2） 边数相同；

（3） 度数相同的结点数相同.

但它们不是两个图同构的充分条件，下图中(a)和(b)满足上述三个条件，但这两个图并不同构，请说明理由。

(a) (b)

题5：设无向图G有12条边，已知G中度数为3的节点个数为6个，其余结点的度数均小于3，问G中至少有多少边？

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

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

题8、如下图所示的赋权图表示某七个城市v1,v2,?,v7及预先测算出它们之间的一些直接通信线路造价，试给出一个设计方案，使得各城市之间既能够通信而且总造价最小。

题9、求带权2、3、5、7、11、13的最优二叉树

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