1、問題回答一、回答“學習求助”(wzzlhlf)教材第42頁練習2.1(A)：1(1) 求的真值。其中P：3>2；Q(x)：x£3；R(x)：x>5，e：6，個體域D2,3,6。解 P為“3>2”，顯然為真，即PÛ1，e=6，R(e)為“6>5”，此命題真值為1，故R(e)Û1。二、回答“答張喜榮(wwwedu)”1任意集合A，B，證明P(A)ÈP(B)ÍP(AÈB) 證明 "xÎ(P(A)ÈP(B)ÛxÎP(A)ÚxÎP(B)Ûx&

2、#205;AÚxÍBÞxÍ(AÈB)ÛP(AÈB)說明：集合有性質AÍAÈB，BÍAÈB。xÍAÍAÈB，xÍBÍAÈB，所以xÍ(AÈB)Ç(AÈB)=AÈB。而AÇBÍA，AÇBÍB證明中的“xÍAÚxÍBÞxÍ(AÈB)”，只能是單方向Þ，而不是雙方向Û

3、。2. 教材第154頁23題。解 "x，xÎf1(AÇB)Ûf(x)ÎAÇBÛf(x)ÎAÙf(x)ÎBÛ說明：本題需要分清楚：f：X®Y，即XDom(f)，Ran(f)ÍY。Y的子集合A，B都是值域的部分，那么f1(A)或f1(B)都是定義域中的元素。3. 自反性與反自反性的區分，自反性就是所有<x,x>(第一元素與第二元素相等的有序對)都在二元關系R中，當然x應是集合A的元素；而反自反性就是所有<x,x>(第一元素與第二元素相等的有序對)

4、都不在二元關系R中。如Aa,b,c,那么只要含有<a,a>,<b,b>,<c,c>有序對的二元關系，就都具有自反性，而<a,a>,<b,b>,<c,c>有序對都沒有的二元關系，就都具有反自反性的。而有一個或兩個這種對的二元關系既不是自反的也不是反自反的。三、回答Email：heavy_rain_tien的問題原問題1. 證明“集合A上的二元關系是傳遞關系的充分必要條件是R·RÍR”是否要用歸納法？解答：不用歸納法，證明如下。證明 先證必要性Þ即已知R是傳遞關系，要證R·RÍ

5、R因為，若<a,c>ÎR·RÛ$bÎA(<a,b>ÎRÙ<b,c>ÎR)，由R是傳遞的定義，得到<a,c>Î<R，所以，若<a,c>ÎR·R，都有<a,c>Î<R故R·RÍR再證充分性，Ü，即已知R·RÍR，要證R是傳遞的由復合關系定義，若"<a,b>,<b,c>, 若<a,b>ÎRÙ&l

6、t;b,c>ÎRÞ<a,c>ÎR·RÍR,即<a,c>ÎR,所以R是傳遞的原問題2. 要畫出完全圖的子圖很容易漏掉，請問對于Kn的子圖數目有什么規律性？解答：作Kn的子圖，尤其是非同構的子圖，沒有好的規律可用一般地，對邊數歸納逐一做先做0條邊的，結點逐一增至n；再做1條邊的，結點逐一增至n；原問題3. 第6章定理4,5,9,12都省略了證明，老師是否可以提供一下？解答：下面給出幾個定理的證明。(1) 第6章定理4的證明定理4：設G<V,E>為無向簡單圖且½V½³3

7、，如果G中每對結點度數之和大于或等于½V½，則在G中存在一條哈密頓回路為了證明定理4，首先證明引理引理1：設G是有n個結點的無向簡單圖，如果G中每對結點度數之和大于或等于n1，則G中存在哈密頓通路證明 首先證明G是連通的否則，G中至少存在兩個連通分支G1和G2設G1有n1個結點，G2有n2個結點由于G是簡單圖，故G1和G2均為簡單圖因而于是 與題設條件矛盾所以G是連通圖下面證明存在哈密頓通路設Lv1v2vl為G中一條長度為l1的初級通路l£n，不妨設此通路的端點不再與L外的結點相鄰了，否則可將相鄰的結點擴充到該通路中來（1）若l=n，則L是G中哈密頓通路（2）若l

8、<n，我們來證明G存在過結點v1,v2,vl的初級回路若v1和vl相鄰，則v1v2vl v1為G中一初級回路若v1和vl不相鄰，設v1與=v2，相鄰，則，均在L上并且k³2，假若k=1，因為v1不與vl相鄰，因而，于是這與題設條件矛盾又vl至少與中的一個結點相鄰，否則vl至多與l11(k1)lk1個結點相鄰，于是這又與題設條件矛盾不妨設vl與相鄰(2£j£k)，見圖1所示去掉邊(),得回路，如圖2所示(3) 由于l<n，因而G中必存在不在回路上的結點由G的連通性，存在回路外的結點vx與回路上的結點vk相鄰，見圖3去掉邊(vk1,vk)得初級通路這條新的

