cabedf图一cabedf图四精品文档---下载后可任意编辑一、单项选择题1．设无向图 G 的邻接矩阵为则 G 的边数为( )．A．6 B．5 C．4 D．32．已知图 G 的邻接矩阵为 ，则 G 有（ ）．A．5 点，8 边 B．6 点，7 边C．6 点，8 边 D．5 点，7 边3．设图 G＝，则下列结论成立的是 ( )．A．deg(V)=2E B．deg(V)=EC． ∑v ∈Vdeg(v)=2|E| D． ∑v ∈Vdeg(v)=|E|4．图 G 如图一所示，以下说法正确的是 ( ) ．A．{(a, d)}是割边B．{(a, d)}是边割集C．{(d, e)}是边割集D．{(a, d) ,(a, c)}是边割集5．如图二所示，以下说法正确的是 ( )．A．e 是割点 B．{a,e}是点割集C．{b, e}是点割集 D．{d}是点割集6．如图三所示，以下说法正确的是 ( ) ．A．{(a, e)}是割边 B．{(a, e)}是边割集C．{(a, e) ,(b, c)}是边割集 D．{(d, e)}是边割集图三7．设有向图（a）、（b）、（c）与（d）如图四所示，则下列结论成立的是 ( )．图四 A．（a）是强连通的 B．（b）是强连通的C．（c）是强连通的 D．（d）是强连通的应该填写：D8．设完全图 K 有 n 个结点(n≥2)，m 条边，当（ ）时，K 中存在欧拉回路．A．m 为奇数 B．n 为偶数 C．n 为奇数 D．m 为偶数9．设 G 是连通平面图，有 v 个结点，e 条边，r 个面，则 r= ( )．A．e－v＋2 B．v＋e－2 C．e－v－2 D．e＋v＋210．无向图 G 存在欧拉通路，当且仅当( )．A．G 中所有结点的度数全为偶数 B．G 中至多有两个奇数度结点C．G 连通且所有结点的度数全为偶数D．G 连通且至多有两个奇数度结点11．设 G 是有 n 个结点，m 条边的连通图，必须删去 G 的( )条边，才能确定 G 的一棵生成树．A．B．C．D．12．无向简单图 G 是棵树，当且仅当( )．A．G 连通且边数比结点数少 1 B．G 连通且结点数比边数少 1C．G 的边数比结点数少 1 D．G 中没有回路．二、填空题1．已知图 G 中有 1 个 1 度结点，2 个 2 度结点，3 个 3 度结点，4 个 4 度结点，则 G 的边数是．2．设给定图 G(如图四所示)，则图 G 的点割集是．3．若图 G=中具有一条汉密尔顿回路，则对于结点集 V 的每个非空子集 S，在 G 中删除 S中的所有结点得到的连通分支数为 W，则 S 中结点数|S|与 W 满足的关系式为．4．无向图 G 存在欧拉回路，当且仅当 G 连通且．...
