中国科学院软件所 一九九四年招收硕士学位研究生入学考试试题答案 试题名称：离散数学 一． 1．×．如，，。 2．×.不一定有传递性，如取，，但 。 3．√. 4．×.是交换群，但不一定是。 5．√. 二．[证]： 自反性：，， 对称性：如果，则使且， 对称，且，。 传递性：如果， 则 使且 使且  由1）2）3）知S是等价关系。 三．[证] 单位元，，H是G的非空子集，对，设a的阶为m, b的阶为n，则  是有限阶元，,是的子群，又是交换群，是正规子群。 2)对且，假设的阶有限，为s作到 的自然同态f，即对， = 即为有限元。 g为有限元， 与假设矛盾！ 的阶是无限的，原命题得证。 四．[证]： 用反证法。假设H不是连通图，设为图H的连通分支 图H不含孤立点。 不是孤立点，即的顶点数， 边数。 H的边数  =   即：    从而不是平面图，与已知矛盾！ H为连通图。 五．[证]： 完全图的邻接距阵，E为元素全是1的距阵，则长为k的路的数目由决定. =  若以记从到的长为k的路的数目，则：  六．[证]： 在有向图D中任取一结点，由于所有结点的入度都大于1，所以射入该结点的有向边数，沿射入的某一条有向边反向到达D的另一结点，再对这样做，得。得到的有向迹其中必存在一有向圈。设a是此有向迹中最小的标号，使得，中都不含有向圈，而中含有向圈。 现从D中去掉这一段有向迹，得到有向图，其所有结点入度显然都大于0，与上同理，从某点出发，沿某条有向边反向达到的另一结点……，可知中仍有一有向圈。 和即为有向图的两个不同的有向圈。 七.1,3,4,5,是永真式,2不是永真式. 八.1. 2. 3.