科学院离散数学1995答案历年考研真题2010-年2013笔记加

中国科学院软件所abAaTbaRbbRabRaaRbbTa，TRaaRa为真，而aTaaRaaRaaRaaTaT若R是传递的，aRbaRcaRcaTbaTcaRbbRabRc(aRbbRc)(cRbaRccRaaTc,T是传递的。T为等价关系，Raxaxayaya使axyx,yaaa之前的两aaa是置位元素b1b2，显然b1ab2a，且b1b2a,aAaa本身为并不可约元，且aaa，如a至少有两个置位元素b1b2，则ab1b2b1b2若都2止，最后ac1c2ck。其中cii1,k里如果出现cicj,cicj，则用cj代cicj替，另ci用代替cici，证证明：令SLSR,(aH)是映射，即对每一个元素均有效，若aHbH，则baH，H是子群ab(ba)HHaHb，即(aH(bH任取HbSR,bHSL，使(bH)Hb 是满射若(aH)(aH)HbHaHa，即aaH a1Ha2H，为单射。综上知是SL到SR的双射。G是有限群，SLSR|SL||SR四．G中存在v0V(Gd(V0k2G在中对这些结点至多用k-2种颜即至少还有k-1种颜色中的一种未使用，Gk-1(G)k矛盾。故不可，(Gk1x11x12x1p，(Gk，pkx1iL上Lx1iL与是最长通路矛盾，x11x12x1pL在上lk12）用反证法。设G{x1x2xk}xk1xk2xl是一条通路，它在一个连通片中，令Cxk1xk2xl不在的那个连通片。在C中有长m的最长通路y0y1ym。由1）dcy0m，在图G中，令imin{j|xj与y0相邻，通路xlxl1xi1xiy0y1ymG中长为lmi1。由于L是最长路lmi1l1im2。由此看出x1x2xk中至多有km1y0相邻。所以：d(y0)dc(y0)(km1)m(km1)k与(Gk矛盾，Gx1x2xk1）用反证法。若G不连通，它至少有两个连通片G1G2，取u1V(G1u2V(G2d(u1d(u2|V(G1||V(G2|2n2与已知条件矛盾，G是连通的。2）设Lv1v2vlvl1是G的最长通路，显然ln1。由于L是G的最长通路v1vl1的邻点L都在上，令v1的邻点vj1vj2,vjk，如果vj11,vj21,vjk1都不与vl1相邻，那d(v1)d(vl1)ln1n，与已知条件矛盾。于是存在一个i，使vi1与v1相邻，vi与vl1相邻，构造长为l+1的回路C:v1v2vivl1vlvi1v1。如果ln1，G中必有不在L上的结点w，由于G连通，w与L上的一个结点vp相邻，2vpl.当2piwvpvp1v1vi1vi2vl1vivi1vp1是G中长l+1为的通路当i1plwvpvp1vl1vivi1v1vi1vi2vp1是G中长l+1为的通路回路，G是哈密尔顿图。七．(PQ)RPQRRP(PQR)(PQR)(PQR)(PQR)(PQ)R((PQ)R)((PQ)R)(PQR)(PQR)(PQR)(PQ八．1）RRQPR(R(QPRQP2）P(xyxy对任何x都能找到y=x+1，显然x<y。xyP(xy为T，对任何y存在x=y+1，使x不小于y，yxP(x,y)为F.九．x(P(x)yQy)yR(x,x(P(x)yz(Q(z)R(x,xyz(P(x)(Q(z)R(x,十．1)c1P(xxQ(xx是素数R(xyxy。x(P(x)Q(x)R(x,c1))x(Q(x)(P(x)R(x,c12)x(A(x)B