哈工大离散数学dit06.doc

应用计算机数学05DIT （本试卷满分70分，任选14题，每题5分） 1．设A,B,C都是集合，若且，试证B=C。 证：证法1 对，若，则。由于故，；若，，，故又，只能有。，总有，。同理，因。 证法2 2．设A、B是集合，证明 证：时，显然，得证假设，必存在但，故与题设矛盾所以假设不成立，故。 (2)(3) 解：（1），（2）都不成立。反例如下： （1），则。 （2），则。 4.设A,B,C是任意三个集合，则 证：，有且，即且 但。于是，但，从而有,故 ，反之设，有，，于是有：且但，从而且即，于是。 由集合相等定义有： 5．设，证明：f是满射。 证：（2） 显然 假设f不是满射，则，使得，。于是 令，有， 由题意得，矛盾。 故f一定为满射。 6．设，试构造两个映射f和g：，使得但。 解：但，故f是满射，但f不是单射。于是令： ，，则 但。 事实上，当n＝1时，，故。 7.设，则若gf是是单射，则f是单射吗？说明理由。 解：f是单射。 假设f不是单射，则使得于是 即。 这与gf是是单射矛盾，所以f是单射。 8．是否存在一个同时不满足自反性，对称性，反对称性，传递性和反自反性的二元关系？ 解：存在。设，R是X的。 设R是X上的二元关系，证明：是对称的二元关系。 证：证Ⅰ，故是对称的。 证Ⅱ，或即或。，因此是对称的。 设R是X上的二元关系，试证==。 证：。 11．是否存在X（X=n）上的一个关系R使得两两不相等。 解：存在。 设，R是X上的二元关系且即可。 若且，则。 证：R是A上的等价关系。 若且，由R的对称性有：且， 由R的传递性有： R是自反的，故有。 若，由有，所以R是对称的。 若且，由R的对称性有：且， 故由题意得，所以R是传递。 因此，R是A上的等价关系。 13．任意非平凡树都是偶图。 证：任一非平凡树无圈，即圈长为零，零是偶数，所以任一非平凡树都是偶图。 14．证明具有奇数个顶点的偶图不是哈密顿图。 证：设G=({V1,V2},E)，因为G有奇数个顶点，故|V1|≠|V2|。 （1）若|V1|＞|V2|，则w(G-V2)=V1＞V2，由定理知，G不是哈密顿图。 （2）若|V1|＜|V2|，则w(G-V1)=V2＞V1，由定理知，G不是哈密顿图。 综上可知，G不是哈密顿图 15. 列出无向树的特征性质（至少5个）。 答：(1)G是树，即G是连通且无圈的无向图；(2)G任两不同顶点间有唯一路； (3)G连通且p=q+1；(4)G无圈且p=q+1；(5)G无圈且任加一边有唯一圈； (6)G连通且任去一边得不连同图。 16．一棵树T有n2个度为2的顶点，n3个度为3的顶点，…，nk个度为k的顶点，则T有多少个度为1的顶点？ 解：设T有x个度为1的顶点。 由∑degv=2q且q=p-1，p=n2+n3+…+nk,得 2×n2+3×n3+…+k×nk+1×x=2(n2+n3+…+nk-1)，得 x=n3+2n4+…+(k-2)nk+2。 17. 若G是顶点数p≥11的平面图，试证Gc不是平面图。 证:平面图中边数满足。边数， 若要，则要它大于 故当时，不是平面图。 18.一个没有有向回路的有向图中至少有一个出度(入度)为零的顶点。 证：设D=(V，A)是一个没有有向回路的有向图。考虑中任一条最长的有向路的最后顶点v，则od(v)=０。因为若od(v)≠０，则必有一个顶点u使得(v，u)∈ A。于是，若u不在此最长路上，则此最长路便不是中的最长路，这是与前面的假设相矛盾。若u在此最长路上，则D中有有向回路，这又与定理的假设相矛盾。因此，od(v)=０。 19. 设=(V，A)是一个有根树，其每个顶点的出度不是0就是2。若有n个叶子，试求的弧的条数。 解:设有p个顶点q条弧，则q=p-1。故中所有顶点的入度之和为p-1，而所得顶点的出度之和为2(p-n)。所以，2(p-n)=p-1。 因此，p=2n-1。把p=2n-1代入q=p-1中便得q=2(n-1)。所以，中有2(n-1)条弧。 20.证明一棵正则二元树T必有奇数个顶点。 证1：设T为一棵正则二元树，有p个顶点，q条弧。 因为T的每个顶点关联两条弧，所以T有偶数条边，又p=q+1，故p为奇数。 证2：设T有p个顶点，n0个叶子，n2个分支点，则由 P=n0+n2且n0=n2+1 得p=2n2+1，故p为奇数。 4