《 离散数学 》

同步测试卷10:图的基本概念

一．填空：

1．一个无向图表示为G=，其中V是 结点 的集合，E是 边 的集合， 并且要求E中的任何一条边必须和G中的两个结点 相关联 。

2．设无向图G中有12条边，已知G中度为3的结点有6个，其余的结点度均 小于3，则G中至少有 9 个结点。

3．设G=(n,m)是简单图，v是G中一个度为k的结点，e是G中的一条边，则G – v中有n?1个结点，m?k条边；G – e中有n个结点，m?1条边。

4．设G是个有向图，当且仅当G中有一条经过每一个结点的路径时，G才是 单向 连通图。

5．设图G=，则：若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的子图，已知G?的边数E??n?n?1?，

则G的边数m为n?n?1?。

12．35条边，每个结点的度数至少是3的图最多有__23_个结点。

13、3个结点可构成 4 个不同构的简单无向图，可构成 16 个不同构的简单有向图。 14、设G??100,100?为无向连通图，则从G中能找到 1 条回路 15、K5的点连通度为 4 ，边连通度为 4 。

?0?116、设图G=，V??v1,v2,v3,v4?，若G的邻接矩阵A???1??1101??011?，则

100??000?deg??v1?? 3 ，deg??v4?? 1 ，，从v2到v4长度为2的通路有 1 条。

17、右图的点连通度为 1 ，边连通度为 1 。

1

18、当n为 奇 数时，Kn必为欧拉图。 19、Kn,m为哈密顿图，当且仅当n?m?2

20、若连通平面图G有4个结点，3个面，则G有 5 条边。 21、仅当n? 4 时，Kn为平面图。

22、设图G=<7,15>为简单平面图，则G一定是 连通的 ，且每个面均为K3 。 23、图A所示的图G的色数??G?? 3 。

24、图B所示的图G的点连通度??2，G的边连通度??3，点色数??G??4 。

A

B

25、K4的生成子图中，有 6 个非同构的连通图。

26、平面图G的对偶图G*同构于G，则称G为自对偶图，若一个?n,m?图是自

对偶的，则其结点数n与边数m的关系为m?2n?2

27、设D是n(?n?2?阶有向简单（若连通）图，则D的可达矩阵的所有元素之和至少为n?1

28、完全二部图Kn,m的点覆盖数?0? min?n,m?

29、设Wn?n?2k,k?2?为轮图，则Wn的点色数为??Wn?? 4

二．判断下列命题的对错。正确的在括号内填√,错误的在括号内填×。

1. 设图G=，则V中所含的结点数称为图G的阶。 （ √ ）

2． 设图G=，若V??，则称G为零图。 （ × ） 3、 设图G=，若V?1，则称G为平凡图。 （ × ） 4. 在简单有向图G的邻接矩阵A?aij??n?n中，结点vi所对应的行中1的个数等于vi的出

2

度。.(√)

5. 在简单无向图G的邻接矩阵A?aij??n?n中，结点vi所对应的行中1的个数等于vi的

度。.(√)

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．至少有n?1条边 C．最多有n条边 D．至少有n条边

2．设G=为无自环的无向图，如果V?5,E?12，则G是( D ) A．完全图 B．正则图 C．简单图 D．多重边图

3．设G=为简单完全有向图，如果V?5，则G中有( B )条边。 A．10 B．20 C．16 D．8

4．设G=为无自环的无向图，如果V?6,E?16，则G是( D ) A．完全图 B．零图 C．简单图 D．多重边图 （因E?5．如果无向图G中( D )，则称G是个简单无向图。

A．无回路 B．无自环 C．五多重边 D．无自环且无多重边 6．设G=(n,m)，若G中每个结点的度数不是k就是k?1，则G中度数为k的结点

3

V?V?1?2?15）

个数为( A )

A．n?k?1??2m B．n?n?1? C．nk D．7．任何无向图G中结点间的可达关系是( B )

n 2A．偏序关系 B．等价关系 C．相容关系 D．逆序关系 8．设有向图G=，其中V?{1,2,3,4},E?{?1,2?,?3,1?,?3,4?,?4,2?}，则G是( C )

A．强连通图 B．单向连通图 C．弱连通图 D．非连通图

9．设有向图G=，其中V?{a,b,c,d},E?{?a,b?,?a,d?,?d,c?,?b,d?}，则G是( C )

A．强连通图 B．单向连通图 C．弱连通图 D．非连通图

10．设有向图G=，其中V?{a,b,c,d}，则使G构成强连通的边集E是( A ) A．E?{?a,d?,?b,a?,?b,d?,?c,b?,?d,c?} B．E?{?a,d?,?b,a?,?b,c?,?b,d?,?d,c?} C．E?{?a,c?,?b,a?,?b,c?,?d,a?,?d,c?} D．E?{?a,b?,?a,c?,?a,d?,?b,d?,?c,d?} 11．设G=是个非连通的有向图，则 ( 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．不是多重边

4