bazo
选择/填空题
1、任何n个节点m条边的图G = (V,E) , 边数与顶点度数的关系是。 3、n阶完全图Kn的边数为。
4、n个结点的有向完全图边数是( )，每个结点的度数是( )。
5、已知图G中有1个1度结点，2个2度结点，3个3度结点，4个4度结点，则G的边数是．
6、下面四组数能构成无向图的度数列的有( )。
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。
7、设无向图G有16条边且每个顶点的度数都是2，则图G有( )个顶点。
(1) 10 (2) 4 (3) 8 (4) 16
8、在有n个顶点的连通图中，其边数（ ）。
(1) 最多有n-1条(2) 至少有n-1 条
(3) 最多有n条 (4) 至少有n 条
9、如右图相对于完全图航行警告K5的补图为（）。
10、给定无向图G如下图所示，下面给出的结点集子集中，不是点割集的为（）． A．{b, d} B．{d}
C．{a, c} D．{b, e}
11、图G如右图所示，以下说法正确的是 ( ) ．
A．{(a, c)}是割边
B．{(a, c)}是边割集
C．{(b, c)}是边割集
D．{(a, c) ,(b, c)}是边割集
12、给定无向图G=<V, E>如下图所示，下面哪个边集不是其边割集（）。
A、；
B、{<v1,v4>,<v4,v6>};
C、；
D、。
13、设有向图（a）、（b）、（c）与（d）如下图所示，则下列结论成立的是( )．
A．（a）是强连通的 B．（b）是强连通的
C．（c）是强连通的 D．（d生产力研究）是强连通的
14、下图的邻接矩阵A=
15、设无向图G的邻接矩阵为，则G的边数为( )．
A．5B．6C．3D．4
16、图 的邻接矩阵为( )。
A、；B、；C、；D、。
综合题
17、设G=<V，E>，V={ v1，v2张清常，v3，v4，v5}，E={ (v1,v3)，(v2,v3)，whetheror(v2,v4)，(v3,v4)，(v3,v5)，(v4,v5) }，试
(1) 给出G的图形表示； (2) 写出其邻接矩阵；
(3) 求出每个结点的度数； (4) 画出其补图的图形．
18、已知：D=<V,E>，V={1,2,3,4,5}，E={<1,2>,<1,4>,<2,3>,<3,4>,<3,5>,<5,1>}，求D的邻接距阵A和可达距阵P。
19、无向图G有12条边，G中有6个3度结点，其余结点的度数均小于3，问G中至少有多少个结点？
内病外治
20、 有向图如右图所示。
（1）求的邻接矩阵；
（3）中到自身长度为3的回路有几条？
（4）是哪类连通图？
21、设图如图1所示，
(1) 求的邻接矩阵；
(2) 求，说明从到的长为的路径各有几条；
(3) 求的可达矩阵；
(4) 求的强连通分图。
22、设有如下有向图G=<V,E>，
（1）求G的邻接矩阵；
（2）G中v1到v4的长度为4 的通路有多少条？
（3）G中经过v1的长度为3 的回路有多少条？
（4）G中长度不超过4 的通路有多少条？其中有多少条通路？
二、 二部图、欧拉图、哈密顿图
选择/填空题
23、无向图G存在欧拉通路，当且仅当( )．
A．G中所有结点的度数全为偶数
B．G中至多有两个奇数度结点
C．G连通且所有结点的度数全为偶数
D．G连通且至多有两个奇数度结点
24、无向图G是欧拉图,当且仅当( )
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议