第十四章部分课后习题参考答案
5、设无向图G有10条边,3度与4度顶点各2个,其余顶点的度数均小于3,问G至少有多少个顶点?在最少顶点的情况下,写出度数列、。 解:由握手定理图G的度数之和为:
3度与4度顶点各2个,这4个顶点的度数之和为14度。
其余顶点的度数共有6度。
其余顶点的度数均小于3,欲使G的顶点最少,其余顶点的度数应都取2,
所以,G至少有7个顶点, 出度数列为3,3,4,4,2,2,2,.
7、设有向图D的度数列为2,3,2,3,出度列为1,2,1,1,求D的入度列,并求,
,.
解:D的度数列为2,3,2,3,出度列为1,2,1,1,D的入度列为1,1,1,2.
,,
8、设无向图中有6条边,3度与5度顶点各1个,其余顶点都是2度点,问该图有多少个顶点?
解:由握手定理图G的度数之和为:
李安喜 设2度点个,则,,该图有4个顶点.
14、下面给出的两个正整数数列中哪个是可图化的?对可图化的数列,试给出3种非同构的无向图,其中至少有两个时简单图。 (1) 2,2,3,3,4,4,5 (2) 2,2,2,2,3,3,4,4
解:(1) 2+2+3+3+4+4+5=23 是奇数,不可图化;
(2) 2+2+2+2+3+3+4+4=16, 是偶数,可图化;
18、设有3个4阶4条边的无向简单图G1、G2、G3,证明它们至少有两个是同构的。
证明:4阶4条边的无向简单图的顶点的最大度数为3,度数之和为8,因而度数列为2,2,2,2;3,2,2,1;3,3,1,1。但3,3,1,1对应的图不是简单图。所以从同构的观点看,4阶4条边的无向简单图只有两个:
所以,G1、G2、G3至少有两个是同构的。
20、已知n阶无向简单图G有m条边,试求G的补图的边数。
解:
21、无向图G如下图
(1)求G的全部点割集与边割集,指出其中的割点和桥; (2) 求G的点连通度与边连通度。
解:点割集: {a,b},(d)
边割集{e2,e3},{e3,e4},{e1,e2},{e1,e4}{e1,e3},{e2,e4},{e5}
==1
23、求G的点连通度、边连通度与最小度数。
氨基丙酸
解:、 、
28、设n阶无向简单图为3-正则图,且边数m与n满足2n-3=m问这样的无向图有几种非同构的情况?
解: 得n=6,m=9.
31、设图G和它的部图的边数分别为和,试确定G的阶数。
解: 得
45、有向图D如图
(2)求到长度为1,2,3,4的回路数;
(3)求D中长度为4的通路数;
(4)求D中长度小于或等于4的回路数;
(5)写出D的可达矩阵。
解:有向图D的邻接矩阵为:
,
(1)到长度为1,2,3,4的通路数为0,2,0,0;
(2)到长度为1,2,3,4的回路数为0,0,4,0;
(3)D中长度为4的通路数为32;
(4)D中长度小于或等于4的回路数10;
(4)出D的可达矩阵
第十六章部分课后习题参考答案
1、画出所有5阶和7阶非同构的无向树.
2、一棵无向树T有5片树叶,3个2度分支点,其余的分支点都是3度顶点,问T有几个顶点?
解:设3度分支点个,则
,解得
T有11个顶点
3、无向树T有8个树叶,2个3度分支点,其余的分支点都是4度顶点,问T有几个4度分支点?根据T的度数列,请至少画出4棵非同构的无向树。
解:设4度分支点个,则
奈多罗米钠,解得
度数列111111113344
4、棵无向树T有 (i=2,3,…,k)个i度分支点,其余顶点都是树叶,问T应该有几片树叶?
解:设树叶片,则
,解得运动粘度
评论:2,3,4题都是用了两个结论,一是握手定理,二是
5、蓓舒宁n(n≥3)阶无向树T的最大度至少为几?最多为几?
解:2,n-1
6、若n(n≥3)阶无向树T的最大度 =2,问新闻体裁T中最长的路径长度为几?
解:n-1