离散课后习题答案.docx
- 文档编号:12264514
- 上传时间:2023-06-05
- 格式:DOCX
- 页数:19
- 大小:58.05KB
离散课后习题答案.docx
《离散课后习题答案.docx》由会员分享,可在线阅读,更多相关《离散课后习题答案.docx(19页珍藏版)》请在冰点文库上搜索。
离散课后习题答案
第十四章部分课后习题参考答案
5、设无向图G有10条边,3度与4度顶点各2个,其余顶点的度数均小于3,问G至
∆、
少有多少个顶点?
在最少顶点的情况下,写出度数列、
解:
由握手定理图G的度数之和为:
2⋅10=20
()™(G)。
3度与4度顶点各2个,这4个顶点的度数之和为14度。
其余顶点的度数共有6度。
其余顶点的度数均小于3,欲使G的顶点最少,其余顶点的度数应都取2,
所以,G至少有7个顶点,出度数列为3,3,4,4,2,2,2,∆(
)=4,
()=2.
G™G
7、设有向图D的度数列为2,3,2,3,出度列为1,2,1,1,求D的入度列,并求
∆(D),™(D),
∆(D),™
+(),∆−
D
(D),™
(D).
解:
D的度数列为2,3,2,3,出度列为1,2,1,1,D的入度列为1,1,1,2.
∆()=3,()=2,∆+
D™D
(D)=2,™
+()=1,∆−
D
(D)=2,™
(D)=1
8、设无向图中有6条边,3度与5度顶点各1个,其余顶点都是2度点,问该图有多少
个顶点?
解:
由握手定理图G的度数之和为:
2⋅6=12
设2度点x个,则3⋅1+5⋅1+2x=12,x=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,因而度数列
1
为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的补图G的边数m′。
解:
′=n(n−1)
m2m
21、无向图G如下图
(1)求G的全部点割集与边割集,指出其中的割点和桥;
(2)求G的点连通度k(G)与边连通度⎣(G)。
ae1
e2d
e
be5
解:
点割集:
{a,b},(d)
e3e4
c
边割集{e2,e3},{e3,e4},{e1,e2},{e1,e4}{e1,e3},{e2,e4},{e5}
()=(
GG
)=1
23、求G的点连通度(
G
)、边连通度(
⎣G
)与最小度数()。
™G
解:
(G)=2、⎣(G)=3
、()=4
™
28、设n阶无向简单图为3-正则图,且边数m与n满足2n-3=m问这样的无向图有几种
非同构的情况?
解:
⎧
n=2m
得n=6,m=9.
⎩2n−3=m
2
31、设图G和它的部图G的边数分别为m和m,试确定G的阶数。
解:
m+m
=n(n+1)
2
−1+
得n=
1+8(m+m)
2
45、有向图D如图
(1)求v2到v5长度为1,2,3,4的通路数;
(2)求v5到v5长度为1,2,3,4的回路数;
(3)求D中长度为4的通路数;
(4)求D中长度小于或等于4的回路数;
(5)写出D的可达矩阵。
v1v4
v5
v2v3
解:
有向图D的邻接矩阵为:
⎛0000
⎜
⎜0101
1⎞
⎟
1⎟,A
⎟
⎠
⎛01
⎜
=⎜0
⎜
⎝20
010⎞
⎟
0⎟A
⎟
20⎠
⎛20200⎞
⎜⎟
=⎜20⎟
⎜⎟
⎝0000⎠
⎛00004⎞
⎜⎟
⎜40400⎟
4=⎜00004⎟
A⎜⎟
⎜40400⎟
⎜⎟
⎝0404⎠
A+A+
A+A
⎛01
⎜
⎜52
4=⎜21
⎜
⎜42
⎜
⎝25
215⎞
⎟
522⎟
215⎟
⎟
522⎟
⎟
25⎠
(1)v2到v5长度为1,2,3,4的通路数为0,2,0,0;
(2)v5到v5长度为1,2,3,4的回路数为0,0,4,0;
(3)D中长度为4的通路数为32;
(4)D中长度小于或等于4的回路数10;
3
⎛1
⎜
⎜1
(4)出D的可达矩阵=⎜1
P⎜
⎜1
⎜
⎝1
1111⎞
⎟
1111⎟
1111⎟
⎟
1111⎟
111⎟
第十六章部分课后习题参考答案
1、画出所有5阶和7阶非同构的无向树.
2、一棵无向树T有5片树叶,3个2度分支点,其余的分支点都是3度顶点,问T有
几个顶点?
解:
设3度分支点x个,则
5⋅1+3⋅2+3x=2⋅(5+3+x−1),解得x=3
T有11个顶点
3、无向树T有8个树叶,2个3度分支点,其余的分支点都是4度顶点,问T有几个4
度分支点?
根据T的度数列,请至少画出4棵非同构的无向树。
解:
设4度分支点x个,则
8⋅1+2⋅3+4x=2⋅(8+2+x−1),解得x=2
度数列
4
4、棵无向树T有
i
几片树叶?
(i=2,3,…,k)个i度分支点,其余顶点都是树叶,问T应该有
解:
设树叶片,则
x
ni⋅i+x⋅1=2⋅(ni
+x−1),解得x=(
−2)ni+2
评论:
2,3,4题都是用了两个结论,一是握手定理,二是m=n−1
5、n(n≥3)阶无向树T的最大度
少为几?
最多为几?
解:
2,n-1
6、若n(n≥3)阶无向树T的最大度
=2,问T中最长的路径长度为几?
解:
n-1
7、证明:
n(n≥2)阶无向树不是欧拉图.证明:
无向树没有回路,因而不是欧拉图。
8、证明:
n(n≥2)阶无向树不是哈密顿图.证明:
无向树没有回路,因而不是哈密顿图。
9、证明:
任何无向树T都是二部图.
证明:
无向树没有回路,因而不存在技术长度的圈,是二部图。
10、什么样的无向树T既是欧拉图,又是哈密顿图?
解:
一阶无向树
14、设e为无向连通图G中的一条边,e在G的任何生成树中,问e应有什么性质?
解:
e是桥
15、设e为无向连通图G中的一条边,e不在G的任何生成树中,问e应有什么性质?
解:
e是环
23、已知n阶m条的无向图G是k(k≥2)棵树组成的森林,证明:
m=n-k.;证明:
数学归纳法。
k=1时,m=n-1,结论成立;
设k=t-1(t-1≥1)时,结论成立,当k=t时,无向图G是t棵树组成的森林,任取两棵
树,每棵树任取一个顶点,这两个顶点连线。
则所得新图有t-1棵树,所以m=n-(k-1).
所以原图中m=n-k
得证。
24、在图16.6所示2图中,实边所示的生成子图T是该图的生成树.
(1)指出T的弦,及每条弦对应的基本回路和对应T的基本回路系统.
5
(2)指出T的所有树枝,及每条树枝对应的基本割集和对应T的基本割集系统.
(a)(b)
图16.16
解:
(a)T的弦:
c,d,g,h
T的基本回路系统:
S={{a,c,b},{a,b,f,d},{e,a,b,h},{e,a,b,f,g}}
T的所有树枝:
e,a,b,f
T的基本割集系统:
S={{e,g,h},{a,c,d,g,h},{b,c,d,g,h},{f,d,g}}
(b)有关问题仿照给出
25、求图16.17所示带权图中的最小生成树.
(a)(b)
图16.17
解:
注:
答案不唯一。
37、画一棵权为3,4,5,6,7,8,9的最优2叉树,并计算出它的权.
6
38.下面给出的各符号串集合哪些是前缀码?
A1={0,10,110,1111}是前缀码A2={1,01,001,000}是前缀码A3={1,11,101,001,0011}不是前缀码A4={b,c,aa,ac,aba,abb,abc}是前缀码A5={b,c,a,aa,ac,abc,abb,aba}不是前缀码
41.设7个字母在通信中出现的频率如下:
a:
35%b:
20%c:
15%d:
10%e:
10%f:
5%
g:
5%
用Huffman算法求传输它们的前缀码.要求画出最优树,指出每个字母对应的编码.
并指出传输10n(n≥2)个按上述频率出现的字母,需要多少个二进制数字.
解:
a:
01b:
10c:
000d:
110e:
001f:
1111g:
1110
W(T)=5*4+5*4+10*3+10*3+15*3+20*2+35*2=255
传输10n(n≥2)个按上述频率出现的字母,需要255*10n-2个二进制数字.
7
《管理学基础》离线作业2
第三章计划职能
一、判断题
1.任务环境中最直接、最明显影响企业经营的是市场。
(√)
2.按原有已规定的程序、处理方法和标准进行的决策是程序化决策(√)
3.管理问题分析界定的基本内容是明确解决问题的方向与思路(×)
4.企业的基本计划类型主要是战术计划(×)
二、单项选择题
1.制定目标的原则主要有(D)
A.明确性原则和先进合理原则
D.明确性原则、先进合理原则、可行性原则和定量化原则
2.邀请专家、内行、针对组织内某一个问题或某一个一题,让大家开动脑筋,畅所欲言地发表个人意见,充分发挥个人和集体的创造性,经过相互启发,产生连锁反应,集思广益,然后进行决策的方法是(B)
3.面对棘手的管理问题,要熟练地运用一些创造性技法,形成解决问题的全新创意。
根据管理实践经验,创造技法包括(D)
、综合B.分解、折中
C.换元、重组D.寻异、综合、分解、折中、换元、重组、移植、逆寻
三、多项选择题
1.对企业经营较大的一般环境主要有(ABCD)
2.美国学者波特提出了产业竞争结构的分析模型,他认为,决定一个产业的竞争状态的基本竞争力量主要包括(ABCD)
3.管理问题分析与确定的方法与技术主要有(BCD)
3.建立竞争优势的基础主要包括(ABCD)
4.来自管理者自身的创造力直接来源有(ABCD)
B.知识、经验与技能
四、简述题
1.编制计划的要领有哪些?
正确答案:
(答案要点)
第一,明确制定计划的目的与依据;
第二,抓住四个环节,按照科学程序运作;
第三,要着重关注中基层管理者所负责的计划类型。
答案讲解:
编制计划要关注的要领
2.试述分析与解决管理问题的基本程序
正确答案:
(答案要点)
第一阶段:
发现问题
⑴明确标准
⑵建立高效的环境扫瞄系统,对管理活动与环境进行实时监测,搜集相关信息。
⑶以预期标准为依据,对所扫描到的信息进行比较衡量,以确定是否出现差异,即问题。
⑷如发现问题,就对出现的问题进行客观、全面、准确的描述
第二阶段:
界定问题。
⑴经过认真分析,确定管理问题的性质与程度
⑵分析造成这一问题的原因与深层根源。
⑶对与这一问题相关的环境与条件作出分析与评价。
⑷在分析界定问题的基础上,提出破解如何管理问题的方向。
第三阶段:
解决问题。
⑴确定解决问题的工作目标。
⑵激发并形成解决问题的创意。
⑶制定体现创意、解决问题的可行方案。
⑷将方案付诸实施,并进行跟踪控制,作必要的调整,以确保问题的圆满解决。
答案讲解:
分析与解决管理问题的基本程序
五、计算题
1.某厂生产一种产品,其固定成本为200000元,单位产品变动成本为10元,产品销价为15元。
求:
(1)该长的盈亏平衡点产量应为多少?
(2)如果要实现利润20000元,其产量应为多少?
正确答案:
(1)
即当产量为40000件时,处于盈亏平衡点上。
(2)
即当产量为44000件时,企业可获利20000元。
答案讲解:
盈亏平衡方法的使用基本技巧
第四章组织职能
一、判断题
1.管理层次较少,而管理幅度较大的组织结构称为直线组织形式。
(×)
2.最早和最简单的组织形式是矩阵制。
(×)
3.组织结构中人员组合最基本的原理是同素异构原理。
(√)
4.奖酬是各类组织中基层管理者重要的管理内容与最基本的激励手段。
(√)
二、单项选择题
1.组织结构的内涵是人们的(C)关系。
C.职、权、责
2.(A)是指规定组织构成和组织方式、决定组织性质的基本制度。
3.人员考核最基本的要求是必须坚持(D)的原则。
三、多项选择题
1.组织结构的影响因素(ABCD)
2.下列属于扁平型管理结构的是(ABC)
3.规范制度的基本功能主要有(ABD)
4.管理人员选聘的方式(AC)
5.对员工进行考核,从管理者的角度看,主要目的有(CD)
四、简述题
1.简述矩阵制的结构特点。
正确答案:
(答案要点)
矩阵制是由按职能划分的纵向指挥系统与按项目组成的横向系统结合而成的组织。
优点:
纵横结合,有利于配合;人员组合富有弹性。
缺点:
破坏命令统一原则。
适用:
主要适用于突击性、临时性任务。
答案讲解:
矩阵制的结构特点
2.简述人员考核的作用
正确答案:
(答案要点)
(1)考核有利于评价、监督和促进员工的工作,有明显的激励作用;
(2)为确定员工的劳动报酬与其他待遇提供科学依据;(3)个人认识自我、组织进行考核,促进员工的全面发展创造条件;(4)有利于管理者了解下属,以便进行合理的岗位调整及职务晋升。
答案讲解:
人员考核的作用
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 离散 课后 习题 答案
![提示](https://static.bingdoc.com/images/bang_tan.gif)