图论练习题2009(学生练习)VIP免费

图论练习题 一、基本题 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、把平面分成 x 个区域，每两个区域都相邻，问 x 最大为（ ） A．6 B．4 C．5 D．3 5、设图G 有 n 个结点，m 条边，且 G 中每个结点的度数不是 k，就是 k+1，则 G 中度数为k 的节点数是（ ） A．n/2 B．n(n+1) C．nk-2m D．n(k+1)-2m 6、设 G=为有向图，则有（ ）

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

A．充分条件 B．必要条件 C．充分必要条件 D．既不充分也不必要条件 8、设 G=为有向图，V={a,b,c,d,e,f}，E={,,,,}是（ ）

A．强连通图 B．单向连通图 C．弱连通图 D．不连通图 9、无向图G 中的边 e 是 G 的割边（桥）的充分必要条件是（）

A．e 是重边 B．e 不是重边 C．e 不包含在 G 的任一简单回路中 D．e 不包含在 G 的某一简单回路中 10、在有 n 个结点的连通图中，其边数（ ） A．最多有 n-1 条 B．至少有 n-1 条 C．最多有 n 条 D．至少有 n 条 11．设无向简单图的顶点个数为 n，则该图最多有（ ）条边

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