离散数学作业答案.docx

资源描述

离散数学作业答案.docx

《离散数学作业答案.docx》由会员分享，可在线阅读，更多相关《离散数学作业答案.docx（12页珍藏版）》请在冰点文库上搜索。

离散数学作业答案.docx

离散数学作业答案

【篇一：

2014离散数学作业5答案】

散数学图论部分形成性考核书面作业

本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型（除单项选择题外）安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。

本次形考书面作业是第二次作业，大家要认真及时地完成图论部分的综合练习作业。

要求：

将此作业用a4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，要求本学期第15周末前完成并上交任课教师（不收电子稿）。

并在05任务界面下方点击“保存”和“交卷”按钮，以便教师评分。

一、填空题

1．已知图g中有1个1度结点，2个2度结点，3个3度结点，4个4度结点，则g的边数是15．

2．设给定图g（如右由图所示），则图g的点割集是．

3．设g是一个图，结点集合为v，边集合为e，则g的结点等于边数的两倍．

4．无向图g存在欧拉回路，当且仅当g连通且5．设g=v，e是具有n个结点的简单图，若在g中每一对结点度数之和大于等于n-1，则在g中存在一条汉密尔顿路．

6．若图g=v,e中具有一条汉密尔顿回路，则对于结点集v的每个非空子集s，在g中删除s中的所有结点得到的连通分支数为w，则s中结点数|s|与w满足的关系式为w?

|s|．

7．设完全图kn有n个结点（n?

2），m条边，当n为奇数时，kn中存在欧拉回路．

8．结点数v与边数e满足-关系的无向连通图就是树．9．设图g是有6个结点的连通图，结点的总度数为18，则可从g中删去

10．设正则5叉树的树叶数为17，则分支数为i

二、判断说明题（判断下列各题，并说明理由．）

1．如果图g是无向图，且其结点度数均为偶数，则图g存在一条欧拉回路．．

错。

缺了一个条件，图g应该是连通图。

如反例，图g是一个有孤立结点的图。

2．如下图所示的图g存在一条欧拉回路．

错。

图中有奇数度结点，所以不存在欧拉回路。

3．如下图所示的图g不是欧拉图而是汉密尔顿图．

对。

因为图中结点a、b、d、f的度数都为奇数，所以不是欧拉图。

如果沿着（a,d,g,f,e,b,c,a），这样除起点和终点是a外，经过每个点一次且仅一次，所以存在一条汉密尔顿回路，是汉密尔顿图。

4．设g是一个有7个结点16条边的连通图，则g为平面图．

错。

假设图g是连通的平面图，根据定理，结点数为v，边数为e，应满足e?

3v-6，但现在16?

3*7-6，显然不成立，所以假设错误。

5．设g是一个连通平面图，且有6个结点11条边，则g有7个面．对。

根据欧拉定理，有v-e+r=2，结点数v=11，边数e=6，代入公式求出面数r=7。

三、计算题

1．设g=v，e，v={v1，v2，v3，v4，v5}，e={（v1,v3），（v2,v3），（v2,v4），（v3,v4），（v3,v5），（v4,v5）}，试

（1）给出g的图形表示；

（2）写出其邻接矩阵；（3）求出每个结点的度数；（4）画出其补图的图形．

v1?

00100?

00110?

11011?

01101?

00110?

（3）1，2，4，3，2。

（4）v2

2．图g=v,e={a,b,c,d,e}，e={（a,b）,（a,c）,（a,e）,（b,d）,（b,e）,?

，其中v4v，对应边的权值依次为3（c,e）,（c,d）,（d,e）}2、1、2、3、6、1、4及5，试

（1）画出g的图形；

（2）写出g的邻接矩阵；（3）求出g权最小的生成树及其权值．

0110

10011?

01101?

11110?

（3）a

权值w（t）=1+1+2+3=7

3．已知带权图g如右图所示．

（1）求图g的最小生成树；

（2）计算该生成树的权值．

（1）

（2）权值（1+2+3+5+7）=18

4．设有一组权为2,3,5,7,17,31，试画出相应的最优二叉树，计算该最优二叉树的权．

四、证明题

权为2*5+3*5+5*4+7*3+17*2+31=131

1．设g是一个n阶无向简单图，n是大于等于3的奇数．证明图g与它的补图g中的奇数度顶点个数相等．

证明：

设g?

v,e?

，?

v,e?

．则e?