9、通路比原來的通路多一條邊，對新的通路重復(1)，(2)，(3)重復上述過程，直到全部結點擴展到初級通路中來得G的一條哈密頓通路為止v1 v2 vi1 vl圖1v1 v2 vi1 vl圖2v1 v1 vk1 vk vi1 vlvx圖3下面證明定理4證明定理4 設G 有n個結點由引理，G中存在哈密頓通路不妨設v1v2vn為G中一條哈密頓通路(1) 若v1與vn相鄰，則v1v2vn為G中一條哈密頓回路(2) 若v1與vn不相鄰，用同證明引理類似的方法，可證存在過結點v1,v2,vn的初級回路，即為一條哈密頓回路(2) 第6章定理5的證明定理5：設有向圖D<V,E>，且½V

10、89;n³2如果所有的有向邊均用無向邊替代，所得無向圖中含生成子圖Kn，則有向圖D中存在哈密頓通路證明 由已知可知，有向圖是連通圖，且任何一對結點之間至少存在一條有向邊首先確定D中一條初級通路v1v2vp，p£n(1) 若p=n，則v1v2vp為D中哈密頓通路(2) 若p<n，必存在不在通路上的結點vx，若<vx,v1>ÎE，得初級通路vxv1v2vp，1)見圖4，通路增加一條邊若<vx,v1>ÏE，則<v1,vx>ÎE，這時若<vx,v2>ÎE，得初級通路v1vxv2v3vp，

11、通路也增加一條邊若<vx,v2>ÏE，則<v2,vx>ÎE，再考察v3vp，最后只可能有兩種情形： 1) 存在vi,2£i£p1，<vx,vi>ÎE，而<vx,vj>ÏE，1£j£i1，得通路v1v2vivxvivpv1 v2 vp-1 vpvx圖42)對任意i(1£i£p)，<vi,vx>ÎE，而<vx,vi>ÏE，這時得通路 v1v2v3vpvx總之無論如何將vx通擴進到初級通路v1v2v3vp中了v

12、1 v2 vp-1 vpvx圖5同樣，若新的通路外還有結點，用類似的方法，再將它擴進通路中來經過有限次，將圖中所有結點全能擴進通路中來，得D中一條通過圖中所有結點的初級通路，即為哈密頓通路(3) 第6章定理9的證明，定理9的證明比定理4，5還長請參考黃天發編著的離散數學第371373頁(16開本的書)(電子科技大學出版社出版，地址：610054 成都建設北路二段4號)(4) 第6章定理12的證明引理2：設G是連通簡單平面圖，則它一定有一個度數不超過5的結點證明 因為G是連通簡單平面圖，它的每個面至少有3條邊，所以有，即（其中r，e分別為圖G的面數和邊數） 假設結論不成立，則每個結點的度數都大于

13、等于6則有 ，即有（其中v是圖G的結點數）由歐拉公式：2=0矛盾所以G中至少有一個結點的度數小于或等于5定理12：任何平面圖G是5色的證明 不妨設G是連通圖，否則可對每個連通分支進行討論用1，2，3，4，5代表5種不同的顏色對圖G的結點數進行歸納證明當n£5時，定理顯然成立設結點數n=k³6時成立，我們來證明n=k+1時定理也成立由引理2可知，G中存在結點v，將v從圖G中刪去得圖記作G1，有假設G1是5色的將G1的各結點用5種顏色著色，然后將v及所關聯的邊加入G1，使其還原成G看v是否可著色(1) 若，當然v可著五種顏色的一種使其與相鄰的結點沒有相同的顏色(2) 若，但與v

14、相鄰的五個結點至多用了四種顏色，這時給v著一種顏色，使其與相鄰的結點沒有相同的顏色是辦得到的若與相鄰的結點已經用了五種顏色(如圖6)v1 1v2 2 v5 v C53 v34 v4圖6設V1u½u是G的結點，且u著顏色1或3設V的導出子圖為G1.3，若v1,v3分別屬于G1.3的不同的連通分支，則在v1所在的連通分支中，將1， 3兩種顏色對調，這時v1著顏色3，故可給v著顏色2若v1,v3屬于G1.3的同一個連通分支，則V1Èv的導出子圖中含從v1，經過v和v3以及V1中一些結點到v1的回路，設C是其中的一條回路(如圖6)，則C將G所在的平面分成兩個區域顯然v2和v4分別處

15、在這兩個區域中設V2u½u是G的結點且u著顏色2或4并設V的導出子圖為G2.4則v2和v4必屬于G2.4的不同的連通分支在v2所在的連通分支將2,4兩種顏色對調，使v2著顏色4于是，可將v著顏色2這就證明了5色定理引理2：設G是連通簡單平面圖，則它一定有一個度數不超過5的結點證明 因為G是連通簡單平面圖，它的每個面至少有3條邊，所以有，即（其中r，e分別為圖G的面數和邊數） 假設結論不成立，則每個結點的度數都大于等于6則有 ，即有（其中v是圖G的結點數）由歐拉公式：2=0矛盾所以G中至少有一個結點的度數小于或等于5原問題4. 第6章，定理14性質4“不含圈的連通圖”指的是什么？解答：

