《 离散数学 》
同步测试卷10:图的基本概念
一．填空：
1．一个无向图表示为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为有向图。 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=
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=
2． 设图G=
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=
3．设G=
4．设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=
A．强连通图 B．单向连通图 C．弱连通图 D．非连通图
9．设有向图G=
A．强连通图 B．单向连通图 C．弱连通图 D．非连通图
10．设有向图G=
12．设G是具有n个结点的3次正则图，则结点数n( B ) A．必是奇数 B．必是偶数 C．或者是奇数或者是偶数 D．必等于6
13．无向图G中的边e是G中的割边的充要条件是：e( C ) A．是悬挂边 B．不是多重边
4