是由n阶无向完全图kn的边删去e所得到的．所以对于任意结点u?

v，u在g和g中的度数之和等于u在kn中的度数．由于n是大于等于3的奇数，从而kn的每个结点都是偶数度的（n?

1（?

2）度），于是若u?

v在g中是奇数度结点，则它在g中也是奇数度结点．故图g与它的补图g中的奇数度结点个数相等．

【篇二：

2014离散数学作业3答案】

离散数学集合论部分形成性考核书面作业

本次形考书面作业是第一次作业，大家要认真及时地完成集合论部分的综合练习作业。

要求：

将此作业用a4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，要求本学期第11周末前完成并上交任课教师（不收电子稿）。

并在03任务界面下方点击“保存”和“交卷”按钮，完成并上交任课教师。

一、填空题1．设集合a?

{1,2,3},b?

{1,2}，则p（a）-p（ba?

b．

2．设集合a有10个元素，那么a的幂集合p（a）的元素个数为．

3．设集合a={0,1,2,3}，b={2,3,4,5}，r是a到b的二元关系，

x,y?

a且y?

b且x,y?

b}则r的有序对集合为{2,2,2,3,3,2,3,3}．

4．设集合a={1,2,3,4}，b={6,8,12}，a到b的二元关系

r＝{?

x,y?

2x,x?

a,y?

那么r－1＝{6,3,8,4}5．设集合a=｛a,b,c,d｝，a上的二元关系r={a,b,b,a,b,c,c,d}，则r具有的性质是没有任何性质．

6．设集合a=｛a,b,c,d｝，a上的二元关系r={a,a,b,b,b,c,c,d}，若在r中再增加两个元素{c,b,d,c}，则新得到的关系就具有对称性．7．如果r1和r2是a上的自反关系，则r1∪r2，r1∩r2，r1-r2中自反关系有2个．

8．设a={1,2}上的二元关系为r={x,y|x?

a，y?

a,x+y=10}

，则r的自反闭包为{1,1,2,2}．

9．设r是集合a上的等价关系，且1,2,3是a中的元素，则r中至少包含1,1,2,2,3,3等元素．

10．设集合a={1,2}，b={a,b}，那么集合a到b的双射函数是或{1,b,2,a}．

二、判断说明题（判断下列各题，并说明理由．）

1．若集合a={1，2，3}上的二元关系r={1,1，2,2，1,2}，则

（1）r是自反的关系；

（2）r是对称的关系．解：

（1）错误。

r不具有自反的关系，因为3,3不属于r。

（2）错误。

r不具有对称的关系，因为2,1不属于r。

2．如果r1和r2是a上的自反关系，判断结论：

“r-11、r1∪r2、r1∩r2是自反的”是否成立？

并说明理由．解：

成立。

因为r1和r2是a上的自反关系，即ia?

r1，ia?

r2。

由逆关系定义和ia?

r1，得ia?

r1-1；

由ia?

r1，ia?

r2，得ia?

r1∪r2，ia?

r1?

r2。

所以，r1-1、r1∪r2、r1?

r2是自反的。

a3．若偏序集a，r的哈斯图如图一所示，

bcg

则集合a的最大元为a，最小元不存在．解：

错误。

集合a的最大元不存在，a是极大元。

4．设集合a={1,2,3,4}，b={2,4,6,8}，，判断下列关系f是否构成函数f：

b，并说明理由．

（1）f={1,4,2,2,,4,6,1,8}；

（2）f={1,6,3,4,2,2}；（3）f={1,8,2,6,3,4,4,2,}．

解：

（1）不构成函数。

因为对于3属于a，在b中没有元素与之对应。

（2）不构成函数。

因为对于4属于a，在b中没有元素与之对应。

（3）构成函数。

因为a中任意一个元素都有a中唯一的元素相对应。

三、计算题

1．设e?

{1,2,3,4,5},a?

{1,4},b?

{1,2,5},c?

{2,4}，求：

（1）（a?

b）?

~c；

（2）（a?

b）-（b?

a）（3）p（a）－p（c）；（4）a?

b．

解：

（1）（a?

b）?

~c={1}?

{1,3,5}?

{1,3,5}

（2）（a?

b）-（b?

a）={1，2,4,5}-{1}={2,4,5}

（3）p（a）?

p（c）?

{1},{4},{1,4}}?

{2},{4},{2,4}}?

{{1},{1,4}}（4）a?

b=（a?

b）－（a?

