《 离散数学 》
土库曼语同步测试卷10:图的基本概念
一．填空：
1．一个无向图表示为G=<V, E>，其中V是 结点 的集合，E是 边 的集合， 并且要求E中的任何一条边必须和G中的两个结点 相关联 。
2．设无向图G中有12条边，已知G中度为3的结点有6个，其余的结点度均
小于3，则G中至少有 9 个结点。
3．设G=(n,m)是简单图，v是G中一个度为k的结点，e是G中的一条边，则G – v中有个结点，条边；G – e中有个结点，条边。
4．设G是个有向图，当且仅当G中有一条经过每一个结点的路径时，G才是
单向 连通图。
5．设图G=<V, E>，则：若E中的每条边都是_无向边 _，则称图G为无向图；若E中的每条边都是_有向边__，则称图G为有向图。
6．设图G中 无自环 和 无平行边 ，则称图G为简单图。
7．设G是个无自环的无向图，其中有2个结点的度数为4，其余结点的度为2，有6条边。则G中共有_ 4 个结点。因此，G是个多重边_图。
8．一个无向图G有16条边，若G中每一个结点的度均为2，则G有16个结点。
9．设G是个具有5个结点的简单无向完全图，则G有__10_条边。
10．设G是个具有5个结点的简单有向完全图，则G有_20_条边。
11．设G是个n阶简单有向图，是G的子图，已知的边数，则G的边数m为。
12．35条边，每个结点的度数至少是3的图最多有__23_个结点。
13、3个结点可构成 4 个不同构的简单无向图，可构成 16 个不同构的简单有向图。
14、设为无向连通图，则从中能到 1 条回路
15、的点连通度为 4 ，边连通度为 4 。
16、设图G=<V, E>，，若G的邻接矩阵，则
3 ， 1 ，，从到长度为2的通路有 1 条。
17、右图的点连通度为 1 ，边连通度为 1 。
18、当为 奇 数时，必为欧拉图。
19、为哈密顿图，当且仅当
20、若连通平面图G有4个结点，3个面，则G有 5 条边。
21、仅当 4 时，为平面图。
22、设图G=<7,15>为简单平面图，则G一定是 连通的 ，且每个面均为 。
23、图A所示的图G的数 3 。
24、图B所示的图G的点连通度2，G的边连通度3，点数4 。
25、的生成子图中，有 6 个非同构的连通图。
26、平面图的对偶图同构于，则称为自对偶图，若一个图是自对偶的，则其结点数与边数的关系为 27、设D是阶有向简单（若连通）图，则D的可达矩阵的所有元素之和至少为
28、完全二部图的点覆盖数
29、设为轮图，则的点数为 4
二．判断下列命题的对错。正确的在括号内填√,错误的在括号内填×。 1. 设图G=<V, E>，则V中所含的结点数称为图G的阶。 （ √ 黑龙江畜牧兽医网）
2． 设图G=<V, E>，若，则称G为零图。 （ × ）
3、 设图G=<V, E>，若，则称G为平凡图。 （ × ）
4. 在简单有向图G的邻接矩阵中，结点所对应的行中1的个数等于的出度。.(√)湘乡市育才中学
5. 在简单无向图G的邻接矩阵中，结点所对应的行中1的个数等于的度。.(√)
6． 若无向图中恰有两个奇结点，则这两个奇结点比相互可达。.(√)
7. 若有向图中恰有两个奇结点，则必有从一个结点到另一个结点可达或相互可达。.(×)
8． 对任何一个图，其奇结点的个数一定是偶数。.(√)
9． 在有向图中，结点间的可达关系一定是个等价关系。.(×)
10． 割边（或桥）一定是悬挂边。.(×)
11． 悬挂边一定是割边（或桥）。.(√)
12． 悬挂点一定是割点。(×)
13． 割点一定是悬挂点。 (×)
14． 有向图中的每个结点都恰处于一个单向分图中。(×) 15． 在完全无向图中，任意两个点都是邻接结点。(√)
16． 如果无向图G的邻接矩阵中所有元素均为零，则G必为零图。(√)
17． 如果简单无向图G的邻接矩阵中除主对角线外所有元素均为“1”，则G一定是完全图。(×)
18．如果G是一个非连通无向图，则G的一个连通子图称为G的一个分支。(×)
19．如果一个简单无向图G连通且无回路，则G中的每条边必为割边。(√)
20．具有n个结点的连通图中，至少有n条边。(×)
三、在每小题的备选答案中只有一个正确答案，将正确答案序号填入下列叙述中的 内(多选不给分)。
1．在具有n个结点的无向连通图中，( B )
A．恰好有n条边 B．至少有条边
C．最多有n条边 D．至少有n条边
2．设G=<V, E>为无自环的无向图，如果，则G是( D )
A．完全图 B．正则图 C．简单图 D．多重边图
3．设G=<V, E>为简单完全有向图，如果，则G中有( B )条边。
A．10 三维建模 B．20 C．16 D．8
4．设G=<V, E>为无自环的无向图，如果，则G是( D )
A．完全图 B．零图 C．简单图 D．多重边图 （因）
5．如果无向图G中( D )，则称G是个简单无向图。
A．无回路 B．无自环 C．五多重边 D．无自环且无多重边
6．设G=(n,m)，若G中每个结点的度数不是就是，则G中度数为的结点个数为( A )
A． B． C． D．
7．任何无向图G中结点间的可达关系是( B )
A．偏序关系 B．等价关系 C．相容关系 D．逆序关系
8．设有向图G=<V, E>，其中，则G是( C )
A．强连通图 B．单向连通图
C．弱连通图 D．非连通图
9．设有向图G=<V, E>，其中，则G是( C )
A．强连通图 B．单向连通图
C．弱连通图 D．非连通图
10．设有向图G=<V, E>，其中，则使G构成强连通的边集E是( A )
A．
B．
C．
D．
11．设G=<V, E>是个非连通的有向图，则 ( A )
A．G中的每个结点恰处于一个强分图中
B．G中的每个结点恰处于一个单向分图中
C．G中有的结点可能处于两个强分图中
D．G中有的结点可能不处于任何单向分图中
12．设G是具有n个结点的3次正则图，则结点数n( B )
A．必是奇数 B．必是偶数
C．或者是奇数或者是偶数 D．必等于6
13．无向图G中的边e是G中的割边的充要条件是：e( C )
A．是悬挂边 B．不是多重边
C．不包含在G的任一简单回路中
D．不包含在G的某一回路中
14．设无向图G中有5条边，已知G中度为2的结点有2个，其余结点的度为3，则G中共有( C )个结点。
A．6 B．6 C．4 D．10
15．图与的结点和边分别存在一一对应的关系是与同构的( B )
A．充分条件 B．必要条件
C．充要条件 D．既不是充分条件也不是必要条件
16、设为有向图，则有( A )
A． B． C． D．
17、含有5个结点、3条边的不同构的简单图有( C )个
A．2 B．3 C．4 D．5
18、设G为有个结点的简单图，则有( A )
A． B．
C． D．
19、设，且中每个结点的度数不是就是，则中度为的结点的个数是( D )
A． B． C． D．
20、给定下列序列，( B )可以构成无向简单图的结点度数序列。
A． B．ssnd
C． D．
21、个结点可构造的简单无向图（含同构图）的个数是(D )
A． B． C． D．（完全图的边集的子集数目）
22、中含有3条边的不同构生成子图有( 3 )个
A．1 B．3 C．4 D．2农村业余文化生活
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议