张清华 图论课后题问题详解

《张清华 图论课后题问题详解》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、实用标准第1章图论预备知识1.1解：(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}

2、1.4证明：设(x,y)∈(A∩B)X(C∩D)说明x∈A∩B,y∈C∩D由于x∈A,y∈C所以(x,y)∈AXC由于x∈B,y∈D所以(x,y)∈BXD所以(x,y)∈（AXC）∩（BXD）反过来，如果（x,y）∈(AXC)∩（BXD）由于(x,y)∈（AXC）所以x∈A,y∈C由于(x,y)∈（BXD）所以x∈B,y∈D所以x∈(A∩B)y∈(C∩D)所以(x,y)∈(A∩B)X(C∩D)所以(A∩B)X(C∩D)=(AXC)∩（BXD）1.5解：Hasse图12249431025文案大全实用标准极大元{9,24,10,7}极小元{3,2,5,7}最大元{24}最小元{2}1.6解

3、(1)R={

4、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>}(2)略(3)IAR故R是自反的。<1,2>R<2,3>R但是<1,3>R故不满足传递性1.8解：(1)不成立A={1}B={2}C={3}D={4}则左式={<1,3>，<1,4>,<2,3>,<2,4>}右式={<1,3>,<2,4>}(2)不成立A={1,3}B={1}C={2,4}D={2}则左式={<3,4>}右式={<1,4>,<3,2>,<3,4>}(3

5、)不成立A={1}B={2}C={3}D={4}则左式={<1,3>,<1,4>,<2,3>,<2,4>}右式={<1,3>,<2,4>}(4)成立证明：设(A-B)XCx(A-B)∧yCxA∧xB∧yCAXC∧BXC(AXC)-(BXC)故得（A-B）XC=（AXC）-（BXC）文案大全实用标准1.9略1.10略1.11解：A为n个元素的优先级和，A上有2n2个不同的二元关系，理由为：设A，B为集合，AXB的任何子集所定义的二元关系称作从A到B的二元关系，特别当A=B时，称作A上的二元关系，若

6、A

7、=n，则

8、AXA

9、=n2，那么A上共有2n2个

10、不同的二元关系。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都是反对称

11、关系.但是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，使得∈R,由对称性所以∈R,由传递性∈R,所以R是等价关系。1.15证明：①x∈A，∈R,∈S→∈R∩S，所以R∩S有自反性；②x,y∈A,因为R,S是反对称的，∈R∩S∧∈R∩S

12、(∈R∧∈S)∧(∈R∧∈S)(∈R∧∈R)∧(∈S∧∈S)x=y∧y=xx=y所以，R∩S有反对称性。③x,y,z∈A,因为R,S是传递的，∈R∩S∧∈R∩S∈R∧∈S∧∈R∧∈S∈R∧∈R∧∈S∧∈S∈R∧∈S∈R∩S所以，R∩S有传