b）={1,2,4,5}?

{1}?

{2,4,5}

2．设a={{1},{2},1,2}，b={1,2,{1,2}}，试计算

解：

（1）a?

b={{1},{2}}

3．设a={1，2，3，4，5}，r={x，y|x?

a，y?

a且x+y?

4}，s={x，y|x?

a，y?

a且x+y0}，试求r，s，r?

s，s?

r，r-1，s-1，r（s），s（r）．

解：

r={1,1,1,2,1,3,2,1,2,2,3,1}

s=空集r?

s=空集s?

r=空集

r-1={1,1,2,1,3,1,1,2,2,2,1,3}s-1=空集

r（s）={1,1,2,2,3,3,4,4,5,5}

s（r）={1,1,1,2,1,3,2,1,2,2,3,1}

4．设a={1,2,3,4,5,6,7,8}，r是a上的整除关系，b={2,4,6}．

（1）写出关系r的表示式；

（2）画出关系r的哈斯图；（3）求出集合b的最大元、最小元．

解

（1）r={1,1,1,2,1,3,1,4,1,5,1,6,1,7,1,8,2,2,2,4,2,6,2,8,3,3,3,6,4,4,4,8,5,5,6,6,7,7,8,8}

（3）集合b没有最大元，最小元是2

四、证明题

1．试证明集合等式：

（b?

c）=（a?

b）?

（a?

c）．证明：

设，若x∈a?

（b?

c），则x∈a或x∈b?

c，

即x∈a或x∈b且x∈a或x∈c．即x∈a?

b且x∈a?

c，即x∈t=（a?

b）?

（a?

c），

所以a?

（b?

c）?

（a?

b）?

（a?

c）．

反之，若x∈（a?

b）?

（a?

c），则x∈a?

b且x∈a?

c，即x∈a或x∈b且x∈a或x∈c，

即x∈a或x∈b?

c，即x∈a?

（b?

c），

所以（a?

b）?

（a?

c）?

（b?

c）．因此．a?

（b?

c）=（a?

b）?

（a?

c）．

2．试证明集合等式a?

（b?

c）=（a?

b）?

（a?

c）．

证明：

设s=a∩（b∪c），t=（a∩b）∪（a∩c），若x∈s，则x∈a且x∈b∪c，即x∈a且x∈b或x∈a且x∈c，

也即x∈a∩b或x∈a∩c，即x∈t，所以s?

t．反之，若x∈t，则x∈a∩b或x∈a∩c，即x∈a且x∈b或x∈a且x∈c

也即x∈a且x∈b∪c，即x∈s，所以t?

s．因此t=s．

【篇三：

离散数学作业5答案[1]1】

离散数学图论部分形成性考核书面作业

本课程形成性考核书面作业共3次，内容主要分别是图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。

本次形考书面作业是第二次作业，大家要认真及时地完成图论部分的综合练习作业。

要求：

将此作业用a4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，完成并上交任课教师（不收电子稿）。

并在07任务界面下方点击“保存”和“交卷”按钮，以便教师评分。

一、单项选择题

1．设图g的邻接矩阵为?

00111000001001

，则g的边数为（d）．?

a．5b．6c．3d．42．设图g＝v,e，则下列结论成立的是（c）．a．deg（v）=2?

b．deg（v）=?

c．?

deg（v）?

2ed．?

deg（v）?

3．设有向图（a）、（b）、（c）与（d）如下图所示，则下列结论成立的是（a）．

a．（a）是强连通的b．（b）是强连通的c．（c）是强连通的d．（d）是强连通的4．给定无向图g如右图所示，下面给出的结点集子集中，不是点割集的为（b）．

a．{b,d}b．{d}

bc4题图d

c．{a,c}d．{b,e}

5．图g如右图所示，以下说法正确的是（c）．a．{（a,c）}是割边b．{（a,c）}是边割集c．{（b,c）}是边割集d．{（a,c）,（b,c）}是边割集

6．无向图g存在欧拉通路，当且仅当（d）．a．g中所有结点的度数全为偶数b．g中至多有两个奇数度结点c．g连通且所有结点的度数全为偶数d．g连通且至多有两个奇数度结点

7．若g是一个欧拉图，则g一定是（c）．

a．平面图b．汉密尔顿图c．连通图d．对偶图

8．设g是连通平面图，有v个结点，e条边，r个面，则r=（a）．a．e－v＋2b．v＋e－2c．e－v－2d．e＋v＋2