16、定理14就是討論樹的等價定義的，故“不含圈的連通圖”就是沒有回路的且連通的圖,即是樹原問題5. 回答練習6.3(A)：第4題寫出圖623的色多項式解答：(a) 答案為P(G,l)=，色數為3(b) 答案為P(G,l)=，色數為3即你的答案原教材上的答案與你的答案展開式，只是l5的系數有差別，書上答案系數為720，正確答案應為740可能是展開，合并同類項時計算有誤下面說明圖(a)的答案教材答案不對. 你的計算答案也有錯按照P(G,l)的定義(教材第206頁912行)，P(G,l)是使P(G,l)>0的l的最小值.P(G,l)=，顯然P(G,1)=P(G,2)=0,而P(G,3)=½

17、;l=3=6>0故色數為3但是，你的答案： P(G,l)=首先這不是l的6次多項式；不滿足P(G,1)=0現將解答過程列下用定理13將定理13改造如下記定理13中的G¢e為G，G為G+，G²e=G(注意：在G²e中有兩條平行線，我們討論的都是簡單圖，因此平行線應畫在一起，是一條線)于是，教材P206的圖619應為d d d c c c G+ G G圖619在本圖G中，不相鄰的兩個結點c,d之間加邊(c,d),得圖G；將圖G的兩個結點c,d合并，將d合到c,得圖G的左圖，將d合并到c，得圖G的右圖，均是一樣的于是，定理13的結論改寫成：P(G,l)=P(G,l

18、)+P(G,l)利用這個結論，計算圖623(a)的色多項式圖623(a)(即圖7(a)G)如下 f a 圖7 (a) G 圖G有6個結點，在G中添加不相鄰結點間的邊，再將該二個結點合并，將整個圖分解成若干個結點數不超過6的完全圖的和將G添加成K6，就需在不相鄰結點間，逐步添加邊和合并結點完成(1) 如圖7，在結點a,f之間加邊，再將其合并，得到圖8添加邊得到圖記作，c c b df f a e 圖8 圖8 合并a到f得到圖記作于是P(G,l)=P(,l)+P(l)(2) 對添加不相鄰結點的邊(b,e),再合并e到b，得圖，c c b df f a eG21 G22圖9 如圖9(3) 對再作添加

19、比相鄰結點的聯邊，而后再合并這兩個結點，又各自分別得到和，繼續對這些圖作添加不相鄰結點的聯邊，再合并二不相鄰結點直至所有圖都是完全圖，可得到一個K6，五個K5和六個K4(4) 再對作添加邊(b,e)，然后再合并e到b，得到圖10是K4；對作與前面相同的處理方法，可以得到一個K5，兩個K4和一個K3c c b df f G23 G24 圖10 總之，可以得到K6，6個K5，9個K4，1個K3即P(G,l)= P(K6,l)+6 P(K5,l)+9 P(K4,l)+ P(K3,l)由教材第206頁，倒數第2行：3. 若圖G是n個結點的完全圖，則P(Kn,l)=有P(K6,l)=P(K5,l)=P(

20、K4,l)=P(K3,l)=所以 P(G,l)=69原問題6. 習題6的第4題，“P(G)£½S½+1”,我認為應該是½S½。因為回路中去掉一結點a后，P(Ca)1。解答：請看原教材的題目，其中的C是哈密頓路(回路或通路)S是V的真子集合，顯然C要經過S的所有結點，故P(Ga)£2，而不是P(Ga)1故原結論成立只有C是回路時，P(Ga)1原問題7：練習7.3(B)第2，最后一步：既然k=minZ+，是滿足條件的最小正數，那么0£k<1成立？另外，H包含于ak理由也不充分。解答：請看教材練習7.3(B)第2的答案。書中

21、解答是正確的k=舉例，如6階循環群，G(a)=a0=e,a1,a2,a3,a4,a5G有子群：H(a2)=a0=e,a2,a4，顯然a2,a4,a6(=a0),a8,a10,a14,a16,ÎHk=2原問題8：據群的定義，+單位元是0，無零元；任意集合內元素a，有惟一a。而環的性質中+有零元0，a有負元a。我們以哪種說法為準？解答：關于單位元與0元在整數群(Z，)中，加法(普通數的加法)的單位元是“0”在環中，運算的0元是“0”這里的，不一定就只是數的加法所以不必將它們統一原問題9：環的零因子是否只針對第二個運算符？對于“既是做零因子，又是右零因子”的理解有二：(1) a¹0，a·a=0,則a是零因子；(2) a，b¹0，b·a=0,則a是零因子哪一個正確？若是前者，則練習8.1第4（2）,（3）的答案不對。解答：環的0因子是針對第二個運算·的；而第一個運算的類似的元素叫“負元”你關于“左、右零因子”的理解是對的練習8.1(A)的第4題答案正確(2) Z10，關于·(確切地說應為×10)的0因子是2,4,5,6,8因為2×