52.
请给出图中各点的度数，以及图的最大度数和最小度数。 答案：
d(v1)=4, d(v2)=4, d(v3)=2, d(v4)=1, d(v5)=3 D(G)=4, d(G)=1
53. 请给出图中各点的出度和入，以及图的最大出度和最小入度。
答案：
d+(a)=4, d-(a)=1, d(a)=5, d+(b)=0, d-(b)=3, d(b)=3, ?+(D)=4, ?+(D)=0, ??(D)=3, ??(D)=1, ?(D)=5, ?(D)=3.
54. (3,3,3,4), (2,3,4,6,8)能成为图的度数序列吗? 答案：
不可能. 它们都有奇数个奇数.
55. 已知图G有10条边, 4个3度顶点, 其余顶点的度数均小于等于2, 问G至少有多少个顶点? 答案：
设G有n个顶点. 由握手定理,
4?3+2?(n-4)?2?10 解得 n?8
56. 下面无向图中有几个顶点？
(1) 16条边，每个顶点都是2度顶点
(2) 21条边，3个4度顶点，其余的都是3度顶点
(3) 35条边，每个顶点的度数至少为3的图最多有几个顶点？ 答案：
57. 确定下列各图的出度、入度和度数
第16页， 共24页
答案：
58. 判断下列图是否同构
答案： 是 是 不是 是
59. 下图中，
1. 写出{a,d,e}的导出子图 2. 画出它的一个生成子图 3. 边集{e4,e7,e6}的导出子图
第17页，共24页
答案：
60. 试画出以下两个图的并图、交图和环和。
答案：
61. 判断下列各图是否是连通图：
第18页， 共24页
答案： 是、不是
62. 指出下列有向图的连通性
答案：
强连通图 单向连通图 弱连通图 强连通图 单向连通图 弱连通图
63. 求下列图的强连通分支
v1v2v3
v4
v5v6v7
答案：
64.
（1）{e5}、{e2 、e3}、{e6}、{e4}是否是下图的边割集？
（2）{v5}、{v2 、v4}、{v3}、{v1 、v2}、{v2 、v3}是否是下图的点割集？
第19页， 共24页
答案：
（1）是、是、是、否 （2）是、是、是、否、否
65. 求出下图的全部割点和桥
答案：
66. 下列图是否是树？如果是，找出树的分枝结点和树叶。
答案： 不是、是
分枝结点：e,f
树叶：a, b, c, d, g, h
67. 设一棵树T有2个度数为2的结点，1个度数为3的结点，3个度数为4的结点，求T有几片树叶。 答案：
第20页， 共24页