第五章单元测试
- 给定下列各图，为简单图的是（ ）。
- 下面各序列中，可以构成无向简单图的是（ ）。
- 下面给出的无向图中，为多重图的是（ ）。
- 下列各组数中，能够构成无向图的度数列的是（ ）。
- 一个无向图有16条边，每个顶点都是2度的，则这个无向图中有几个顶点（ ）。
- 下面图中强连通图为（ ）。
- 对如下无向图
下面选项中哪一个不是该无向图的点割集。（ ） - 不含平行边的图称为简单图。（ ）
- 任何图（无向图或有向图）中，度数为奇数的顶点个数为偶数。（ ）
- 顶点数相同，边数相同，度数序列也相同的两个图一定同构。（ ）
- 给图着色时，若图为圈，长度为偶数的圈要用2种颜色，长度为奇数的圈要用3种颜色。（ ）
- 给图着色时，奇阶轮图要用3种颜色，偶阶轮图要用4种颜色。（ ）
- 项目网络图有一个始点和一个终点，始点的出度为0，终点的入度为0。（ ）
- 无向图的关联矩阵中每一列都恰好有两个1或一个2。（ ）
- 有向图的邻接矩阵中所有元素之和等于对应图中边数的两倍。（ ）
- 完全图K4的所有非同构的生成子图中， 2条边的有（ ）个。____。
- 一个无向图有21条边，3个4度顶点，其余都是3度顶点，则该图有（ ）个顶点。____。
- 任何图（无向图或有向图）中所有顶点的度数之和等于边数的（ ）倍。____。
- 在一个n阶图中，若从顶点u到v(u
v)存在通路，则从u到v存在长度小于等于（ ）的通路。____。 - 下图至少要用（ ）种颜色着色。____。
- 35条边，每个顶点的度数至少为3的图最多有（ ）个顶点。____。
- 求图中从顶点b顶点到g的最短路径为（ ）。____。
- 画出4阶3条边的所有非同构的无向简单图。
- 设有向图D的度数列为2,2,3,3，入度列为0,0,2,3，试求出D的出度列。
- 设G为9阶无向图，每个顶点的度数不是5就是6，证明G中至少有5个6度顶点或至少有6个5度顶点。
- 设G1与G2均为无向简单图，证明：G1@G2当且仅当
，其中
分别为G1与G2的补图。 - 已知n阶无向图G中有m条边，各顶点的度数均为3，又已知2n-3=m，问在同构的意义下，G是唯一的吗？若G为简单图，是否唯一？请说明为什么。
- 有向图D如下图所示，求D中在定义意义下长度为4的通路总数，并指出其中有多少条是回路？又有几条是v3到v4的通路。
- 计算机系期末要安排7门公共课的考试，课程编号为1到7。下列每一对课程有学生同时选修：1和2，1和3，1和4，1和7，2和3，2和4，2和5，2和7，3和4，3和6，3和7，4和5，4和6，5和6，5和7，6和7。这7门课的考试至少要安排在几个不同的时间段？给出一个安排方案。
A:
B:
C:
D:
答案:
A:（1,1,2,2,2）
B:（1,3,4,4,3）
C:（3,3,4,2,3）
D:（1,1,2,2,3）
A:G=＜V，E＞, 其中V={a, b, c, d, e}，E={（a, b）,（b, e）,（e, b）,（a, e）,（d, e）}
B:G=＜V，E＞, 其中V={a, b, c, d, e}，E={（a, b）,（b, e）,（e, d）,（c, c）}
C:G=＜V，E＞, 其中V={a, b, c, d, e}，E={（a, b）,（b, c）,（c, d）,（a, e）}
D:G=＜V，E＞, 其中V={a, b, c, d, e}，E={（a, c）,（b, e） ,（a, e）,（d, e）}
A:1,1,1,2,4
B:1,2,3,4,5
C:3,3,2,3
D:2,2,4,2,2
A:10
B:4
C:16
D:8
A:
B:
C:
D:
A:{v2，v4}
B:{v6}
C:{v3，v5}
D:{v2}
A:对 B:错
A:对 B:错
A:错 B:对
A:对 B:错
A:对 B:错
A:对 B:错
A:对 B:错
A:对 B:错
温馨提示支付 ￥3.00 元后可查看付费内容,请先翻页预览!
