張清華圖論課后題答案

1、第1章圖論預(yù)備知識(shí)圖論預(yù)備知識(shí)1.1解：(1)p=abcabacbcabc?(2)p=?abcabc(3)p=??(4)p=?????(5)p=?abaababababaabababababaababab1.2解：(1)真(2)假(3)假(4)假1.3解：(1)不成立，A=1B=12C=2(2)不成立，A=1B=12C=131.4證明：設(shè)(xy)∈(A∩B)X(C∩D)說明x∈A∩By∈C∩D由于x∈Ay∈C所以(xy)∈AXC由于x∈

2、By∈D所以(xy)∈BXD所以(xy)∈（AXC）∩（BXD）反過來，如果（xy）∈(AXC)∩（BXD）由于(xy)∈（AXC）所以x∈Ay∈C由于(xy)∈（BXD）所以x∈By∈D所以x∈(A∩B)y∈(C∩D)所以(xy)∈(A∩B)X(C∩D)所以(A∩B)X(C∩D)=(AXC)∩（BXD）1.5解：Hasse圖241241039故得（AB）XC=（AXC）（BXC）1.9略1.10略1.11解：A為n個(gè)元素的優(yōu)先級(jí)和，A

3、上有2n2個(gè)不同的二元關(guān)系，理由為：設(shè)A，B為集合，AXB的任何子集所定義的二元關(guān)系稱作從A到B的二元關(guān)系，特別當(dāng)A=B時(shí)，稱作A上的二元關(guān)系，若|A|=n，則|AXA|=n2，那么A上共有2n2個(gè)不同的二元關(guān)系。1.12略1.13解：1)真.由于R1和R2和R2都是自反的因而對(duì)任何都有(xx)∈R1(xx)∈R2.因此對(duì)任何x∈A都有(xx)∈R1R2.所以R1R2是自反的。2)假.令A(yù)=abR1=(ab)R2=ba.那么R1R2=(

4、aa)它就不是A上的反自反關(guān)系.3)假.令A(yù)=abcR1=(ab)(ba)R2=(bc)(cb).那末R1R2=(ac)就不是A的對(duì)稱關(guān)系.4)假.令A(yù)=abcdR1=(ac)(bc)R2=(cb)(da)易證R1R2都是反對(duì)稱關(guān)系.但是R1R2=(ab)(ba)就不是A上的反對(duì)稱關(guān)系.5)假.令A(yù)=abcR1=(ac)(ba)(bc)R2=(cb)(ac)(ab)易證R1和R2都是傳遞關(guān)∈系但R1R2=(ab)(bb)(bc)就不是A