张清华图论课后题答案..docx

图论预备知识解：(1) p={,{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}}(2) p={,{a},{{b,c}},{a,{b,c}}}(3) p={,{}}(4) p={,{},{{}},{,{}}}(5)p={,{{a,b}},{{a,a,b}},{{a,b,a,b}},{{a,b},{a,a,b}},{{a,b},{a,b,a,b}},{{a,b},{a,a,b},{a,b,a,b}}}1.2 解：(1) 真 (2) 假 (3)假 (4)假1.3 解：(1) 不成立，A={1} B={1,2} C={2} (2) 不成立，A={1} B={1,2} C={1,3}1.4 证明：设(x,y)∈(A∩B)X(C∩D) 说明x∈A∩B,y∈C∩D 由于 x∈A,y∈C所以 (x,y) ∈A X C 由于x∈B,y∈D所以 (x,y) ∈B X D 所以 (x,y) ∈（A X C）∩（B X D） 反过来，如果（x,y）∈(A X C) ∩（B X D） 由于 (x,y) ∈（A X C）所以 x∈A,y∈C 由于 (x,y) ∈（B X D）所以x∈B,y∈D 所以x∈(A∩B) y∈(C∩D) 所以 (x,y) ∈(A∩B)X(C∩D) 所以(A∩B)X(C∩D)= (A X C) ∩（B X D）1.5 解：Hasse图12249431025极大元{9,24,10,7}极小元{3,2,5,7}最大元{24}最小元{2}1.6 解 (1)R={x,y|x整除y}468(2)关系图为：9102571(3)不存在最大元，最小元为{2}1.7 解：(1)R={1,1,2,2,3,3,4,4,1,2,2,1,2,3,3,2}略IAR 故R是自反的。1,2R 2,3R 但是1,3R 故不满足传递性1.8 解：(1) 不成立 A={1} B={2} C={3} D={4} 则左式={1,3，1,4,2,3,2,4}右式={1,3,2,4}不成立 A={1,3} B={1} C={2,4} D={2} 则左式={3,4}右式={1,4,3,2,3,4}不成立 A={1} B={2} C={3} D={4} 则左式={1,3,1,4,2,3,2,4}右式={1,3,2,4}成立 证明：设x,y(A-B)X C x(A-B)∧ yCxA∧xB∧ yCx,yA X C∧x,yB X Cx,y(A X C)-(B XC) 故得 （A-B）X C=（A X C）-（B X C）1.9 略1.10略1.11 解：A为n个元素的优先级和，A上有2n2 个 不同的二元关系，理由为：设A，B为集合，AXB的任何子集所定义的二元关系称作从A到B的二元关系，特别当A=B时，称作A上的二元关系，若|A|=n，则|AXA|=n2，那么A上共有2n2个不同的二元关系。1.12略1.13 解：1)真.由于R1和R2和R2都是自反的,因而对任何,都有(x,x)∈R1,(x,x)∈R2.因此,对任何x∈A,都有(x,x)∈R1R2.所以R1R2是自反的。2)假.令A={a,b},R1={(a,b)},R2={b,a}.那么R1R2={(a,a)},它就不是A上的反自反关系.3)假.令A={a,b,c},R1={(a,b),(b,a)},R2={(b,c),(c,b)}.那末R1R2={(a,c)},就不是A的对称关系.4)假.令A={a,b,c,d},R1={(a,c),(b,c)},R2={(c,b),(d,a)}易证R1,R2都是反对称关系.但是R1R2={(a,b),(b,a)}就不是A上的反对称关系.5)假.令A={a,b,c},R1={(a,c),(b,a),(b,c)},R2={(c,b),(a,c),(a,b)},易证R1和R2都是传递关∈系,但R1R2={(a,b),(b,b),(b,c)}就不是A上的传递关系.1.14 证明：由任意的a，存在一个b，使得a,b∈R,由对称性所以b,a∈R,由传递性a,a∈R,所以R是等价关系。1.15 证明：①x∈A，x,x∈R,x,x∈S→x,x∈R∩S，所以R∩S有自反性；②x,y∈A,因为R,S是反对称的，x,y∈R∩S∧y,x∈R∩S(x,y∈R∧x,y∈S) ∧(y,x∈R∧y,x∈S)(x,y∈R∧y,x∈R) ∧(x,y∈S∧y,x∈S)x=y∧y=xx=y所以，R∩S有反对称性。③x,y,z∈A,因为R,S是传递的，x,y∈R∩S∧y,z∈R∩Sx,y∈R∧x,y∈S∧y,z∈R∧y,z∈Sx,y∈R∧y,z∈R∧x,y∈S∧y,z∈Sx,z∈R∧x,z∈Sx,z∈R∩S所以，R∩S有传递性。所以R∩S也是A上的偏序关系。1.16 解：r(R)={1,1