资源描述：
《哈工大离散数学dit06.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、个人收集整理勿做商业用途应用计算机数学05DIＴ（本试卷满分70分，任选１4题,每题5分）1．设A,Ｂ,Ｃ都是集合，若且,试证B=C。证:证法1 对,则若,则。由于，故,即;若,则,由于,故。又,只能有。因此,，总有,故。同理可证,。因此。证法２ 2.设A、B是集合,证明:证：当时,显然,得证。假设，则必存在,使得但,故与题设矛盾。所以假设不成立，故。3．下列命题是否成立?(1）(2)(3)解：(1)，（２）都不成立。反例如下：（１),则。(2),则。4.设A，Ｂ,C是任意三个集合，则证：，有且，即且但。于是,但，从而有,故个人收集
2、整理勿做商业用途，反之设，有，，于是有：且但，从而且即,于是。由集合相等定义有:5.设，证明：ｆ是满射。证:(2） 显然假设f不是满射，则，使得,。于是令，有,由题意得，矛盾。故f一定为满射。６.设，试构造两个映射ｆ和g：,使得但。解：但,故f是满射,但ｆ不是单射。于是令：,,则但。事实上,当n＝1时，，故。7.设，则若gf是是单射，则f是单射吗?说明理由。解:f是单射。假设f不是单射，则使得于是即。这与gf是是单射矛盾,所以ｆ是单射。８.是否存在一个同时不满足自反性,对称性，反对称性,传递性和反自反性的二元关系？解:存在。设,R是X上
3、的二元关系。９.设R是Ｘ上的二元关系,证明：是对称的二元关系。证：证Ⅰ,故是对称的。个人收集整理勿做商业用途证Ⅱ，则或,即或。于是，因此是对称的。10．设R是X上的二元关系,试证:==。证:。11．是否存在X(Ｘ＝n）上的一个二元关系R使得两两不相等。解：存在。设，Ｒ是X上的二元关系且即可。12．设Ｒ是A上的一个自反关系,证明:Ｒ是等价关系若且，则。证:R是A上的等价关系。若且,由R的对称性有：且,由R的传递性有:R是自反的，故有。若,由有，所以R是对称的。若且,由R的对称性有：且,故由题意得，所以Ｒ是传递。因此，Ｒ是A上的等价关系。1
4、3．任意非平凡树都是偶图。证：任一非平凡树无圈,即圈长为零，零是偶数,所以任一非平凡树都是偶图。14.证明具有奇数个顶点的偶图不是哈密顿图。证:设G=({Ｖ1,V2｝,E)，因为G有奇数个顶点，故
5、V１
6、≠
7、V２
8、。（1)若
9、Ｖ1
10、>｜V2｜，则w（G-Ｖ２)=V1＞V2,由定理知,G不是哈密顿图。(2）若｜V1
11、＜
12、V2
13、,则w(Ｇ-V1)＝V2>Ｖ1,由定理知，G不是哈密顿图。综上可知,Ｇ不是哈密顿图15.列出无向树的特征性质(至少5个）。答：(1）Ｇ是树,即G是连通且无圈的无向图;（2）G任两不同顶点间有唯一路；(3)G连通且p=
14、q+1;(4)G无圈且p=q+1；(５）G无圈且任加一边有唯一圈；（6)G连通且任去一边得不连同图。个人收集整理勿做商业用途16.一棵树Ｔ有n2个度为２的顶点,n3个度为3的顶点,…，nk个度为k的顶点，则Ｔ有多少个度为1的顶点?解:设T有x个度为1的顶点。由∑deｇv＝2q且q=p－1,p=n2+n3+…+ｎk，得２×n2+３×n３+…＋k×nk＋1×ｘ=2(n2+n3+…+nk-1),得ｘ=n3+2n4+…+（ｋ－2)nｋ＋2。17. 若G是顶点数ｐ≥11的平面图,试证Gｃ不是平面图。证:平面图中边数满足。边数,若要，则要它大于故当
15、时,不是平面图。18.一个没有有向回路的有向图中至少有一个出度(入度)为零的顶点。证:设D=（V,A)是一个没有有向回路的有向图。考虑中任一条最长的有向路的最后顶点v，则ｏｄ(v）＝０。因为若od(v)≠０,则必有一个顶点u使得(ｖ，ｕ)∈A。于是，若u不在此最长路上,则此最长路便不是中的最长路,这是与前面的假设相矛盾。若u在此最长路上,则D中有有向回路,这又与定理的假设相矛盾。因此,ｏd（v)＝0。19. 设=（V，A)是一个有根树，其每个顶点的出度不是０就是2。若有n个叶子，试求的弧的条数。解：设有ｐ个顶点q条弧,则ｑ=p-1。故中
16、所有顶点的入度之和为p－１，而所得顶点的出度之和为２(p-n)。所以,2(p－n)=ｐ－1。因此,p＝２n-1。把p=2n-1代入ｑ=ｐ-１中便得q＝2（n-1）。所以，中有2(n-1)条弧。20.证明一棵正则二元树T必有奇数个顶点。证1：设T为一棵正则二元树,有p个顶点，q条弧。因为T的每个顶点关联两条弧,所以T有偶数条边,又ｐ＝q+1,故p为奇数。证2：设T有ｐ个顶点,ｎ0个叶子，ｎ2个分支点，则由Ｐ=n0＋n2且n0＝n２＋１得ｐ＝2ｎ２+1,故p为奇数。