9．设g是有n个结点，m条边的连通图，必须删去g的（a）条边，才能确定g的一棵生成树．

a．m?

1b．m?

nc．m?

1d．n?

110．已知一棵无向树t中有8个结点，4度，3度，2度的分支点各一个，t的树叶数为（b）．

a．8b．5c．4d．3

二、填空题

1．已知图g中有1个1度结点，2个2度结点，3个3度结点，4个4度结点，则g的边数是15．

2．设给定图g（如右由图所示），则图g的点割集是

3．设g是一个图，结点集合为v，边集合为e，则g的结点等于边数的两倍．

4．设有向图d为欧拉图，则图d中每个结点的入度5．设g=v，e是具有n个结点的简单图，若在g中每一对结点度数之和大于等于n-1，则在g中存在一条汉密尔顿路．

6．设无向图g＝v，e是汉密尔顿图，则v的任意非空子集v1，都有v1?

．

7．设完全图kn有n个结点（n?

2），m条边，当当m=2n时，kn中存在欧拉回路．

8．设图g?

v,e?

，其中?

n，?

m．则图g是树当且仅当g

是连通的，

b5题图ad

且m?

n-1．

9．连通无向图g有6个顶点9条边，从g中删去条边才有可能得到g的一棵生成树t．

10．设正则5叉树的树叶数为17，则分支数为i

三、判断说明题（判断下列各题，并说明理由．）

1．

（1）如果图g是无向图，且其结点度数均为偶数，则图g存在一条欧拉回路．．

（2）图g1，（如下图所示）是欧拉图．

解：

（1）错，图g是无向图，当且仅当g是连通的，且所有结点度数均为偶数，这里不能确定g图是否是连通的。

（2）对，由欧拉图的定理“无向图g具有一条欧拉路，当且仅当g是连通的，且有零个或两个奇数度结点”得到，这里可找到如下一条欧拉回路v4v5v2v6v4v1v2v3v4。

2．图g2（如下图所示）不是欧拉图而是汉密尔顿图．

解：

对，由欧拉图的定理“无向图g具有一条欧拉路，当且仅当g是连通的，且有零个或两个奇数度结点”，这里结点a,b,d,f的度数都为奇数；它是汉密尔顿图，因为找到了如下一条汉密尔顿回路abefgdca。

3．

（1）设g是一个有7个结点16条边的连通图，则g为平面图．

（2）设g是一个连通平面图，且有6个结点11条边，则g有7个面．

解：

（1）错，没有提到面。

（2）对，由欧拉定理得到：

结点-边+面=2，即为连通平面图，这里6-11+7=2

4．下图给出的树是否同构的．

解：

（a）不与（b）、（c）同构，但（b）、（c）同构。

因为由图的同构相关联，得到同构的必要条件：

（1）结点数目相同；

（2）边数相同；（3）度数相同的结点数目相同。

四、计算题

1．设g=v，e，v={v1，v2，v3，v4，v5}，e={（v1,v3），（v2,v3），（v2,v4），（v3,v4），（v3,v5），（v4,v5）}，试

（1）给出g的图形表示；

（2）写出其邻接矩阵；（3）求出每个结点的度数；（4）画出其补图的图形．解：

（1）g的图形如下

（2）g=?

011011011011010?

（3）v1度数为1，v2度数为2，v3度数为4，v4度数为3，v5度数为2

（4）其补图的图形如下

2．图g=v,e，其中v={a,b,c,d,e,f}，e={（a,b）,（a,c）,（a,e）,（b,d）,（b,e）,（c,e）,（d,e）,（d,f）,（e,f）}，对应边的权值依次为5，2，1，2，6，1，9，3及8．

（1）画出g的图形；

（2）写出g的邻接矩阵；（3）求出g权最小的生成树及其权值．

解：

（1）g的图形如下

（2）g=?

001

11101?

00110?

100001001111

（3）最小{（a,e）,（e,c）,（b,d）,（d,f）,（a,b）}权值为

1+1+2+3+5=12

3．已知带权图g如右图所示．

（1）求图g的最小生成树；

（2）计算该生成树的权值．

解：

（1）最小生成树为

{1,3,2,7,5}

（2）权值为1+2+3+5+7=18

4．设有一组权为2,3,5,7,17,31，试画出相应的最优二叉树，计算该最优二叉树的权．

解：

（1）相应的最优二叉树图如下

展开阅读全文